2020/04/18 by Péter Frankl, Frankl, Peter, Andrey Kupavskii +1 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · doi:10.48550/arxiv.2004.08714
openalex publication_date 2020/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let n > k > 1 be integers, [n] = \1, …, n\. Let \mathcal F be a family of k-subsets of~[n]. The family \mathcal F is called intersecting if F ∩ F' ≠ ∅ for all F, F' ∈ \mathcal F. It is called almost intersecting if it is not intersecting but to every F ∈ \mathcal F there is at most one F'∈ \mathcal F satisfying F ∩ F' = ∅. Gerbner et al. proved that if n ≥ 2k + 2 then |\mathcal F| ≤ n - 1\choose k - 1 holds for almost intersecting families. The main result implies the considerably stronger and best possible bound |\mathcal F| ≤ n - 1\choose k - 1 - n - k - 1\choose k - 1 + 2 for n > (2 + o(1))k.