← All problems

Kahn's independent-set bound for regular graphs

16 years old · traced to

Let GG be a dd-regular graph with nn vertices, and let i(G)i(G) denote its number of independent sets. Alon and Kahn's conjecture. One has

i(G)≤i(Kd,d)n/(2d)=(2d+1−1)n/(2d).i(G) \leq i(K_{d,d})^{n/(2d)}=(2^{d+1}-1)^{n/(2d)}.

This formalized the proposed extremal role of a disjoint union of copies of Kd,dK_{d,d}; 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

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.