HEXAGONbeta

Three conjectures on the first two graph eigenvalues

A mix of human-written and AI-generated textHuman understanding: all partsmath.CO — Combinatorics

Contributed by Idris Ali Shaik ↗

Version 1 / Oct 17, 2026 / CC BY 4.0

Abstract

Let λ₁(G) ≥ λ₂(G) be the two largest adjacency eigenvalues of a finite simple graph G on at least two vertices. We resolve the three conjectures appearing as 1.15–1.17 in Kannan, Kumar and Pragada. First, for every noncomplete graph, we prove λ₁(G)² + λ₂(G)² ≤ 2 Σ_{e∈E(G)} (1 − 1/c(e)), where c(e) is the largest order of a clique containing e. Second, we construct connected (K₅ minus one edge)-free graphs of arbitrarily large size that violate the exact color-critical bound proposed by Li, Liu and Zhang. Third, for every fixed F with χ(F) = r + 1 ≥ 3, we prove, uniformly over F-free graphs with m = e(G) → ∞, λ₁(G)² + λ₂(G)² ≤ 2(1 − 1/r)m − ((r − 2)/r)Δ(G) + o_F(m), where Δ(G) is the maximum degree. The coefficient of the degree term is best possible. The arguments use the half-plane complete-positivity theorem of Coutinho, Liu, Spier, Tang and Zhang, together with an explicit connected construction, weighted clique removal and spectral separation of vertices of high degree. Theorems 1.1–1.3 are formalized in Lean 4 and registered as PALOMAR-2026-10-15-000015 v1, PALOMAR-2026-10-16-000012 v1 and PALOMAR-2026-10-17-000005 v1, respectively.

Provenance statement

OpenAI ChatGPT and Codex assisted with mathematical exploration, Lean formalization, manuscript preparation and review. The author reviewed the AI-assisted material and takes full responsibility for the manuscript.

Formalizations

References

  1. B. Bollobás and V. Nikiforov, Cliques and the spectral radius, J. Combin. Theory Ser. B 97 (2007), 859--865. doi:10.1016/j.jctb.2006.12.002 (https://doi.org/10.1016/j.jctb.2006.12.002).DOI
  2. D. Bradač, A generalization of Turán's theorem, arXiv:2205.08923 (2022). https://arxiv.org/abs/2205.08923.arXiv
  3. D. Conlon and J. Fox, Graph removal lemmas, arXiv:1211.3487 (2012). https://arxiv.org/abs/1211.3487.arXiv
  4. G. Coutinho, Y. Liu, T. J. Spier, Q. Tang and S. Zhang, The Bollobás--Nikiforov inequality for nonnegative edge weights, repository manuscript, fixed source version. https://github.com/ShengtongZhang-alt/BN/blob/5f4741254398424b730c9a893220a51e1cd829c5/docs/sol.tex.link
  5. A. Jayarajan, M. R. Kannan, S. Pragada and R. Roy, A vertex-localized positive square-energy strengthening of Turán's theorem, arXiv:2608.24861v2 (2026). https://arxiv.org/abs/2608.24861v2.arXiv
  6. M. R. Kannan, H. Kumar and S. Pragada, Localization of spectral Turán-type theorems, arXiv:2512.01409v2. https://arxiv.org/abs/2512.01409v2.arXiv
  7. H. Kumar and S. Pragada, Bollobás--Nikiforov conjecture for graphs with not so many triangles, Linear Algebra Appl. 727 (2025), 1--9. doi:10.1016/j.laa.2025.07.035 (https://doi.org/10.1016/j.laa.2025.07.035).DOI
  8. H. Lin, B. Ning and B. Wu, Eigenvalues and triangles in graphs, Combin. Probab. Comput. 30 (2021), 258--270. doi:10.1017/S0963548320000462 (https://doi.org/10.1017/S0963548320000462).DOI
  9. S. Zhang, On the first two eigenvalues of regular graphs, Linear Algebra Appl. 686 (2024), 102--110. doi:10.1016/j.laa.2024.01.002 (https://doi.org/10.1016/j.laa.2024.01.002).DOI
  10. G. Coutinho, T. J. Spier and S. Zhang, Conic programming to understand sums of squares of eigenvalues of graphs, arXiv:2411.08184v1 (2024). https://arxiv.org/abs/2411.08184v1.arXiv
Show all 20 referencesShow fewer references
  1. D. Malec and C. Tompkins, Localized versions of extremal problems, European J. Combin. 112 (2023), Article 103715. doi:10.1016/j.ejc.2023.103715 (https://doi.org/10.1016/j.ejc.2023.103715).DOI
  2. Y. Li, H. Liu and S. Zhang, An edge-spectral Erdős--Stone--Simonovits theorem and its stability, arXiv:2508.15271v2 (2026). https://arxiv.org/abs/2508.15271v2.arXiv
  3. F. Liu, S. Sun, Y. Wang and Q. Wu, Local Turán inequalities for walks and the spectral radius, arXiv:2605.02191v2 (2026). https://arxiv.org/abs/2605.02191v2.arXiv
  4. Y. Li, An entropy bridge from weighted to spectral Turán theorems, arXiv:2608.24388v2 (2026). https://arxiv.org/abs/2608.24388v2.arXiv
  5. Y. Li, H. Liu and S. Zhang, Edge-spectral Turán theorems for color-critical graphs with applications, arXiv:2511.15431v3 (2026), accepted for publication in SIAM J. Discrete Math. https://arxiv.org/abs/2511.15431v3.arXiv
  6. L. Liu and B. Ning, Local properties of the spectral radius and Perron vector in graphs, J. Combin. Theory Ser. B 176 (2026), 241--253. doi:10.1016/j.jctb.2025.09.001 (https://doi.org/10.1016/j.jctb.2025.09.001).DOI
  7. L. Liu and B. Ning, A new spectral Turán theorem for weighted graphs and consequences, arXiv:2510.26410v1 (2025). https://arxiv.org/abs/2510.26410v1.arXiv
  8. I. A. Shaik, Localized two-eigenvalue bound for finite noncomplete graphs, Palomar, PALOMAR-2026-10-15-000015 v1 (2026). https://palomar-registry.org/entry?id=PALOMAR-2026-10-15-000015&version=1.link
  9. I. A. Shaik, Connected counterexamples to the exact color-critical two-eigenvalue bound, Palomar, PALOMAR-2026-10-16-000012 v1 (2026). https://palomar-registry.org/entry?id=PALOMAR-2026-10-16-000012&version=1.link
  10. I. A. Shaik, A sharp asymptotic spectral bound for forbidden subgraphs, Palomar, PALOMAR-2026-10-17-000005 v1 (2026). https://palomar-registry.org/entry?id=PALOMAR-2026-10-17-000005&version=1.link

Version history

  1. v1Submitted by Idris Ali ShaikInitial depositCurrentOct 17, 2026