Griggs's dominance conjecture for chain decompositions of the Boolean lattice

About 7 years old · traced to

Let [n]={1,…,n}[n]=\{1,\dots,n\}, let 2[n]2^{[n]} be the Boolean lattice, and set

M=(n⌊n/2⌋).M=\binom{n}{\lfloor n/2\rfloor}.

Let σ1≥⋯≥σM\sigma_1\geq\dots\geq\sigma_M be the sizes of the chains in a symmetric chain decomposition of 2[n]2^{[n]}. A sequence s1,…,sMs_1,\dots,s_M is dominated by σ1,…,σM\sigma_1,\dots,\sigma_M when

∑i=1ksi≤∑i=1kσi(k=1,…,M).\sum_{i=1}^k s_i\leq\sum_{i=1}^k\sigma_i\quad (k=1,\dots,M).

Griggs's conjecture. If s1≥⋯≥sMs_1\geq\dots\geq s_M is a sequence of positive integers dominated by σ1,…,σM\sigma_1,\dots,\sigma_M and

∑i=1Msi=2n,\sum_{i=1}^M s_i=2^n,

then there exists a chain decomposition D1,…,DMD_1,\dots,D_M of 2[n]2^{[n]} such that ∣Di∣=si|D_i|=s_i for every ii. The conjecture proposes that every admissible chain-size sequence below the symmetric-chain profile can be realized. The source attributes it to Griggs; it notes that the uniform chain decomposition conjecture is a special subcase and may be the most challenging one.

References

Primary source

Benny Sudakov, Istvan Tomon and Adam Zsolt Wagner, “Uniform chain decompositions and applications”, arXiv:1911.09533 (2019).

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.