Simple juntas for shifted families
share
We say that a family F of k-element sets is a j-junta if there is a set J of size j such that, for any F, its presence in F depends on its intersection with J only. Approximating arbitrary families by j-juntas with small j is a recent powerful technique in extremal set theory. The weak point of all known approximation by juntas results is that they work in the range n>Ck, where C is an extremely fast growing function of the input parameters, such as the quality of approximation or the number of families we simultaneously approximate. t-intersecting families or for families with no s-matching C is at least exponential in t or s). We say that a family F is shifted if for any F={x_1,..., x_k}∈ F and any G ={y_1,..., y_k} such that y_i< x_i, we have G∈ F. For many extremal set theory problems, including the Erdős Matching Conjecture, or the Complete t-Intersection Theorem, it is sufficient to deal with shifted families only. In this note, we present very general approximation by juntas results for shifted families with explicit (and essentially linear) dependency on the input parameters. The results are best possible up to some constant factors, moreover, they give meaningful statements for almost all range of values of n. The proofs are shorter than the proofs of the previous approximation by juntas results and are completely self-contained.
READ FULL TEXT
