Intersecting Families are Essentially Contained in Juntas

Source abstract

A family $\J$ of subsets of {1, . . ., n } is called a j -junta if there exists J ⊆ {1, . . ., n }, with | J | = j , such that the membership of a set S in $\J$ depends only on S ∩ J . In this paper we provide a simple description of intersecting families of sets. Let n and k be positive integers with k < n /2, and let $\A$ be a family of pairwise intersecting subsets of {1, . . ., n }, all of size k . We show that such a family is essentially contained in a j -junta $\J$ , where j does not depend on n but only on the ratio k / n and on the interpretation of ‘essentially’. When k = o ( n ) we prove that every intersecting family of k -sets is almost contained in a dictatorship, a 1-junta (which by the Erdős–Ko–Rado theorem is a maximal intersecting family): for any such intersecting family $\A$ there exists an element i ∈ {1, . . ., n } such that the number of sets in $\A$ that do not contain i is of order $\C {n-2}{k-2}$ (which is approximately $\frac {k}{n-k}$ times the size of a maximal intersecting family). Our methods combine traditional combinatorics with results stemming from the theory of Boolean functions and discrete Fourier analysis.