Polylogarithmic independence number conjecture for Paley graphs

For a prime pp, let GpG_p be the Paley graph, let Gp\overline G_p be its complement, and write α(Gp)=ω(Gp)\alpha(G_p)=\omega(\overline G_p) for its independence number. Here polylog(p)\mathsf{polylog}(p) denotes a fixed polylogarithmic function of pp. Polylogarithmic independence-number conjecture.

α(Gp)=O(polylog(p)).\alpha(G_p)=O(\mathsf{polylog}(p)).

Determining the independence number is a central problem connected with bounds for quadratic non-residues and Ramsey theory. The statement is described as widely believed, but remains open in the source.

Sources & referencesView supporting material

Primary source

Dmitriy Kunisky, “Spectral pseudorandomness and the road to improved clique number bounds for Paley graphs”, arXiv:2303.16475 (2023).

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.