Author: Haixiao Wang
As demonstrated in , expander graphs are a sparse graph that mimic the structure properties of complete graphs, quantified by vertex, edge or spectral expansion. At the same time, expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.
This lecture is organized as follows. We introduce two different definitions of expanders in the first section, and then explore the relationship between them in second part.
17.1. Two Definitions
We start our discussion in expansion with two definitions of expansion: combinatorial and spectral. In the rest of this post, we consider an undirected graph with
, where self loops and multiple edges are allowed. Given two subsets , the set of edges between and is denoted by .
17.1.1. Combinatorial expansion
Intuitively, a graph is an expander if subsets expand outwards into . In other words, all small subsets will have large boundary, respectively. Follow this intuition, we introduce the definition of boundary, based on edges and vertices respectively, to quantify the corresponding expansion.
- The Edge Boundary of a set , denoted by , is the set of edges , which is the set of edges between disjoint set and .
- The Vertex Boundary of a set is a subset of vertices in adjacent to vertices in , denoted as .
Obviously, vertex boundary is the same as the number of neighboring vertices of vertex sets . With those notations, we then define the expansion over the entire graph via maximizing over subsets .
Definition 2(Expander): For some , a graph with is an
- -edge-expander if .
- -vertex-expander if .
Remark 3: The reason for the restriction is that we are examining the relative size of every cut in the graph, i.e., the number of edges crossing between and , and we examine each case only once.
Problem 1: Show that the complete graph is
- at least a -edge-expander.
- a -vertex-expander. (We only consider here.)
From the definition above, the maximum , which makes an -edge-expander, is an important criteria, leading to the definition of Cheeger constant.
Definition 4(Cheeger Constant): The Edge Expansion Ratio, or Cheeger constant, of graph with , denoted by , is defined as
Remark 5: Actually, Cheeger constant can be defined alternatively as . We didn’t follow this definition since we want to keep .
17.1.2. Spectral Expansion
To simplify our discussion, we focus on regular graphs in the rest of this lecture. Let denote the adjacency Matrix of a -regular graph with and being real symmetric, then has real eigenvalues, denoted by , and corresponding orthonormal eigenvectors with . The spectrum of encodes a lot of information about the graph structure. Recall the following properties, which we have seen in previous lectures.
- The largest eigenvalue is and the corresponding eigenvector is .
- The graph is connected if and only if .
- The graph is bipartite if and only if .
The definition of spectral expansion and spectral gap then follows.
Definition 6(Spectral Expansion): A graph with is a -spectral-expander if .
In other words, the second largest eigenvalue of , in absolute value, is at most . This also gives rise to the definition of Ramanujan graph.
Definition 7(Ramanujan graph): A connected -regular graph is a Ramanujan graph if .
We now refer to the spectral gap.
Definition 8(Spectral Gap): The spectral gap of -regular graph is .
Remark 9: Sometimes the spectral gap is defined as , which is often referred as one-sided.
- Show that the complete graph has spectral gap . Actually, we can also show that the one-sided spectral gap is .
- Show that the complete bipartite graph has spectral gap . (Hint: use the spectral property above.)
17.2. Relating Two Definitions
It is not so obvious that the combinatorial and spectral versions of expansion are related. In this section, we will introduce two relations between edge and spectral expansion: the Expander-Mixing Lemma and Cheeger’s inequality.
17.2.1. The Expander-Mixing Lemma
Lemma 10(Expander-Mixing Lemma): Let be a -regular graph with vertices and eigenvalues . Then for all :
As we can see, the left-hand side measures the deviation between two quantities:
- : the number of edges between the two subsets and .
- : the expected number of edges between two subsets and , drawn from an Erdos–Renyi random graph .
The Expander-Mixing lemma tell us a small (a.k.a. large spectral gap) implies that this discrepancy is small, leading to the fact that the graph is nearly random in this sense, as discussed in . We should mention that the converse of expander-mixing is true as well, stated as follows.
Lemma 11(Expander-Mixing Lemma Converse ): Let be a -regular graph with vertices and eigenvalues satisfying:
for any two disjoint subsets and some positive . Then .
Proof of Expander-Mixing Lemma: Recall that the adjacency matrix has eigenvalues with corresponding orthonormal eigenvectors . Let and be the characteristic vectors of subsets and (a.k.a., the -th coordinate of is if and otherwise). We then decompose and in the orthonormal basis of eigenvectors as
Observing that , we expand out the right hand side and apply orthogonality, which yields
where the last step follows from the facts with corresponding , and . Shifting the first term on right hand side to the left, the desired result follows from Cauchy-Schwarz inequality:
Remark 12: If we normalize the adjacency matrix and obtain , where each entry of is divided by , then the corresponding eigenvalues of , namely , lie in the interval . The Expander-Mixing Lemma is in the form of
It is sometimes convenient to consider the normalized spectrum. For example in random graph theory, it would be convenient to look at the normalized spectrum when the expected degree . However, we can focus on the spectrum of $\latex A = A(G)$ without normalization when the expected degree $\latex d = O(1)$.
Regular -spectral expanders with small (a.k.a. large spectral gap) have some of significant properties, listed as follows.
Corollary 13: An independent set , in a graph with , is a set of vertices , where no two vertices in are adjacent, i.e. with . An independent set , in a -regular -spectral expander , has cardinality at most , i.e., , which follows immediately from Lemma 10(Expander-Mixing Lemma).
Corollary 14: Given a graph with , the diameter of is defined as , where is the length of shortest path between and . If is a -regular -spectral expander with , then we have
17.2.2. Cheeger’s Inequality
As we have seen from previous discussion, spectral expansion implies strong structural properties on the edge-structure of graphs. In this section, we introduce another famous result, Cheeger’s inequality, indicating that the Cheeger constant(Edge Expansion Ratio) of a graph can be approximated by the its spectral gap .
Theorem 15(Cheeger’s inequality, ): Let be a -regular graph with eigenvalues , then
In the normalized scenario with eigenvalues , we have
Remark 16: The proof for the normalized scenario is different from the regular scenario. We should start from the desired quantity and finish the calculation step by step. However, the strategy are the same. We use the Rayleigh Quotient to obtain upper bound and lower bound.
In the context of , the estimate of spectral gap was given by Nilli Alon.
Theorem 17(): For every -regular graph , we have
The term is a quantity that tends to zero for every fixed as .
. Shlomo Horry, N. L. and Wigderson, A. (2006). Expander graphs andtheir applications.BULLETIN (New Series) OF THE AMERICAN MATHEMATICAL SOCIETY, 43(4).. Alon, N. and Chung, F. R. K. (1988). Explicit construction of linear sized tolerantnetworks.Discrete Mathematics, 42 . Cheeger, J. (1970). A lower bound for the smallest eigenvalue of the laplacian.Problems inanalysis, 26.[Nilli, 1991] Nilli, A. (1991). On the secon. Yonatan Bilu, N. L. (2006). Lifts, discrepancy and nearly optimal spectral gap.Com-binatorica, 26. Nilli, A. (1991). On the second eigenvalue of a graph.Discrete Mathematics, 91(2):207–210.. Lovett, S. (2021). Lecture notes for expander graphs and high-dimensional expanders.