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

For positive integers nn and knk\leq n, let B(n,k)B(n,k) be the bipartite graph with vertex set consisting of the kk-subsets and (k1)(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))n2(n1k1).\operatorname{mis}(B(n,k))=(1+o(1))\cdot n\cdot 2^{\binom{n-1}{k-1}}.

This conjecture strengthens the known logarithmic asymptotics log2mis(B(n,k))=(1+o(1))(n1k1)\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.

Sources & referencesView supporting material

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.