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

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

M=(nn/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=1ksii=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 s1sMs_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.

Sources & referencesView supporting material

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.