Article contents
A Stability Result for Families with Fixed Diameter
Published online by Cambridge University Press: 06 March 2017
Abstract
Let $\mathcal F$ ⊂ 2[n] be a family of subsets. The diameter of $\mathcal F$ is the maximum of the size of symmetric differences among pairs of members of $\mathcal F$. In 1966 Kleitman determined the maximum of |$\mathcal F$| for fixed diameter. However, this important classical result lacked a characterization of the families meeting the bound. This is remedied in the present paper, where a best possible stability result is established as well.
In Section 4 we introduce a ‘parity trick’ that provides an easy way of deducing the odd case from the even case in both Kleitman's original theorem and its stability version.
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2017
References
- 3
- Cited by