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

About 3 years old · traced to

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.

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.