Tight bounds for Katona's shadow intersection theorem

DOI10.1016/J.EJC.2021.103391zbMath1469.05161arXiv2005.06999OpenAlexW3178101769MaRDI QIDQ2048364

Dhruv Mubayi, Xizhi Liu

Publication date: 5 August 2021

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: A fundamental result in extremal set theory is Katona's shadow intersection theorem, which extends the Kruskal-Katona theorem by giving a lower bound on the size of the shadow of an intersecting family of $k$-sets in terms of its size. We improve this classical result and a related result of Ahlswede, Aydinian, and Khachatrian by proving tight bounds for families that can be quite small. For example, when $k=3$ our result is sharp for all families with $n$ points and at least $3n-7$ triples. Katona's theorem was extended by Frankl to families with matching number $s$. We improve Frankl's result by giving tight bounds for large $n$.

Full work available at URL: https://arxiv.org/abs/2005.06999

zbMATH Keywords

Kruskal-Katona theoremKatona's shadow intersection theorem

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Extremal set theory (05D05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved bounds for Erdős' matching conjecture
• A new short proof of the EKR theorem
• On hypergraphs without two edges intersecting in a given number of vertices
• Extremal problems concerning Kneser-graphs
• On Sperner families in which no k sets have an empty intersection
• On maximal antichains containing no set and its complement
• Shadows and shifting
• Some best possible inequalities concerning cross-intersecting families
• Some intersection theorems
• On a conjecture on the Sperner property
• Resilient hypergraphs with fixed matching number
• The complete nontrivial-intersection theorem for systems of finite sets
• On shadows of intersecting families
• The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton–Milner family
• The structure of large intersecting families
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On Mubayi's Conjecture and Conditionally Intersecting Sets
• Intersection theorems for systems of finite sets
• On intersecting families of finite sets

Related Items (1)

On strengthenings of the intersecting shadow theorem

This page was built for publication: Tight bounds for Katona's shadow intersection theorem