Understanding the Basics: Adjacency Matrices and Eigenvalues

At the heart of our exploration lies the adjacency matrix ( A ) of a graph ( G = (V, E) ). For a ( d )-regular graph with ( n ) vertices, the eigenvalues of ( A ) are ordered as follows:

[ d = \lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n \geq -d. ]

The maximum spectral radius, denoted ( \lambda ), is defined as:

[ \lambda = \max{|\lambda_2|, |\lambda_n|}, ]

which allows us to examine the behavior of the graph in relation to its connectivity. The significance of these eigenvalues extends beyond mere numbers; they provide insights into the graph's expansion properties and mixing times.

The Quadratic Form Identity: A Key Insight

One of the fundamental results in graph theory is the quadratic form identity. For any vector ( x \in \mathbb{R}^n ), the following holds:

[ x^\top A x = \sum_{(u, v) \in E} 2 x_u x_v. ]

This identity reveals that the quadratic form of the adjacency matrix can be expressed as a sum over the edges of the graph. This relationship allows us to connect algebraic properties with combinatorial structures, highlighting how the values of ( x ) at different vertices interact based on the edges that connect them.

Edge Distribution and Indicator Vectors

Building upon the quadratic form identity, we can derive a powerful result concerning edge distribution. For a vertex subset ( S \subseteq V ), we denote the number of edges with both endpoints in ( S ) as ( e(S, S) ). Using the indicator vector ( 1_S ) of the set ( S ), we find that:

[ e(S, S) = \frac{1}{2} 1_S^\top A 1_S. ]

This equation succinctly captures the essence of edge distribution within a subset, allowing us to quantify how densely connected the vertices in ( S ) are. It emphasizes the importance of understanding the relationships between vertices in the context of the overall graph structure.