Asymptotic sharpness of the layered lower bound for Boolean-lattice chain covers

Less than 1 year old · traced to

Let BnB_n be the Boolean lattice of subsets of an nn-element set, and let N(n,r)N(n,r) denote the minimum number of maximal chains needed to cover all strict rr-term chains in BnB_n. For an admissible gap vector (a0,…,ar)(a_0,\dots,a_r), meaning a0,are0a_0,a_r e 0 or a0,ar≥0a_0,a_r\ge 0 and ai≥1a_i\ge 1 for 1≤i≤r−11\le i\le r-1, with a0+⋯+ar=na_0+\cdots+a_r=n, define

M(n,r):=max⁡a(na0,a1,…,ar).M(n,r):=\max_{\mathbf a}\binom{n}{a_0,a_1,\dots,a_r}.

Asymptotic sharpness conjecture. For every fixed r≥1r\ge 1,

N(n,r)=(1+o(1))M(n,r).N(n,r)=(1+o(1))M(n,r).

The quantity M(n,r)M(n,r) is a layered lower bound obtained by fixing the gap vector of the covered chains. The conjecture is disproved: the exact equality version is false in general, as shown by the paper's discussion of small values.

References

Primary source

Zoltán Lóránt Nagy and Balázs Patkós, “Chain Covers in the Boolean Lattice”, arXiv:2606.29385 (2026).

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.