The Spectrum of Triangle-free Graphs
Date
2022
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
© 2022 The Authors
Authors
Person
Research Projects
Organizational Units
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Mathematics
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.
Comments
This preprint is made available throught arXiv at doi:https://doi.org/10.48550/arXiv.2204.00093. Posted with permission.
This work is licensed under the Creative Commons Attribution 4.0 License.