The Spectrum of Triangle-free Graphs

Abstract

Denote by qn(G) the smallest eigenvalue of the signless Laplacian matrix of an n-vertex graph G. Brandt conjectured in 1997 that for regular triangle-free graphs qn(G) ≤ 4n25. We prove a stronger result: If G is a triangle-free graph then qn(G) ≤ 15n94 < 4n25. Brandt's conjecture is a subproblem of two famous conjectures of Erdős:<br/>(1) Sparse-Half-Conjecture: Every n-vertex triangle-free graph has a subset of vertices of size ⌈n2⌉ spanning at most n2/50 edges.<br/>(2) Every n-vertex triangle-free graph can be made bipartite by removing at most n2/25 edges.<br/> In our proof we use linear algebraic methods to upper bound qn(G) by the ratio between the number of induced paths with 3 and 4 vertices. We give an upper bound on this ratio via the method of flag algebras.