Improvement on the Hanson–Petridis bound via degree-2 localization

Let pp be prime, let GpG_p be the Paley graph, let gg be a multiplicative generator of Fp×\mathbb F_p^\times, and let ϑ\vartheta denote the Lovász theta function. Improvement conjecture. There exists ε>0\varepsilon>0 such that, for all sufficiently large pp,

ϑ(Gp,{0,g})(12ε)p.\vartheta(G_{p,\{0,g\}})\leq\left(\frac1{\sqrt2}-\varepsilon\right)\sqrt p.

Here Gp,{0,g}G_{p,\{0,g\}} is the degree-2 localized Paley subgraph. Numerical experiments suggest an improvement over the Hanson–Petridis constant, but the assertion is not proved 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.