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

At least 1 year old · documented by

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:

γ(λ):=lim⁡k→∞inf⁡{ω(G)k∣G 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.

References

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.