The Spectrum of Triangle-free Graphs
Date
2023-01-04
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
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:
(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 Number
Journal Issue
Is Version Of
Article
The Spectrum of Triangle-Free Graphs
(Society for Industrial and Applied Mathematics,
2023-06)
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.
Versions
Series
Academic or Administrative Unit
Type
Preprint
Comments
This preprint is made available through arXiv at doi:https://doi.org/10.48550/arXiv.2204.00093.
Rights Statement
This work is licensed under the Creative Commons Attribution 4.0 License.