Independence number conjecture for sparse random Cayley graphs
Independence number conjecture for sparse random Cayley graphs
Let be a group of size , and let be its random Cayley graph, formed by selecting each equivalence class independently with probability . Write for its independence number, and use to suppress polylogarithmic factors in . Independence number conjecture. The independence number of the random Cayley graph is at most 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.