Paperlane

no. 15 · Monday 16 November 2026

Stabilities of the Kleitman diameter theorem

Yongjiang Wu, Yongtao Li, Lihua Feng, Jiuqiang Liu and Guihai Yu

math.CO · v3

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
pdf ↗ page arXiv:2411.08325 ↗