Simple juntas for shifted families

Abstract

We say that a family $\mathcal{F}$ of $k$-element sets is a {\it $j$-junta} if there is a set $J$ of size $j$ such that, for any $F$, its presence in $\mathcal{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 junta approximation 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. We say that a family $\mathcal{F}$ is {\it shifted} if for any $F=\{x_1,\dots ,x_k\}\in \mathcal{F}$ and any $G=\{y_1,\dots ,y_k\}$ such that $y_i\le x_i$, we have $G\in \mathcal{F}$. For many extremal set theory problems, including the Erd\H os Matching Conjecture, or the Complete $t$-Intersection Theorem, it is sufficient to deal with shifted families only. In this paper, 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. As an application of our junta approximation, we give a nearly-linear bound for the multi-family version of the Erd\H os Matching Conjecture. More precisely, we prove the following result. Let $n\ge 12sk\log (e^{2}s)$ and suppose that the families ${\mathcal{F}}_1,\dots ,{\mathcal{F}}_s\subset \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ do not contain $F_1\in {\mathcal{F}}_1,\dots ,F_s\in {\mathcal{F}}_s$ such that $F_i$'s are pairwise disjoint. Then ${\min }_i|{\mathcal{F}}_i|\le \left(\genfrac{}{}{0ex}{}{n}{k}\right)-\left(\genfrac{}{}{0ex}{}{n-s+1}{k}\right).$

References in corpus (2)

• Hypercontractivity for global functions and sharp thresholds
• The Junta Method for Hypergraphs and the Erdős-Chvátal Simplex Conjecture

Cited by in corpus (7)

• Global hypercontractivity and its applications
• A better bound on the size of rainbow matchings
• Rainbow perfect matchings for 4-uniform hypergraphs
• Co-degree threshold for rainbow perfect matchings in uniform hypergraphs
• On stability of rainbow matchings
• Transversal Hamilton cycle in hypergraph systems
• Extremal Problem for Matchings and Rainbow Matchings on Direct Products