Kleitman's conjecture about families of given size minimizing the number of kk-chains

preprint2016arXivOpen access

Abstract

A central theorem in combinatorics is Sperner's Theorem, which determines the maximum size of a family F⊆P(n)\mathcal{F}\subseteq \mathcal{P}(n) that does not contain a 22-chain F1⊊F2F_1\subsetneq F_2. Erdős later extended this result and determined the largest family not containing a kk-chain F1⊊…⊊FkF_1\subsetneq \ldots \subsetneq F_k. Erdős and Katona and later Kleitman asked how many such chains must appear in families whose size is larger than the corresponding extremal result. This question was resolved for 22-chains by Kleitman in 19661966, who showed that amongst families of size MM in P(n)\mathcal{P}(n), the number of 22-chains is minimized by a family whose sets are taken as close to the middle layer as possible. He also conjectured that the same conclusion should hold for all kk, not just 22. The best result on this question is due to Das, Gan and Sudakov who showed that Kleitman's conjecture holds for families whose size is at most the size of the k+1k+1 middle layers of P(n)\mathcal{P}(n), provided k≤n−6k\leq n-6. Our main result is that for every fixed kk and ε>0ε>0, if nn is sufficiently large then Kleitman's conjecture holds for families of size at most (1−ε)2n(1-ε)2^n, thereby establishing Kleitman's conjecture asymptotically. Our proof is based on ideas of Kleitman and Das, Gan and Sudakov. Several open problems are also given.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.