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

Abstract

The families ${\mathcal{F}}_0,\dots ,{\mathcal{F}}_s$ of $k$-element subsets of $[n]:=\{1,2,\dots ,n\}$ are called cross-union if there is no choice of $F_0\in {\mathcal{F}}_0,\dots ,F_s\in {\mathcal{F}}_s$ such that $F_0\cup \dots \cup F_s=[n]$. A natural generalization of the celebrated Erdős--Ko--Rado theorem, due to Frankl and Tokushige, states that for $n\le (s+1)k$ the geometric mean of $|{\mathcal{F}}_i|$ is at most $\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$. 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}}_0=\dots ={\mathcal{F}}_s=\left(\genfrac{}{}{0ex}{}{[n-1]}{k}\right)$.

14 pages, 1 figure Accepted at Combinatorial Theory