×

zbMATH — the first resource for mathematics

Intersecting families are essentially contained in juntas. (English) Zbl 1243.05235
Summary: A family \(\mathcal J\) of subsets of \(\{1,\dots , n\}\) is called a \(j\)-junta if there exists \(J \subseteq \{1, \dots, n\}\), with \(|J| = j\), such that the membership of a set \(S\) in \(\mathcal J\) depends only on \(S \cap 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 \(\mathcal A\) be a family of pairwise intersecting subsets of \(\{1, \dots, n\}\), all of size \(k\). We show that such a family is essentially contained in a \(j\)-junta \(\mathcal 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 \(\mathcal A\) there exists an element \(i \in \{1, \dots, n\}\) such that the number of sets in \(\mathcal A\) that do not contain \(i\) is of order \(\binom{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.

MSC:
05D05 Extremal set theory
05A18 Partitions of sets
05B99 Designs and configurations
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Kruskal, Mathematical Optimization Techniques pp 251– (1963)
[2] Katona, Theory of Graphs pp 187– (1968)
[3] DOI: 10.1016/0097-3165(95)90072-1 · Zbl 0839.05092
[4] DOI: 10.1007/PL00009809 · Zbl 0909.06008
[5] DOI: 10.1017/S0963548398003575 · Zbl 0915.05108
[6] DOI: 10.1007/BF00537230 · Zbl 0501.60043
[7] Dinur, Ann. of Math. 162 pp 439– (2005)
[8] DOI: 10.1006/eujc.1995.0092 · Zbl 0869.05066
[9] DOI: 10.1016/0095-8956(85)90043-7 · Zbl 0586.05029
[10] Margulis, Prob. Peredachi Inform. 10 pp 101– (1974)
[11] DOI: 10.1093/qmath/12.1.313 · Zbl 0100.01902
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.