TY - JOUR
T1 - THE SPECTRUM OF TRIANGLE-FREE GRAPHS
AU - Balogh, József
AU - Clemen, Felix Christian
AU - Lidický, Bernard
AU - Norin, Sergey
AU - Volec, Jan
N1 - *Received by the editors July 6, 2022; accepted for publication (in revised form) January 5, 2023; published electronically June 20, 2023. https://doi.org/10.1137/22M150767X Funding: The first author's research is partially supported by NSF grants DMS-1764123, RTG DMS 1937241, and FRG DMS-2152488, by the Arnold O. Beckman Research Award (UIUC Campus Research Board RB 22000), by the Langan Scholar Fund (UIUC), and by the Simons Fellowship. The research of the third author is partially supported by NSF grants DMS-1855653 and FRG DMS-2152498, and by a Scott Hanna fellowship. The research of the fourth author was supported by an NSERC Discovery Grant. The research of the fifth author is partially supported by the Czech Science Foundation GACR,\\v grant 23-06815M. \\dagger Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA ([email protected], [email protected]). \\ddagger Department of Mathematics, Iowa State University, Ames, IA 50011 USA ([email protected]). \\S Department of Mathematics and Statistics, McGill University, Montreal, QC, H3A 2K6, Canada ([email protected]). \\P Department of Mathematics, Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University in Prague, Prague, Czech Republic ([email protected]).
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
KW - eigenvalues
KW - graph theory
KW - triangles
UR - http://www.scopus.com/inward/record.url?scp=85166022492&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85166022492&partnerID=8YFLogxK
U2 - 10.1137/22M150767X
DO - 10.1137/22M150767X
M3 - Article
AN - SCOPUS:85166022492
SN - 0895-4801
VL - 37
SP - 1173
EP - 1179
JO - SIAM Journal on Discrete Mathematics
JF - SIAM Journal on Discrete Mathematics
IS - 2
ER -