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
Primary 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).
Additional 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.
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.