Intersecting families are essentially contained in juntas.

*(English)*Zbl 1243.05235Summary: 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.

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.

##### Keywords:

juntas; intersecting subsets; intersecting families; Erdős-Ko-Rado theorem; Boolean function; Fourier analysis
PDF
BibTeX
XML
Cite

\textit{I. Dinur} and \textit{E. Friedgut}, Comb. Probab. Comput. 18, No. 1--2, 107--122 (2009; Zbl 1243.05235)

Full Text:
DOI

**OpenURL**

##### 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.