no. 15 · Monday 16 November 2026
Stabilities of the Kleitman diameter theorem
Abstract
Let $\mathcal{F}$ be a family of subsets of $[n]$. The diameter of $\mathcal{F}$ is defined as the maximum size of the symmetric difference between any two of its members. Resolving a conjecture of Erdős, Kleitman determined the maximum size of a family with fixed diameter. Specifically, if $2\leq s\leq n-2$ and $\mathcal{F}\subseteq2^{[n]}$ is a family with diameter $s$, then for $s=2d$, $|\mathcal{F}|\le \sum_{i=0}^d {n \choose i}$; for $s=2d+1$, $|\mathcal{F}|\le \sum_{i=0}^d {n \choose i} + {n-1 \choose d}$. This result, known as the Kleitman diameter theorem, generalizes both the Katona union theorem and the Erdős–Ko–Rado theorem. In 2017, Frankl provided a complete characterization of the extremal families for Kleitman's theorem and established a stability result. In this paper, we determine the extremal families for Frankl's theorem and prove a further stability result of Kleitman's theorem. This solves a recent problem proposed by Li and Wu and provides the second stability for the Kleitman diameter theorem.
- comments
- Final version
- journal
- European Journal of Combinatorics 140 (2027) 104477
- fields
- Combinatorics