About the topology of a $d$-regular tree

Question

• What is the proof that the infinite $d$-regular tree is an universal covering space for any $d$-regular graph?

• Is it true that the infinite $d$-regular tree is a Ramanujan graph? (any easy way to see that if true?)

Answer 1

I can answer your second question: usually beeing a Ramanujan graph is only defined for finite graphs. The definition is:

Let $G=(V,E)$ be a finite, undirected, connected, $k$-regular graph, for $k \in \mathbb{N}$ and $A$ its adjacency matrix. Then $G$ is called Ramanujan graph, if every eigenvalue $\lambda$ of $A$ is either $\lambda = \pm k$ or $| \lambda | \leq 2 \sqrt{k-1}$.

The $d$-regular tree is (as you already wrote) an infinte graph. So it can't satisfy this definition.

But this tree still plays an important role in the theory of Ramanujan graphs. One can show (I think it was proved by Kesten in "Symmetric Random Walks On Groups") that the $L^2$-spetrum (I will explain below what this is) of this tree is the intervall $[-2 \sqrt{k-1}, 2 \sqrt{k-1}]$. Also this tree is the universal cover of every finite, connected, $k$-regular graph. So beeing a Ramanujan graph is exactly the same, as having a non-trivial spetrum ($\pm k$ are the trivial eigenvalues) that lies in the $L^2$-spectrum of its universal cover.

So what is the $L^2$-spetrum. Let $G=(V,E)$ be any undirected (locally finite) graph (note that this graph can be infinite). Let $L^2(G) = \{ f: V \to \mathbb{R} | \sum_{y \sim x} |f(y)|^2 < \infty \}$, here $y \sim x$ means $(x,y) \in E$. Now in the case the adjacency operator is $A: L^2(g) \to L^2(G), (A f)(x) = \sum_{y \sim x} f(y)$. Note that in the case where $G$ is finite, $L^2(G)$ is just the set of all maps $f: V \to \mathbb{R}$, so this can be seen as a gerneralization of the adjancency matrix.

Answer 2

I can answer your first question:

First of all, we must consider $G$ to be connected for this to work. Now, if you consider both the d-regular graph $G$ and the infinite d-regular tree $T^{d}$ as 1-dimensional CW-complexes (thus, with the topology induced by the CW-complex structure), then $T^{d}$ is the universal cover of $G$ in the usual topological sense, that is there is a covering map $p:T^{d}\to G$ and $T^{d}$ is a simply connected space. Let us see why these claims hold:

• $T^{d}$ is a simply connected space. For a space to be simply connected means that it is path-connected (in our case of graphs this means just connected) and every loop is homotopic to the point. In the case of graphs, the latter just that it is acyclic, as a non-trivial loop corresponds to a cycle in the graph, which obviously is not homotopic to a point.
• To find a covering map $p:T^{d}\to G$ we construct $T^{d}$ by mimicking the construction of the universal covering of an arbitrary topological space but in a discrete setting. Let $v\in V(G)$ be a vertex. Set $X$ to be the set of reduced (or non-backtracking) walks in $G$ starting at $v$. By reduced, we mean that an edge $e$ in the walk cannot be immediately followed by its transposed edge $\overline{e}$. So let $V(T^{d})=X$ and let two such walks be adjacent if and only if one is a single-step extension of the other. Now, it is easy to see that the graph described above is the infinite $d$-regular tree and that the map $p:T^{d}\to G$ that sends the a reduced walk to its terminal vertex is an infinite-fold covering map.