Eigenvalues and triangles in graphs

Basic Information

• Paper ID: 1910.12474
• Title: Eigenvalues and triangles in graphs
• Authors: Huiqiu Lin, Bo Ning, Baoyindureng Wu
• Classification: math.CO (Combinatorics)
• Publication Date: July 18, 2020 (arXiv v3)
• Paper Link: https://arxiv.org/abs/1910.12474

Abstract

This paper investigates the relationship between eigenvalues of graphs and triangle structures. The authors confirm the correctness of the Bollobás-Nikiforov conjecture for $r=2$ (triangle-free graphs), proving that for a triangle-free graph $G$, $\lambda_1^2(G) + \lambda_2^2(G) \leq m$, and completely characterize the extremal graph families achieving equality. Furthermore, inspired by classical theorems of Erdős and Nosal, the authors establish two spectral conditions for non-bipartite graphs containing triangles, both of which are optimal.

Research Background and Motivation

1. Core Problem: Investigating the relationship between the spectral radius (largest eigenvalue) of graphs and graph structural parameters (such as clique number and edge count), particularly how eigenvalues characterize the existence of triangles in graphs.
2. Problem Significance:
   • Spectral graph theory is an important branch of combinatorics with broad applications in network analysis, quantum chemistry, and other fields
   • Eigenvalues can reveal structural properties of graphs, such as connectivity, regularity, and diameter
   • Triangles are the most fundamental cycle structures in graphs, and their existence is closely related to graph complexity
3. Limitations of Existing Methods:
   • The Bollobás-Nikiforov conjecture, proposed in 2007, has remained unsolved for the general case
   • Classical Turán-type theorems primarily focus on the relationship between edge count and forbidden subgraphs, while spectral methods provide finer characterizations
4. Research Motivation:
   • Resolve the special case of the long-standing Bollobás-Nikiforov conjecture
   • Establish deep connections between spectral graph theory and extremal graph theory
   • Provide spectral analogs of classical theorems by Erdős and Nosal

Core Contributions

1. Proved the Bollobás-Nikiforov conjecture for $r=2$: For triangle-free graphs $G$, proved $\lambda_1^2 + \lambda_2^2 \leq m$ and completely characterized the extremal graph families.
2. Established novel applications of doubly stochastic matrix theory: Innovatively employed doubly stochastic matrix theory and weak majorization to handle eigenvalue inequality problems.
3. Proved two spectral theorems on triangle existence:
   • If $\lambda_1(G) \geq \sqrt{m-1}$ and $G \neq C_5 \cup (n-5)K_1$, then non-bipartite graph $G$ contains a triangle
   • Analogous results based on vertex count
4. Provided complete characterization of extremal graphs: Not only proved the inequalities but also completely determined the structure of all graphs achieving equality.

Methodology Details

Problem Definition

Study graphs $G$ with no $K_{r+1}$ subgraph, where $\lambda_1(G) \geq \lambda_2(G) \geq \cdots \geq \lambda_n(G)$ are eigenvalues of the adjacency matrix $A(G)$. The goal is to establish the relationship between $\lambda_1^2 + \lambda_2^2$ and edge count $m$.

Core Technical Methods

1. Doubly Stochastic Matrix Theory Approach

Key Lemma (Theorem 2.6): Let $x, y \in \mathbb{R}_+^n$ be arranged in non-increasing order. If $y \prec_w x$ (weak majorization), then for $p > 1$, $\|y\|_p \leq \|x\|_p$, with equality if and only if $x = y$.

Proof Strategy:

• Utilize convex combination representation of doubly stochastic matrices: $A = \sum_{i=1}^s a_i P_i$, where $P_i$ are weak permutation matrices
• Apply multiple Minkowski inequalities to control $\ell_p$ norms
• Determine extremal cases through analysis of equality conditions

2. Main Theorem Proof Strategy (Theorem 1.2)

Given graph $G$ with inertia $(n_+, n_-, n_0)$, construct vectors:

