A graph can be viewed through two distinct lenses: its combinatorial structure (the arrangement of cliques, independent sets, and paths) and its algebraic spectrum (the eigenvalues of its associated matrices). The central insight unifying this field is that these two domains constrain each other tightly. A graph cannot possess a large independent set or a specific matching number without forcing its eigenvalues into specific ranges; conversely, the distribution of its eigenvalues dictates how its subgraphs can be arranged.
Interlacing and Structural Thresholds
How does local structure dictate global eigenvalues? A primary tool is the Cauchy Interlacing Theorem, which states that the eigenvalues of a principal submatrix interlace the eigenvalues of the larger matrix. In graph theory, a principal submatrix corresponds exactly to an induced subgraph.
In two closely related papers, Nonpositive eigenvalues of the adjacency matrix and lower bounds for Laplacian eigenvalues and Nonpositive Eigenvalues of Hollow, Symmetric, Nonnegative Matrices, Charles et al. explore this via the concept of $NPO(k)$—the minimum number of vertices a graph must have to guarantee that its adjacency matrix has at least $k$ nonpositive eigenvalues. The authors show that as a graph grows, the unavoidable emergence of either large independent sets or complete subgraphs (a direct consequence of Ramsey theory) forces the appearance of nonpositive eigenvalues. By constructing extreme configurations like the "W-graph," they demonstrate that the vertex threshold required to guarantee $k$ nonpositive eigenvalues grows quadratically, specifically exceeding the $k$-th triangular number $\frac{k(k+1)}{2}$.
This structural constraint via interlacing is a universal theme. For instance, in Hermitian adjacency matrices with at most three distinct eigenvalues, Akbari et al. utilize the interlacing theorem for Hermitian matrices to completely characterize oriented and mixed graphs with highly restricted spectra, demonstrating how tightly bounded eigenvalue counts restrict permissible local subgraphs.
Bounding Combinatorial Counts via Spectral Gaps
While interlacing shows how subgraphs force eigenvalues, we can also reverse the perspective: how do eigenvalues limit the number or size of specific subgraphs?
Consider independent sets. If a graph is highly connected and expands well, it cannot contain massive independent sets. This intuition is formalized by bounding independent sets using the ratio of a graph's smallest eigenvalue to its degree. In Counting sum-free sets in Abelian groups, Balogh et al. leverage this spectral connection to bound the number of independent sets of a specific size in regular graphs. This spectral bound serves as a critical step in their proof to count sparse sum-free sets in Abelian groups, showing that a significant spectral gap tightly constrains combinatorial independence.
Similarly, spectral properties can bound more complex distance-based invariants. In The clique number of the exact distance t-power graph: Complexity and eigenvalue bounds, Abiad et al. study the "t-equidistant number"—the size of the largest vertex set where every pair is at distance exactly $t$. By analyzing the eigenvalues of the graph's distance matrix rather than just the standard adjacency matrix, the authors derive bounds that outperform classical methods, showing that distance spectra provide a direct geometric constraint on how far apart large sets of vertices can be distributed.
Extremal Spectral Radius under Structural Constraints
Another major facet of this research direction is determining the maximum or minimum spectral radius ($\lambda_1$) when certain structural invariants are held constant. The spectral radius measures a graph's overall connectivity and density; thus, restricting invariants like the clique number, matching number, or dissociation number places a strict upper bound on how large $\lambda_1$ can grow.
In A homogeneous polynomial associated with general hypergraphs and its applications, Hou et al. extend this to hypergraphs. By defining a novel homogeneous polynomial and applying Maclaurin's and Cauchy-Schwarz inequalities, the authors derive tight upper and lower bounds on the spectral radius of uniform hypergraphs in terms of their clique number.
For standard graphs, structural parameters like the dissociation number (the size of the largest induced subgraph with maximum degree 1) or the matching number act as similar bottlenecks. In Maximization of the spectral radius of block graphs with a given dissociation number, Das et al. analyze block graphs and bound the spectral radius by analyzing the roots of quadratic approximations of the graph's characteristic polynomials. Similarly, in The maximum Aα-spectral radius of t-connected graphs with bounded matching number, Liu et al. use the Rayleigh-Ritz theorem to bound the generalized $A_\alpha$-spectral radius, providing precise characterizations of the exact extremal graphs that maximize this spectral radius under connectivity and matching constraints.
Walks, Tensors, and Measure-Theoretic Frameworks
To deepen the intuition of why these bounds work, we must look at the relationship between eigenvalues and graph walks. The $k$-th closed walk count of a graph is exactly equal to the $k$-th moment of its spectral measure (i.e., $\sum \lambda_i^k$).
In Measure-theoretic bounds on the spectral radius of graphs from walks, Barreras et al. formalize this by applying the classical moment problem from measure theory. By treating walk counts as moments, the authors constrain the support of the spectral measure, yielding a systematic hierarchy of lower and upper bounds on the spectral radius. This explains why walk-counting methods work: they are implicitly reconstructing the boundaries of the graph's spectrum from local path combinations.
This walk-counting intuition extends to more sophisticated matrices and higher-order structures:
- Non-Backtracking Matrices: In Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs, Bordenave et al. utilize path counting on non-backtracking walks to establish norm bounds on random graph matrices. Eliminating immediate backtracking prevents the spectral radius from being artificially inflated by high-degree vertices, revealing the true underlying community structure.
- Hypergraph Tensors: In Estrada index and subgraph centrality of hypergraphs via tensors, Sun et al. extend walk-based indices (like the Estrada index, which sums $e^{\lambda_i}$) to uniform hypergraphs using adjacency tensors. They show that spectral symmetry in these tensors dictates bounds on subgraph centrality, mapping the density of local hypergraph structures directly onto global tensor eigenvalues.
By translating structural constraints into algebraic inequalities, this body of work demonstrates that a graph's combinatorial geometry and its matrix spectrum are fundamentally inseparable.
Key Foundational Work
Nonpositive eigenvalues of the adjacency matrix and lower bounds for Laplacian eigenvalues (2013) — contributed 7 concept elements to this direction.
Nonpositive Eigenvalues of Hollow, Symmetric, Nonnegative Matrices (2013) — contributed 4 concept elements to this direction.
Counting sum-free sets in Abelian groups (2012) — contributed 2 concept elements to this direction.