Alon–Kahn conjecture on independent sets in regular graphs

About 17 years old · traced to

Let GG be a simple, finite, undirected graph with NN vertices that is dd-regular, and let i(G)i(G) denote its number of independent sets. The graph N2dKd,d\frac{N}{2d}K_{d,d} is the disjoint union of N2d\frac{N}{2d} copies of the complete bipartite graph Kd,dK_{d,d}. Alon–Kahn conjecture. For every such graph GG,

i(G)≤(2d+1−1)N2d.i(G) \leq \left(2^{d+1}-1\right)^\frac{N}{2d}.

Kahn proved this bound for regular bipartite graphs, while the conjecture asserts it for all regular graphs; the general case remains open in the supplied text.

References

Primary source

David Galvin, “An upper bound for the number of independent sets in regular graphs”, arXiv:1007.4811 (2010).

Additional references

2 papers in this index state this conjecture (2009–2010). The statement above is taken from the most recent of them; the others are arXiv:0909.3354.

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.