The Spectrum of Triangle-free Graphs

Date
2022
Authors
Balogh, J´ozsef
Clemen, Felix Christian
Lidicky, Bernard
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
© 2022 The Authors
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
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.
Description
Keywords
Citation
DOI
Collections