The Spectrum of Triangle-free Graphs

Abstract

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.