← All problems

Alon–Kahn conjecture on independent sets in regular graphs

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}.
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.

Status

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

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.