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

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 0mlnm0\leq m\leq l\leq n-m. A cutset is a collection CBn(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=lm+1c=l-m+1 and

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

Minimum-width conjecture. For nmn\gg m,

hn(m,l)=j0Δn(mjc)=Δn(m)+Δn(mc)+Δn(m2c)+.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,n1)=n1h_n(1,n-1)=n-1. 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.