The spectrum of the infinite tree

The spectral norm of the infinite ${d}$ -regular tree is ${2 \sqrt {d-1}}$ . 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 ${2 \sqrt{d-1}}$ comes up often, where ${d}$ is the degree of the graph, for reasons that tend to be related to properties of the infinite ${d}$ -regular tree.

If ${G}$ is a ${d}$ -regular graph, ${A}$ is its adjacency matrix and

$\displaystyle d = \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n \geq -d$

are the eigenvalues of ${A}$ in non-increasing order, then a measure of the expansion of ${G}$ is the parameter

$\displaystyle \sigma_2 = \max_{i=2,\ldots,n} \ | \lambda_i | = \max \{ | \lambda_2 | , | \lambda_n| \}$

which is the second largest singular value of ${A}$ . One way to think about the above parameter is that the “best possible ${d}$ -regular expander,” if we allow weights, is the graph whose adjacency matrix is ${\frac dn J}$ , where ${J}$ is the matrix with ones in every entry. The parameter ${\sigma_2}$ measures the distance between ${A}$ and ${\frac dn J}$ 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 ${G}$ is ${d}$ -regular and bipartite, then ${\lambda_n = -d}$ and an appropriate measure of expansion is ${\max_{i=2,\ldots,n-1} |\lambda_i|}$ , which is just ${\lambda_2}$ .

