Stabilities of the Kleitman diameter theorem

Abstract

Let $\mathcal{F}$ be a family of subsets of $[n]$. The diameter of $\mathcal{F}$ is the maximum size of symmetric differences among pairs of its members. Resolving a conjecture of Erdős, Kleitman determined the maximum size of a family with fixed diameter, which states that a family with diameter $s$ has cardinality at most that of a Hamming ball of radius $s/2$. Specifically, if $\mathcal{F}\subseteq 2^{[n]}$ is a family with diameter $s$, then for $s=2d$, $|\mathcal{F}|\le {\sum }_{i=0}^d\left(\genfrac{}{}{0ex}{}{n}{i}\right)$; for $s=2d+1$, $|\mathcal{F}|\le {\sum }_{i=0}^d\left(\genfrac{}{}{0ex}{}{n}{i}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{d}\right)$. This result is known as the Kleitman diameter theorem, which generalizes both the Katona union theorem and the Erdős--Ko--Rado theorem. In 2017, Frankl provided a complete characterization of the extremal families of Kleitman's theorem and provided a stability result. In this paper, we determine the extremal families of Frankl's theorem and establish a further stability result of Kleitman's theorem. This solves a recent problem proposed by Li and Wu. Our findings constitute the second stability for the Kleitman diameter theorem.

27pages;We simplified the proof of a Theorem