Almost intersecting families (Q2662348)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Almost intersecting families |
scientific article |
Statements
Almost intersecting families (English)
0 references
12 April 2021
0 references
Summary: Let \(n > k > 1\) be integers, \([n] = \{1, \ldots, n\}\). Let \(\mathcal F\) be a family of \(k\)-subsets of \([n]\). The family \(\mathcal F\) is called intersecting if \(F \cap F^\prime \neq \emptyset\) for all \(F, F^\prime \in \mathcal F\). It is called almost intersecting if it is notintersecting but to every \(F \in \mathcal F\) there is at most one \(F^\prime\in \mathcal F\) satisfying \(F \cap F^\prime = \emptyset \). \textit{D. Gerbner} et al. [SIAM J. Discrete Math. 26, No. 4, 1657--1669 (2012; Zbl 1261.05126)] proved that if \(n \geq 2k + 2\) then \(|\mathcal F| \leqslant\binom{n - 1}{k - 1}\) holds for almost intersecting families. Our main result implies the considerably stronger and best possible bound \(|\mathcal F| \leqslant\binom{n - 1}{k - 1} - \binom{n - k - 1}{k - 1} + 2\) for \(n > (2 + o(1))k\), \(k\geqslant 3\).
0 references
extremal set theory
0 references
intersection theorems
0 references
Sperner-type theorems
0 references