The equality conjecture for level-width and cutset-width in the truncated Boolean lattice

Let [n]={1,2,,n}[n]=\{1,2,\ldots,n\} and let Bn(m,l){\cal B}_n(m,l) be the truncated Boolean lattice consisting of all subsets of [n][n] of sizes from mm through ll. A cutset is a collection meeting every maximal saturated chain. Let hn(m,l)h_n(m,l) be the minimum width of a cutset, and let gn(m,l)g_n(m,l) be the smallest kk for which there is a cutset containing at most kk nodes at each level. Equality conjecture. If 0mlnm10\leq m\leq l\leq n-m-1 and nmn\gg m, then

gn(m,l)=hn(m,l).g_n(m,l)=h_n(m,l).

In addition,

gn(m,nm)=(n1m)(n1m1).g_n(m,n-m)=\binom{n-1}{m}-\binom{n-1}{m-1}.

The inequality hn(m,l)gn(m,l)h_n(m,l)\geq g_n(m,l) is immediate from the definitions, while the conjecture predicts equality in the stated range and gives an additional boundary formula. The source gives no resolution, so its status remains open.

Sources & referencesView supporting material

Primary source

Béla Bajnok, “On the Minimum Width of a Cutset in the Truncated Boolean Lattice”, arXiv:1512.02978 (2015).

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.