The minimum-width conjecture for cutsets in the truncated Boolean lattice

About 11 years old · traced to

Let [n]={1,2,…,n}[n]=\{1,2,\ldots,n\}, let 2[n]2^{[n]} be the Boolean lattice ordered by inclusion, and let

Bn(m,l)=⋃i=ml([n]i),{\cal B}_n(m,l)=\bigcup_{i=m}^{l}\binom{[n]}{i},

where 0≤m≤l≤n−m0\leq m\leq l\leq n-m. A cutset is a collection C⊆Bn(m,l){\cal C}\subseteq{\cal B}_n(m,l) meeting every maximal saturated chain, and hn(m,l)h_n(m,l) is the minimum width of such a cutset. Set c=l−m+1c=l-m+1 and

Δn(k)=(nk)−(nk−1).\Delta_n(k)=\binom{n}{k}-\binom{n}{k-1}.

Minimum-width conjecture. For n≫mn\gg m,

hn(m,l)=∑j≥0Δn(m−jc)=Δn(m)+Δn(m−c)+Δn(m−2c)+⋯ .h_n(m,l)=\sum_{j\geq0}\Delta_n(m-jc)=\Delta_n(m)+\Delta_n(m-c)+\Delta_n(m-2c)+\cdots.

This conjecture seeks the minimum possible largest antichain in a cutset of the truncated Boolean lattice, generalizing the known result hn(1,n−1)=n−1h_n(1,n-1)=n-1. 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.