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
Full Text:
References:
  Kruskal, Mathematical Optimization Techniques pp 251– (1963)  Katona, Theory of Graphs pp 187– (1968)  DOI: 10.1016/0097-3165(95)90072-1 · Zbl 0839.05092  DOI: 10.1007/PL00009809 · Zbl 0909.06008  DOI: 10.1017/S0963548398003575 · Zbl 0915.05108  DOI: 10.1007/BF00537230 · Zbl 0501.60043  Dinur, Ann. of Math. 162 pp 439– (2005)  DOI: 10.1006/eujc.1995.0092 · Zbl 0869.05066  DOI: 10.1016/0095-8956(85)90043-7 · Zbl 0586.05029  Margulis, Prob. Peredachi Inform. 10 pp 101– (1974)  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.