Combinatorial Theory

The families \(\mathcal{F}_0,\ldots,\mathcal{F}_s\) of \(k\)-element subsets of \([n]:=\{1,2,\ldots,n\}\) are called cross-union if there is no choice of \(F_0\in \mathcal{F}_0, \ldots, F_s\in \mathcal{F}_s\) such that \(F_0\cup\ldots\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 \(\lvert\mathcal{F}_i\rvert\) is at most \(\binom{n-1}{k}\). 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=\ldots=\mathcal{F}_s={[n-1]\choose k}\).

Mathematics Subject Classifications: 05D05

Keywords: Extremal set theory, generalizations of Erdős-Ko-Rado, cross-union families, cross-intersecting families