A proof of Frankl's conjecture on cross-union families

2022/02/21 by Stijn Cambie, Jaehoon Kim, Cambie, Stijn +5
Mathematics · #05D05 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2202.10365

openalex publication_date 2022/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The families \mathcal F₀,…,\mathcal F_s of k-element subsets of [n]:=\1,2,…,n\ are called cross-union if there is no choice of F₀∈ \mathcal F₀, …, F_s∈ \mathcal F_s such that F₀∪…∪ F_s=[n]. A natural generalization of the celebrated Erdős--Ko--Rado theorem, due to Frankl and Tokushige, states that for n≤ (s+1)k the geometric mean of | \mathcal F_i| is at most \binomn-1k. Frankl conjectured that the same should hold for the arithmetic mean under some mild conditions. We prove Frankl's conjecture in a strong form by showing that the unique (up to isomorphism) maximizer for the arithmetic mean of cross-union families is the natural one \mathcal F₀=…=\mathcal F_s=[n-1]\choose k.

Related

• The binomial norm of intersecting-union families
• A note on non-empty cross-intersecting families
• Formalizing Frankl's Conjecture: FC-families
• The Frankl--Tokushige product conjectures for r-cross-intersecting families
• New Conjectures for Union-Closed Families