Ilinca–Kahn conjecture for maximal independent sets in the Boolean-layer graph

For positive integers nn and kk, let Bn,k\mathcal{B}_{n,k} be the graph with vertex set ([n]k)([n]k+1)\binom{[n]}{k}\cup\binom{[n]}{k+1} and edges given by inclusion, and let mis(G)\operatorname{mis}(G) denote the number of maximal independent sets of a graph GG. Ilinca–Kahn conjecture.

mis(Bn,k)=(1+o(1))n2(n1k),\operatorname{mis}(\mathcal{B}_{n,k})=(1+o(1))n2^{\binom{n-1}{k}},

where the o(1)o(1) term tends to 00 as nn\to\infty. Ilinca and Kahn had proved the corresponding logarithmic asymptotic, while this conjecture predicts the sharp leading factor for the number of maximal independent sets.

Sources & referencesView supporting material

Primary source

Jozsef Balogh, Andrew Treglown and Adam Zsolt Wagner, “Applications of graph containers in the Boolean lattice”, arXiv:1602.05870 (2018).

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.