Centered-set conjecture for k-chains in grid posets

About 10 years old · traced to

Let [m]d[m]^d be the product poset, ordered coordinatewise: a≤b\mathbf{a}\leq\mathbf{b} when ai≤bia_i\leq b_i for every i∈[d]i\in[d]. A kk-chain is a set of kk distinct points satisfying a1≤⋯≤ak\mathbf{a}_1\leq\cdots\leq\mathbf{a}_k. For F⊆[m]d\mathcal{F}\subseteq[m]^d, call F\mathcal{F} mm-centered if, whenever a∈F\mathbf{a}\in\mathcal{F} and b∉F\mathbf{b}\notin\mathcal{F},

∣∑i=1dai−dm2∣≤∣∑i=1dbi−dm2∣,\left\lvert\sum_{i=1}^d a_i-\frac{dm}{2}\right\rvert\leq\left\lvert\sum_{i=1}^d b_i-\frac{dm}{2}\right\rvert,

and equality implies ∑i=1dai≥∑i=1dbi\sum_{i=1}^d a_i\geq\sum_{i=1}^d b_i.

Centered-set conjecture. Given mm, there exists a number d0(m)d_0(m) such that if d≥d0(m)d\geq d_0(m), then the sets minimizing the number of kk-chains among subsets of [m]d[m]^d of any prescribed size are mm-centered.

This is a proposed extension of Kleitman's question from the Boolean lattice to grid posets. The source emphasizes that the conjecture is a natural guess with little supporting evidence and does not claim uniqueness of the minimizers.

References

Primary source

Jozsef Balogh and Adam Zsolt Wagner, “Kleitman's conjecture about families of given size minimizing the number of k-chains”, arXiv:1609.02262 (2016).

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.