Asymptotic order conjecture for the clique ratio of regular graphs with bounded smallest eigenvalue

For an integer λ2\lambda\geq 2, let γ(λ)\gamma(\lambda) be the limiting infimum of ω(G)/k\omega(G)/k as kk tends to infinity over connected kk-regular graphs GG with smallest eigenvalue at least λ-\lambda, where ω(G)\omega(G) is the clique number of GG:

γ(λ):=limkinf{ω(G)kG is a connected k-regular graph and λmin(G)λ}.\gamma(\lambda):=\lim_{k\to\infty}\inf\left\{\frac{\omega(G)}{k}\mid G\text{ is a connected }k\text{-regular graph and }\lambda_{\min}(G)\geq-\lambda\right\}.

Asymptotic clique-ratio conjecture. There exist positive constants ε1\varepsilon_1 and ε2\varepsilon_2 such that

ε1λ2γ(λ)ε2λ2\frac{\varepsilon_1}{\lambda^2}\leq\gamma(\lambda)\leq\frac{\varepsilon_2}{\lambda^2}

holds for every integer λ\lambda. The preceding bounds show that the authors seek to improve their lower bound, while Hamming graphs provide an upper bound of order 1/λ1/\lambda; the conjecture predicts the sharper order 1/λ21/\lambda^2.

Sources & referencesView supporting material

Primary source

Qianqian Yang and Jack H. Koolen, “A structure theory for regular graphs with fixed smallest eigenvalue”, arXiv:2401.10468 (2024).

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.