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
    0 references
    0 references
    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
    0 references
    extremal set theory
    0 references
    intersection theorems
    0 references
    Sperner-type theorems
    0 references
    0 references
    0 references