Sperner's theorem and a problem of Erdős, Katona and Kleitman
From MaRDI portal
(Redirected from Publication:5364244)
Abstract: A central result in extremal set theory is the celebrated theorem of Sperner from 1928, which gives the size of the largest family of subsets of [n] not containing a 2-chain. Erdos extended this theorem to determine the largest family without a k-chain. Erdos and Katona, followed by Kleitman, asked how many chains must appear in families with sizes larger than the corresponding extremal bounds. In 1966, Kleitman resolved this question for 2-chains, showing that the number of such chains is minimized by taking sets as close to the middle level as possible. Moreover, he conjectured the extremal families were the same for k-chains, for all k. In this paper, making the first progress on this problem, we verify Kleitman's conjecture for the families whose size is at most the size of the middle levels. We also characterize all extremal configurations.
Recommendations
Cites work
- A generalization of Sperner's theorem and an application to graph orientations
- Extremal problems among subsets of a set
- scientific article; zbMATH DE number 3845613 (Why is no real title available?)
- scientific article; zbMATH DE number 1016362 (Why is no real title available?)
- scientific article; zbMATH DE number 3256524 (Why is no real title available?)
- scientific article; zbMATH DE number 3188526 (Why is no real title available?)
- On a lemma of Littlewood and Offord
- On a theorem of Rademacher-Turán
- On induced subgraphs of the cube
- Supersaturation in the Boolean lattice
- The minimum number of disjoint pairs in set systems and related problems
Cited in
(29)- Kleitman's conjecture about families of given size minimizing the number of \(k\)-chains
- Supersaturation in posets and applications involving the container method
- Infinite Sperner's theorem
- A generalization of the independence number
- Multicolor chain avoidance in the Boolean lattice
- A continuous analogue of Erdős' \(k\)-Sperner theorem
- Colouring set families without monochromatic k-chains
- Structure and supersaturation for intersecting families
- Supersaturation, counting, and randomness in forbidden subposet problems
- Maximum-size antichains in random set-systems
- On saturated k-Sperner systems
- A random version of Sperner's theorem
- On the number of K₄-saturating edges
- Subsets of posets minimising the number of chains
- Supersaturation and stability for forbidden subposet problems.
- On the number of monotone sequences
- Comparable pairs in families of sets
- A note on supersaturated set systems
- The ``\(k = 1\) case of a problem of Greene and Kleitman from 1976: join-irreducible elements in the lattice of Sperner 1-families
- The minimum number of disjoint pairs in set systems and related problems
- Supersaturation in the Boolean lattice
- The number of additive triples in subsets of abelian groups
- Set systems containing many maximal chains
- On some extremal and probabilistic questions for tree posets
- Families in posets minimizing the number of comparable pairs
- Solution to a problem of Katona on counting cliques of weighted graphs
- A short note on supersaturation for oddtown and eventown
- Supersaturation, counting, and randomness in forbidden subposet problems
- On supersaturation for oddtown and eventown
This page was built for publication: Sperner's theorem and a problem of Erdős, Katona and Kleitman
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5364244)
