The Spectrum of Triangle-free Graphs
Clemen, Felix Christian
© 2022 The Authors
Is Version Of
We prove a conjecture by Brandt from 1997 on the spectrum of triangle-free graphs: Given an n-vertex graph G, let λn≤…≤λ1 be the eigenvalues of the adjacency matrix of G. Every regular triangle-free n-vertex graph G satisfies λ1+λn≤4n/25. This is a subproblem of two famous conjectures by Erdős. (1) Sparse-Half-Conjecture: Every n-vertex triangle-free graph has a subset of vertices of size ⌈n2⌉ spanning at most n2/50 edges. (2) Every n-vertex triangle-free graph can be made bipartite by removing at most n2/25 edges. Among others we use improved bounds on the number of C4's in triangle-free graphs, which are obtained via the method of flag algebras.
This preprint is made available throught arXiv at doi:https://doi.org/10.48550/arXiv.2204.00093. Posted with permission. This work is licensed under the Creative Commons Attribution 4.0 License.