Kahn's independent-set bound for regular graphs

About 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

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

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.