Kleitman's conjecture on minimizing the number of k-chains

About 13 years old · traced to

Let [n]={1,…,n}[n]=\{1,\ldots,n\} and let P(n)=2[n]\mathcal{P}(n)=2^{[n]} be the Boolean lattice. For integers n,M>0n,M>0, a family F⊆P(n)\mathcal{F}\subseteq\mathcal{P}(n) of size MM is centered if its sets are chosen from the layers whose sizes are as close to n/2n/2 as possible, filling the larger set-size first when two layers are equally distant from n/2n/2. A kk-chain is a sequence of kk sets F1⊊⋯⊊FkF_1\subsetneq\cdots\subsetneq F_k.

KleItman's conjecture. Let n,M>0n,M>0 and k≥2k\geq 2 be integers. Among families F⊆P(n)\mathcal{F}\subseteq\mathcal{P}(n) of size MM, the number of kk-chains in F\mathcal{F} is minimized by a centered family.

Kleitman proved the assertion for k=2k=2, while the conjecture for general kk is the main open problem addressed by the paper. The results establish it in a wide range of parameters, but not in full generality.

References

Primary source

Jozsef Balogh and Adam Zsolt Wagner, “Kleitman's conjecture about families of given size minimizing the number of k-chains”, arXiv:1609.02262 (2016).

Additional references

2 papers in this index state this conjecture (2013–2016). The statement above is taken from the most recent of them; the others are arXiv:1302.5210.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.