THE SPECTRUM OF TRIANGLE-FREE GRAPHS

József Balogh, Felix Christian Clemen, Bernard Lidický, Sergey Norin, Jan Volec

Research output: Contribution to journalArticlepeer-review

Abstract

Denote by qn(G) the smallest eigenvalue of the signless Laplacian matrix of an nvertex graph G. Brandt conjectured in 1997 that for regular triangle-free graphs qn(G) ≤ 4n/25 . We prove a stronger result: If G is a triangle-free graph, then qn(G) ≤ 15n/94 < 4n/25 . Brandt's conjecture is a subproblem of two famous conjectures of Erdos: (1) Sparse-half-conjecture: Every n-vertex triangle-free graph has a subset of vertices of size [n/2] spanning at most n2/50 edges. (2) Every n-vertex triangle-free graph can be made bipartite by removing at most n2/25 edges. 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.

Original languageEnglish (US)
Pages (from-to)1173-1179
Number of pages7
JournalSIAM Journal on Discrete Mathematics
Volume37
Issue number2
DOIs
StatePublished - 2023

Keywords

  • eigenvalues
  • graph theory
  • triangles

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'THE SPECTRUM OF TRIANGLE-FREE GRAPHS'. Together they form a unique fingerprint.

Cite this