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

At least 10 years old · documented by

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 0≤m≤l≤n−m−10\leq m\leq l\leq n-m-1 and n≫mn\gg m, then

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

In addition,

gn(m,n−m)=(n−1m)−(n−1m−1).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.

References

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.