The Spectrum of Triangle-Free Graphs
Date
2023-06
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Society for Industrial and Applied Mathematics
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) \leq 4n
25 . We prove a stronger result: If G is a triangle-free graph, then qn(G) \leq 15n 94 < 4n 25 . Brandt's conjecture is a subproblem of two famous conjectures of Erd\H os: (1) Sparse-half-conjecture: Every n-vertex triangle-free graph has a subset of vertices of size \lceil n 2 \rceil 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.
Series Number
Journal Issue
Is Version Of
Versions
Preprint
The Spectrum of Triangle-free Graphs
(
2023-01-04)
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:
(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.
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.
(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.
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.
Series
Academic or Administrative Unit
Type
article
Comments
This article is published as Balogh, József, Felix Christian Clemen, Bernard Lidický, Sergey Norin, and Jan Volec. "The spectrum of triangle-free graphs." SIAM Journal on Discrete Mathematics 37, no. 2 (2023): 1173-1179. https://doi.org/10.1137/22M150767X. Posted with permission.
Rights Statement
© 2023 Society for Industrial and Applied Mathematics