论文标题
无三角形图的光谱
The Spectrum of Triangle-free Graphs
论文作者
论文摘要
用$ q_n（g）$表示$ n $ vertex图$ g $的无价laplacian矩阵的最小特征值。布兰特（Brandt）在1997年猜想，对于常规三角形图，$ q_n（g）\ leq \ frac {4n} {25} $。我们证明了一个更强的结果：如果$ g $是三角形的图形，则$ q_n（g）\ leq \ frac {15n} {94} {94} <\ frac {4n} {25} $。布兰特的猜想是两个著名猜想的子问题： （1）稀疏的半个子注射器：每个$ n $ -vertex三角形的图形都有大小$ \ lceil \ lceil \ frac {n} {2} {2} \ rceil $跨度的顶点，最多$ n^2/50 $边缘。 （2）每$ n $ vertex三角形的图形都可以通过最多删除$ n^2/25 $边缘来制作双方。 在我们的证明中，我们使用线性代数方法将其与上限$ q_n（g）$按3和4个顶点的诱导路径数之间的比例。我们通过FLAG代数的方法给出了该比率的上限。
Denote by $q_n(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 $q_n(G) \leq \frac{4n}{25}$. We prove a stronger result: If $G$ is a triangle-free graph then $q_n(G) \leq \frac{15n}{94}< \frac{4n}{25}$. 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 $\lceil\frac{n}{2}\rceil$ spanning at most $n^2/50$ edges. (2) Every $n$-vertex triangle-free graph can be made bipartite by removing at most $n^2/25$ edges. In our proof we use linear algebraic methods to upper bound $q_n(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.
