Polylogarithmic independence number conjecture for Paley graphs

About 3 years old · traced to

For a prime pp, let GpG_p be the Paley graph, let G‾p\overline G_p be its complement, and write α(Gp)=ω(G‾p)\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.

References

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.