A local version of Katona's intersection theorem

2022/06/09 by Sales, Marcelo, Schülke, Bjarne
#05D05 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2206.04278

Abstract

Katona's intersection theorem states that every intersecting family \mathcal F⊆[n]^(k) satisfies \vert∂\mathcal F\vert≥\vert\mathcal F\vert, where ∂\mathcal F=\F∖ x:x∈ F∈\mathcal F\ is the shadow of \mathcal F. Frankl conjectured that for n>2k and every intersecting family \mathcal F⊆ [n]^(k), there is some i∈[n] such that \vert ∂ \mathcal F(i)\vert≥ \vert\mathcal F(i)\vert, where \mathcal F(i)=\F∖ i:i∈ F∈\mathcal F\ is the link of \mathcal F at i. Here, we prove this conjecture in a very strong form for n> \binomk+12. In particular, our result implies that for any j∈[k], there is a j-set \a₁,…,a_j\∈[n]^(j) such that \vert ∂ \mathcal F(a₁,…,a_j)\vert≥ \vert\mathcal F(a₁,…,a_j)\vert. A similar statement is also obtained for cross-intersecting families.

Related

• Tight bounds for Katona's shadow intersection theorem
• On strengthenings of the intersecting shadow theorem
• A note on non-empty cross-intersecting families
• Intersecting non-uniform families containing subfamilies
• Some intersection theorems for finite sets