Nilli proved that, in a ${d}$ -regular graph, ${\lambda_2 \geq 2 \sqrt{d-1} - O( \sqrt d / diam(G))}$ , where ${diam(G) \geq \log_d n}$ is the diameter of ${G}$ . Nilli’s construction is a variant of the way you prove that the spectral norm of the infinite tree is at least ${2\sqrt {d-1}}$ . Lubotzky, Phillips and Sarnak call a ${d}$ -regular graph Ramanujan if ${\sigma_2 \leq 2 \sqrt {d-1}}$ (or if ${\lambda_2 \leq 2 \sqrt{d-1}}$ 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 ${d}$ -regular Ramanujan graphs when ${d-1}$ is prime and ${d-1 \equiv 1 \pmod 4}$ , and this has been generalized by Morgenstern to all ${d}$ such that ${d-1}$ is a prime power.

Marcus, Spielman and Srivastava show the existence of infinitely many Ramanujan bipartite expanders for every degree. (For degree ${d}$ , their construction gives graphs with any number of nodes of the form ${d \cdot 2^k}$ .) Their proof uses the fact that the spectral norm of the infinite ${d}$ -regular tree is at most ${2 \sqrt {d-1}}$ .

Friedman, in an outstanding tour the force, has given a 128-page proof of a conjecture of Alon, that a random ${d}$ -regular graph will satisfy, with high probability, ${\sigma_2 \leq 2 \sqrt {d -1} + o_n(1)}$ . 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, ${d=7}$ , 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 ${G=(V,E)}$ with a countable number of vertices and finite degree we can define the (non-normalized) expansion as

$\displaystyle \phi(G) = \inf_{S \ \rm finite} \ \ \frac {E(S,V-S)}{ |S|}$

In a ${d}$ -regular infinite tree, the expansion is ${d-1}$ , because, if we take any set ${S}$ of ${n}$ vertices, there are at most ${n-1}$ edges in the subgraph induced by ${S}$ (because it’s a forest with ${n}$ vertices) and so there are at least ${dn - n + 1}$ edges leaving ${S}$ . It is easy to see that every other infinite ${d}$ -regular graph has expansion at most ${d-1}$ because, for every ${n}$ , we can run a DFS for ${n}$ steps starting from an arbitrary vertex ${v}$ until we either discover ${n}$ vertices reachable from ${v}$ (including ${v}$ ), or we find a connected component of size ${\leq n}$ . In the former case, let ${S}$ be the ${n}$ vertices found by the DFS: the set ${S}$ induces a connected subgraph, so there are ${\geq n-1}$ edges inside ${S}$ and ${\leq dn - n +1}$ edges leaving ${S}$ . In the latter case, the expansion is zero.

What about the spectral expansion of the infinite tree? If ${G=(V,E)}$ is a finite ${d}$ -regular graph, then the largest eigenvalue of its adjacency matrix is ${d}$ , and the corresponding eigenvector is the vector ${(1,\ldots,1)}$ . By the spectral theorem we have

$\displaystyle \sigma_2 = \max_{x \in {\mathbb R}^V \ : \ \sum_v x_v = 0} \ \ \frac { | 2 \sum_{\{ u,v\} \in E} x_u x_v | } {\sum_v x_v^2}$

When we have an infinite ${d}$ -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

$\displaystyle \sigma (G) = \sup_{x \in {\mathbb R}^V : \ \sum_v x_v^2 < \infty } \ \ \frac { | 2 \sum_{\{ u,v\} \in E} x_u x_v | } {\sum_v x_v^2}$

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 ${d}$ -regular tree ${T= ( V,E)}$ we have ${\sigma \leq 2 \sqrt { d-1}}$ , we need to argue that for every vector ${x \in {\mathbb R}^V}$ such that ${\sum_v x_v^2 < \infty }$ we have

$\displaystyle 2| \sum_{\{ u,v \} \in E} x_u x_v | \leq 2 \sqrt { d -1 } \cdot \sum_v x_v^2 \ \ \ \ \ (1)$

If we fix a root ${r}$ , so that we can talk about the parent and the children of each node, and if we call ${C_u}$ the set of children of ${v}$ , then we want to show

$\displaystyle 2 | \sum_u \sum_{v\in C_u} x_u x_v | \leq 2 \sqrt { d -1 } \cdot \sum_v x_v^2 \ \ \ \ \ (2)$

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 ${2|x_u x_v| \leq x_u^2 + x_v^2}$ , but this does not go anywhere, and it would give an upper bound of ${d \sum_v x_v^2}$ . This means that the bound ${2|x_u x_v| \leq x_u^2 + x_v^2}$ is often loose, which must happen because ${x_u}$ and ${x_v}$ are often different in magnitude. To see why this should be the case, note that if we call ${c:= \sum_v x^2_v}$ , considering that there are ${d\cdot (d-1)^{t-1}}$ vertices at distance ${t}$ from the root, the typical vertex ${v}$ at distance ${t}$ from the root satisfies ${x_v^2 = O(1/(d-1)^t)}$ , and we may think that if ${x_v}$ is a child of ${x_u}$ it should often be the case that ${x^2_v}$ is about a factor of ${(d-1)}$ smaller than ${x_u^2}$ . If that were the case, then a tighter form of Cauchy-Schwarz would be ${2 |x_u| \cdot |x_v| \leq \frac 1 {\sqrt {d-1}} x_u^2 + \sqrt{d-1} x_v^2}$ . Let us try that bound:

$\displaystyle 2 \left| \sum_u \sum_{v\in C_u} x_u x_v \right| \leq \sum_u \sum_{v \in C_u} \frac 1 {\sqrt {d-1}} x_u^2 + \sqrt{d-1} x_v^2$

$\displaystyle = \frac d {\sqrt {d-1}} x_r^2 + \sum_{v \neq r} \left( \frac 1 {\sqrt {d-1}} \cdot (d-1) + \sqrt{d-1} \right) x_v^2$

$\displaystyle \leq 2 \sum_v \sqrt{d-1} x_v^2$

which works! To justify the identity in the middle line, note that, in the sum, the root appears ${d}$ times as a parent and never as a child, and every other vertex appears once as a child and ${d-1}$ times as a parent.

This proves that the spectral norm of the infinite ${d}$ -regular tree is at most ${2 \sqrt {d-1}}$ . To prove that it is at least this much, for every ${\epsilon >0}$ we must find a vector ${x}$ such that

$\displaystyle \left| \sum_u \sum_{v\in C_u} x_u x_v \right| \geq ( 2 \sqrt { d -1 } -\epsilon) \cdot \sum_v x_v^2$

For such vectors, the Cauchy-Schwarz argument about is nearly tight, so it means that in such vectors, if ${u}$ is the parent of ${v}$ , then ${|x_u|}$ needs to be about ${\sqrt {d-1}}$ times larger than ${|x_v|}$ . So let us start from this condition: we pick a vertex ${r}$ to be the root and we set ${x_r = 1}$ , if ${v}$ is a child of ${r}$ we set ${x_v = 1/\sqrt d}$ , and if ${v}$ is at distance ${t>1}$ from the root we set ${x_v = 1/ ( \sqrt { d \cdot (d-1)^{t-1}} )}$ . This means that if we sum ${x_v^2}$ over all the vertices at distance ${t}$ from the root we get ${1}$ , for all ${t}$ , which means that ${\sum_v x_v^2 = \infty}$ . So let us cut off the construction at some distance ${k}$ , so that ${x}$ is defined as follows:

${x_r = 1}$
${x_v = \frac 1 {\sqrt{ d (d-1)^{t-1}}}}$ if ${v}$ is at distance ${t}$ from ${r}$ and ${1\leq t \leq k-1}$
${x_v = 0}$ if ${v}$ is at distance ${\geq k}$ from ${r}$ .

We immediately see

$\displaystyle \sum_v x_v^2 = k$

Then we do the calculations and we see that

$\displaystyle \sum_u \sum_{v\in C_u} x_u x_v = \sqrt d + \sum_{t=1}^{k-2} d \cdot (d-1)^{t-1} \cdot \frac {1}{\sqrt{d \cdot (d-1)^{t-1}}} \cdot \frac {1}{\sqrt{d \cdot (d-1)^{t}}}$

$\displaystyle \sqrt d + (k-2) \sqrt {d-1 } \geq (k-1) \sqrt {d-1}$

so, for every ${k}$ , we can construct a vector ${x}$ such that

$\displaystyle 2 \sum_u \sum_{v\in C_u} | x_u x_v | \geq 2 \cdot \frac {k-1}{k} \cdot \sqrt{d-1} \sum_v x_v^2$

and we are done!

2 thoughts on “The spectrum of the infinite tree”

Pascal on August 24, 2014 at 11:59 pm said:

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

in theory

"Marge, I agree with you – in theory. In theory, communism works. In theory." — Homer Simpson

The spectrum of the infinite tree

2 thoughts on “The spectrum of the infinite tree”

Leave a Reply Cancel reply

Share this:

Like this:

Related

2 thoughts on “The spectrum of the infinite tree”

Leave a Reply Cancel reply