Non-trivial \(d\)-wise intersecting families (Q2221841)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Non-trivial \(d\)-wise intersecting families |
scientific article |
Statements
Non-trivial \(d\)-wise intersecting families (English)
0 references
2 February 2021
0 references
According to the celebrated Erdős-Ko-Rado theorem, the maximal size of a family \(\mathcal{F}\) of \(k\)-element subsets of \([n] = \{1,\ldots,n\}\), where \(n\geq 2k\) and where each pair of subsets has non-empty intersection, is \(\binom{n-1}{k-1}\). With the additional constraint that no element is contained in all members of \(\mathcal{F}\), the maximal size of \(\mathcal{F}\) is \(\binom{n-1}{k-1}-\binom{n-k-1}{k-1}+1\). This was proved by \textit{A. J. W. Hilton} and \textit{E. C. Milner} [Q. J. Math., Oxf. II. Ser. 18, 369--384 (1967; Zbl 0168.26205)] who further considered families \(\mathcal{F}\) for which each \(d\) members have non-empty intersection. Hilton and Milner [loc. cit.] conjectured that, for \(n\) sufficiently large, when such family \(\mathcal{F}\) has maximal size, it is isomorphic either to the family of \(k\)-subsets which contain at least \(d\) elements of \(\{1,\ldots,d+1\}\) or to the family \[ \{A\in\binom{n}{k} : [d-1] \subset A, A\cap [d,k+1] \neq \emptyset \}\cup\{[k+1]\setminus \{i\} : i\in[d-1]\}\,. \] The authors of the present article verifies this conjecture and improves this result by proving a stronger and very interesting theorem on the structure of \(\mathcal{F}\) when \(\mathcal{F}\) is sufficiently large.
0 references
extremal set theory
0 references
delta system method
0 references
intersecting families
0 references
0 references