The equality conjecture for level-width and cutset-width in the truncated Boolean lattice
The equality conjecture for level-width and cutset-width in the truncated Boolean lattice
Let and let be the truncated Boolean lattice consisting of all subsets of of sizes from through . A cutset is a collection meeting every maximal saturated chain. Let be the minimum width of a cutset, and let be the smallest for which there is a cutset containing at most nodes at each level. Equality conjecture. If and , then
In addition,
The inequality 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.