Simple juntas for shifted families

For the moment the link is to the submitted version of the article. It will be updated when the final version has been posted to arXiv.

Simple juntas for shifted families, Discrete Analysis 2020:14, 18 pp.

The Erdős-Ko-Rado theorem, proved in 1961 is a fundamental theorem about collections of sets. It states that if \(2k<n\) and \(\mathcal A\) is a collection of subsets of \(\{1,2,\dots,n\}\), each of size \(k\), such that any two of them intersect, then \(|\mathcal A|\leq\binom{n-1}{k-1}\). In other words, the obvious construction where one takes all sets that contain a given element is best possible. Moreover, it turns out to be unique. (If \(n=2k\), then one can do better by choosing, for each set \(A\) of size \(k\), exactly one of \(A\) and \(A^c\) to belong to \(\mathcal A\), and when \(n<2k\) one can take \(\mathcal A\) to consist of all sets of size \(k\).)

Many very interesting questions in combinatorics can be generated by taking an extremal problem and asking what can be said about near-extremal examples. Here, for example, one could ask what can be said about an intersecting family of \(k\)-sets if its size is close to the maximum, for various possible meanings of the word “close”. A rather remarkable theorem of Dinur and Friedgut from 2007 went a long way towards answering that question. One of their results was that if \(\mathcal A\) is a family of sets of size \(k\), where \(k\) is small compared with \(n\), then there is an element \(j\) that is contained in at most \(C\binom{n-2}{k-2}\) of the sets \(A\in\mathcal A\). To see where the numbers come from, observe that the family of all sets of size \(k\) that contain one of the sets \(\{1,2\}, \{2,3\}\) or \(\{1,3\}\) is intersecting and has size \(3\binom{n-2}{k-2}-2\binom{n-3}{k-3}\), which, since \(k\) is small, is approximately \(3\binom{n-2}{k-2}\).

More generally, a way of constructing intersecting families of \(k\)-sets is to take an intersecting family \(\mathcal F\) of subsets of a set \(J\) and to let \(\mathcal J\) be the set of all sets that intersect \(J\) in a set that belongs to \(\mathcal F\). If the sets in \(\mathcal F\) have size greater than \(r\) and \(J\) is of bounded size, then a set system \(\mathcal J\) constructed in this way has size at most \(C\binom{n-(r+1)}{k-(r+1)}\) (where \(C\) depends on \(r\) and \(|J|\)). A second result of Dinur and Friedgut, again assuming that \(k\) is small, is that for every \(r\) there exists a constant \(c(r)\) such that if \(\mathcal A\) is an intersecting family of \(k\)-sets, then there exists \(J\) of size at most \(c(r)\) and an intersecting family \(\mathcal F\) of subsets of \(J\) (which can all be taken to be of size at most \(r\)) such that all but \(c(r)\binom{n-(r+1)}{k-(r+1)}\) of the sets in \(\mathcal A\) contain a set in \(\mathcal F\). In other words, one can decrease the size of the error at the cost of making a more complicated assertion about the nature of the set system \(\mathcal A\).

The type of set system just discussed is known as a junta. More precisely, if \(J\subset\{1,2,\dots,n\}\) is a set of size at most \(j\), \(\mathcal F\) is a collection of subsets of \(J\), and \(\mathcal J\) is the set of all subsets of \(\{1,2,\dots,n\}\) that intersect \(J\) in some \(F\in\mathcal F\), then \(\mathcal J\) is called a \(j\)-junta. The junta is called intersecting if \(\mathcal F\) is an intersecting family. The conclusion of the first theorem above states that almost all of \(\mathcal A\) is contained in an intersecting 1-junta if \(\mathcal A\) has size substantially larger than \(\binom {n-2}{k-2}\), and the conclusion of the second states that almost all of \(\mathcal A\) is contained in an intersecting \(j(r)\)-junta if \(\mathcal A\) has size substantially larger than \(\binom{n-(r+1)}{k-(r+1)}\).

Friedgut and Dinur also proved results in the case where \(k=pn\) for some fixed \(p\), but these are slightly more complicated to state, and the approximating junta they obtained was not necessarily intersecting. Unfortunately, in order to obtain good bounds, they needed \(p\) to be very small, which restricts the applications of their results. The purpose of this paper is to impose an additional hypothesis that can often be assumed in applications, and to use it to obtain a simpler proof, and bounds that work for a much wider range of values of \(p\).

The additional hypothesis is that the family of sets \(\mathcal A\) is that it is shifted, or left-compressed. This means that if \(A\) belongs to \(\mathcal A\) and \(B\) is a set such that there is a bijection \(\phi:B\to A\) with \(\phi(x)\geq x\) for every \(x\in B\), then \(B\) also belongs to \(\mathcal A\). This sounds like a strong hypothesis, but there are several proofs of extremal problems that show that one can pass, by a process of “shifting” or “compression”, from an arbitrary set system to a shifted set system while preserving the properties of the system that are important for the problem.

Whereas previous results about approximation by juntas have made use of discrete Fourier analysis, this one is purely combinatorial. The authors apply their improved bounds to show that a theorem of Huang, Loh and Sudakov that applied only when the ground set is very large (as a function of various parameters) in fact holds for much smaller sizes as well. It is likely that the results of this paper will have other applications of this kind.