The spectral norm of the infinite -regular tree is . We will see what this means and how to prove it.
When talking about the expansion of random graphs, abobut the construction of Ramanujan expanders, as well as about sparsifiers, community detection, and several other problems, the number comes up often, where is the degree of the graph, for reasons that tend to be related to properties of the infinite -regular tree.
If is a -regular graph, is its adjacency matrix and
are the eigenvalues of in non-increasing order, then a measure of the expansion of is the parameter
which is the second largest singular value of . One way to think about the above parameter is that the “best possible -regular expander,” if we allow weights, is the graph whose adjacency matrix is , where is the matrix with ones in every entry. The parameter measures the distance between and according to the spectral norm. (The spectral norm is a good one to consider when talking about graphs, because it bounds the cut norm, it is efficiently computable, and so on.)
If is -regular and bipartite, then and an appropriate measure of expansion is , which is just .
Nilli proved that, in a -regular graph, , where is the diameter of . Nilli’s construction is a variant of the way you prove that the spectral norm of the infinite tree is at least . Lubotzky, Phillips and Sarnak call a -regular graph Ramanujan if (or if in the case of bipartite graphs). So Ramanujan graphs are the best possible expanders from the point of view of the spectral definition.
Lubotzky, Phillips and Sarnak given an efficient construction of an infinite family of -regular Ramanujan graphs when is prime and , and this has been generalized by Morgenstern to all such that is a prime power.
Marcus, Spielman and Srivastava show the existence of infinitely many Ramanujan bipartite expanders for every degree. (For degree , their construction gives graphs with any number of nodes of the form .) Their proof uses the fact that the spectral norm of the infinite -regular tree is at most .
Friedman, in an outstanding tour the force, has given a 128-page proof of a conjecture of Alon, that a random -regular graph will satisfy, with high probability, . His paper is long, in part, because everything is explained very well. I am taking the analysis of the spectral norm of the infinite tree presented in this post from his paper.
(Notice that it is still an open question to construct, or even to prove the existence of, an infinite family of non-bipartite Ramanujan graphs of degree, say, , or to show, for any degree at all, (except 2!) that Ramanujan graphs of that degree exist for all number of vertices in a dense sets of integers.)
Now let’s talk about the spectrum of the infinite tree. First of all, although finite trees are terrible expanders, it is intuitive that an infinite tree is an excellent expander. For an infinite graph with a countable number of vertices and finite degree we can define the (non-normalized) expansion as
In a -regular infinite tree, the expansion is , because, if we take any set of vertices, there are at most edges in the subgraph induced by (because it’s a forest with vertices) and so there are at least edges leaving . It is easy to see that every other infinite -regular graph has expansion at most because, for every , we can run a DFS for steps starting from an arbitrary vertex until we either discover vertices reachable from (including ), or we find a connected component of size . In the former case, let be the vertices found by the DFS: the set induces a connected subgraph, so there are edges inside and edges leaving . In the latter case, the expansion is zero.
What about the spectral expansion of the infinite tree? If is a finite -regular graph, then the largest eigenvalue of its adjacency matrix is , and the corresponding eigenvector is the vector . By the spectral theorem we have
When we have an infinite -regular graph, the all-1 vector is not an eigenvector any more (because it has infinite norm), and the relevant quantity becomes the spectral norm
We will not need it, but I should remark that there is a Cheeger inequality for infinite graphs, which is actually slightly easier to prove than for finite graphs.
Since we want to prove that, for the infinite -regular tree we have , we need to argue that for every vector such that we have
If we fix a root , so that we can talk about the parent and the children of each node, and if we call the set of children of , then we want to show
Since we have an inequality with a summation on the left-hand-side and a square root on the right-hand-side, this looks like a job for Cauchy-Schwarz! The trick to get a one-line proof is to use the right way to break things up. One thing that comes to mind is to use , but this does not go anywhere, and it would give an upper bound of . This means that the bound is often loose, which must happen because and are often different in magnitude. To see why this should be the case, note that if we call , considering that there are vertices at distance from the root, the typical vertex at distance from the root satisfies , and we may think that if is a child of it should often be the case that is about a factor of smaller than . If that were the case, then a tighter form of Cauchy-Schwarz would be . Let us try that bound:
which works! To justify the identity in the middle line, note that, in the sum, the root appears times as a parent and never as a child, and every other vertex appears once as a child and times as a parent.
This proves that the spectral norm of the infinite -regular tree is at most . To prove that it is at least this much, for every we must find a vector such that
For such vectors, the Cauchy-Schwarz argument about is nearly tight, so it means that in such vectors, if is the parent of , then needs to be about times larger than . So let us start from this condition: we pick a vertex to be the root and we set , if is a child of we set , and if is at distance from the root we set . This means that if we sum over all the vertices at distance from the root we get , for all , which means that . So let us cut off the construction at some distance , so that is defined as follows:
- if is at distance from and
- if is at distance from .
We immediately see
Then we do the calculations and we see that
so, for every , we can construct a vector such that
and we are done!