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!
Most results in spectral graph theory seem to rely on the gap between the largest eingenvalue and the second largest (in absolute value).
Do you know any result where one needs to go beyond the the second largest eigenvalue and look also for instance at the 3rd largest?
Pingback: The Alon-Boppana Theorem | in theory
Pingback: Random 3-regular graphs | Eventually Almost Everywhere