Independence number conjecture for sparse random Cayley graphs

Let GG be a group of size nn, and let G(p)G(p) be its random Cayley graph, formed by selecting each equivalence class {x,x}\{x,-x\} independently with probability pp. Write α(G(p))\alpha(G(p)) for its independence number, and use O~\tilde{O} to suppress polylogarithmic factors in G|G|. Independence number conjecture. The independence number of the random Cayley graph G(p)G(p) is at most O~(p1)\tilde{O}(p^{-1}) whp. This predicts that sparse random Cayley graphs have independence numbers comparable, up to polylogarithmic factors, to random regular graphs of the same degree. The statement is presented as a conjecture and no resolution is given in the source.

Sources & referencesView supporting material

Primary source

Noga Alon and Huy Tuan Pham, “Random Cayley graphs and random sumsets”, arXiv:2509.02561 (2025).

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.