• $x = (\lambda_1^2, \lambda_2^2, 0, \ldots, 0)^T$
• $y = (\lambda_n^2, \lambda_{n-1}^2, \ldots, \lambda_{n-n_-+1}^2)^T$

Key Steps:

1. Assume $\lambda_1^2 + \lambda_2^2 > m$, then $y \prec_w x$ and $x \neq y$
2. Apply Theorem 2.6 to obtain $\|x\|_{3/2} > \|y\|_{3/2}$
3. This leads to $t(G) = \frac{\sum \lambda_i^3}{6} > 0$, contradicting triangle-freeness
4. Equality cases are determined through inertia analysis and graph rank theory to identify extremal structures

3. Triangle Existence Theorem Proof

Proof Strategy for Theorem 1.3:

• Proof by contradiction: assume non-bipartite graph $G$ is triangle-free
• Analyze the length of shortest odd cycles, proving it must be 5
• Utilize graph connectivity and degree constraints to derive contradiction
• Handle the special case of $C_5$ separately

Technical Innovations

1. Novel application of doubly stochastic matrix theory: First systematic application of weak majorization and doubly stochastic matrix theory to spectral extremal problems in graphs.
2. Connection between inertia and graph structure: Cleverly link graph spectral inertia with structural properties (such as rank and bipartiteness).
3. Multi-level extremal analysis: Not only prove tightness of bounds but also completely characterize structural features of extremal graphs.

Experimental Setup

This is pure theoretical research with no numerical experiments. All results are obtained through rigorous mathematical proofs.

Verification Methods

• Verify theorem tightness through concrete extremal graph examples
• Validate reasoning correctness using known spectral properties
• Compare with related results in existing literature

Extremal Graph Examples

• $P_2 \cup K_1$: one edge plus an isolated vertex
• $2P_2 \cup K_1$: two disjoint edges plus an isolated vertex
• $P_4 \cup K_1$: path of length 3 plus an isolated vertex
• $P_5 \cup K_1$: path of length 4 plus an isolated vertex

Experimental Results

Main Results

Theorem 1.2 (Main Result): Let $G$ be a triangle-free graph with at least 3 vertices and $m$ edges. Then: $\lambda_1^2 + \lambda_2^2 \leq m$ Equality holds if and only if $G$ is a blow-up of some graph in $\mathcal{G} = \{P_2 \cup K_1, 2P_2 \cup K_1, P_4 \cup K_1, P_5 \cup K_1\}$.

Theorem 1.3: Let $G$ be a non-bipartite graph with $m$ edges. If $\lambda_1 \geq \sqrt{m-1}$, then $G$ contains a triangle, unless $G = C_5 \cup (n-5)K_1$.

Theorem 1.4: Let $G$ be a non-bipartite graph of order $n$. If $\lambda_1 \geq \lambda_1(S(K_{\lfloor\frac{n-1}{2}\rfloor,\lceil\frac{n-1}{2}\rceil}))$, then $G$ contains a triangle, unless $G \cong S(K_{\lfloor\frac{n-1}{2}\rfloor,\lceil\frac{n-1}{2}\rceil})$.

Theoretical Significance

1. Improved Nosal's theorem: Nosal proved that triangle-free graphs $G$ satisfy $\lambda_1 \leq \sqrt{m}$. This paper provides stronger characterization based on the sum of squares of the first two eigenvalues.
2. Generalized spectral version of Mantel's theorem: Extended from single eigenvalue to sum of squares of two eigenvalues.
3. Established new spectral-structure correspondence: Completely characterized extremal graph structures achieving the bounds.

Related Work

Historical Development

1. Classical Extremal Graph Theory:
   • Turán's theorem (1941): Maximum edge count in $K_r$-free graphs
   • Mantel's theorem: Edge bound for triangle-free graphs $m \leq \lfloor n^2/4 \rfloor$
2. Spectral Graph Theory Development:
   • Wilf's inequality (1986): $\lambda_1 \leq \frac{\omega-1}{\omega}n$
   • Nikiforov's inequality (2002): $\lambda_1 \leq \sqrt{\frac{2(\omega-1)m}{\omega}}$
