Kahn's independent-set bound for regular graphs
Let be a -regular graph with vertices, and let denote its number of independent sets. Alon and Kahn's conjecture. One has
This formalized the proposed extremal role of a disjoint union of copies of ; the conjecture was subsequently resolved by Sah, who proved the relevant upper bound.
References
6 papers in this index state this conjecture (2010–2024). The statement above is taken from the most recent of them; the others are arXiv:1610.09210, arXiv:1406.7872, arXiv:1206.3211, arXiv:1007.4811, arXiv:1007.4803.
Source: Dev Chheda, Ram Goel and Eddie Qiao, “Number of Independent Sets in Regular and Irregular Graphs: A 31 Year Journey”, arXiv:2405.18815 (2024).
Progress summary
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.