Ilinca–Kahn's precise asymptotics conjecture for maximal independent sets in B(n,k)

About 1 year old · traced to

For positive integers nn and k≤nk\leq n, let B(n,k)B(n,k) be the bipartite graph with vertex set consisting of the kk-subsets and (k−1)(k-1)-subsets of [n][n], with adjacency given by inclusion. Write mis⁡(B(n,k))\operatorname{mis}(B(n,k)) for the number of maximal independent sets of this graph.

Ilinca–Kahn's conjecture. The precise asymptotics satisfy

mis⁡(B(n,k))=(1+o(1))⋅n⋅2(n−1k−1).\operatorname{mis}(B(n,k))=(1+o(1))\cdot n\cdot 2^{\binom{n-1}{k-1}}.

This conjecture strengthens the known logarithmic asymptotics log⁡2mis⁡(B(n,k))=(1+o(1))(n−1k−1)\log_2\operatorname{mis}(B(n,k))=(1+o(1))\binom{n-1}{k-1} proved by Ilinca and Kahn. The source presents the precise asymptotic formula as an open question.

References

Primary source

József Balogh, Ce Chen and Ramon I. Garcia, “Maximal independent sets in the middle two layers of the Boolean lattice”, arXiv:2505.00132 (2025).

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.