3. Spectral Extremal Graph Theory:
   • Stanley bound (1987): $\lambda_1 \leq \frac{1}{2}(\sqrt{8m+1}-1)$
   • Nosal's theorem (1970): $\lambda_1 \leq \sqrt{m}$ for triangle-free graphs

Relationship to Related Work

1. Direct generalization: This paper resolves the special case of the Bollobás-Nikiforov conjecture, which generalizes Nikiforov's inequality.
2. Methodological innovation: Introduces doubly stochastic matrix theory, providing new analytical tools for spectral extremal problems.
3. Result deepening: Not only proves existence of bounds but also completely characterizes extremal graph structures.

Conclusions and Discussion

Main Conclusions

1. Completely resolved the triangle case: Confirmed the correctness of the Bollobás-Nikiforov conjecture for $r=2$ and provided complete characterization of extremal graphs.
2. Established new analytical framework: Doubly stochastic matrix theory provides effective tools for handling joint constraints on multiple eigenvalues.
3. Generalized classical theorems: Provided spectral theory versions of classical results by Erdős and Nosal.

Limitations

1. Scope of applicability: The doubly stochastic matrix method primarily applies to the first few eigenvalues; larger values of $r$ may require new techniques.
2. Complexity of extremal graphs: As $r$ increases, the structure of extremal graphs may become more complex and difficult to completely characterize.
3. Computational complexity: For practical applications, the computational complexity of eigenvalue calculation may limit the method's applicability.

Future Directions

The paper raises several important open problems:

1. General Bollobás-Nikiforov conjecture: The case $r \geq 3$ remains open.
2. Generalization to odd girth: Study spectral properties of graphs with odd girth at least $2k+3$.
3. Constraints on more eigenvalues: Consider constraints on $s_+(G) = \sum \lambda_i^2$ (sum of squares of positive eigenvalues).
4. Computational complexity: Investigate computational complexity of related decision problems.

In-Depth Evaluation

Strengths

1. Significant theoretical contribution: Resolves an important long-standing open problem in combinatorics.
2. Innovative methodology: The application of doubly stochastic matrix theory to spectral extremal graph problems is novel, providing new analytical tools for the field.
3. Complete and profound results: Not only proves main inequalities but completely characterizes extremal cases, demonstrating deep mathematical insight.
4. Elegant proof techniques: Skillfully combines abstract matrix theory with concrete graph structures, with very refined technical handling.
5. Clear and rigorous exposition: Well-structured paper with clear proof steps, easy to understand and verify.

Weaknesses

1. Limited scope of applicability: Current methods primarily apply to the $r=2$ case; lack effective treatment for general $r$ values.
2. Practical applicability: As a pure theoretical result, its value in practical applications such as network analysis remains to be explored.
3. Computational aspects: The paper does not discuss computational complexity and implementation issues of related algorithms.

Impact

1. Academic value: Provides important theoretical progress for spectral extremal graph theory, expected to stimulate subsequent research.
2. Methodological contribution: The doubly stochastic matrix method may find applications in other related problems.
3. Citation potential: As work resolving an important conjecture, expected to receive high citation count.

Application Scenarios

1. Theoretical research: Provides new tools and results for research in spectral graph theory and extremal combinatorics.
2. Network analysis: May provide theoretical foundation for spectral characterization of triangle structures in complex networks.
3. Algorithm design: Provides theoretical support for designing graph algorithms based on spectral methods.

References

The paper cites 40 important references, primarily including:

• Bollobás & Nikiforov (2007): Original conjecture proposal
• Nosal (1970): Classical spectral-triangle theorem
• Nikiforov (2002): Spectral Turán theorem
• Zhan (2013): Systematic exposition of doubly stochastic matrix theory
• Andrásfai, Erdős & Sós (1974): Classical results on girth and minimum degree

This paper makes important contributions to spectral graph theory, not only resolving a long-standing open problem but also introducing new analytical tools to the field. While current results are primarily limited to the triangle case, the established methodological framework provides a solid foundation for further research.