Sandbox:DavidKohler/Relativized Alon Conjecture/Graph cover

A graph cover is the application of coverings (from topology) to the context of graphs.

Definition

Let G and B be two directed graphs. A morphism of directed graphs γ: G → B is a covering map if it is an epimorphism (that is, both the vertex map and the edge map are surjective) and if it is a local isomorphism that is for any vertex w ∈ V_G, the edge map γ_E induces a bijection between t_G^-1(w) and t_B^-1(γ(w)) and a bijection between h_G^-1(w) and h_B^-1(γ(w)).

If γ: G → B is a covering map and B is connected, then the degree of the covering map, denoted [G: B], is the number of preimages of a vertex or edge in the graph B under the covering map γ (which does not depend on the vertex or edge). If B is not connected, we insist that the the number of preimages of the covering map of a vertex or edge is the same, i.e., the degree is independent of the connected component, and we will write this number as [G : B].

We say that a morphism of graphs is a covering map if the morphism on underlying directed graphs is a covering map.

We say that the graph G is a graph cover of the base graph B is there exists a covering map γ G → B.

Basic definitions

Let γ: G → B be a graph covering of degree n and consider the spaces ℓ(G) and ℓ(B) of all complex-valued functions on the vertices of the graph G and respectively B. Then we can define two operators:

• The lifting operator γ* defined by

${\begin{aligned}\gamma ^{*}:\ell (B)&\to \ell (G)\\f&\mapsto f\circ \gamma \end{aligned}}$

• The averaged pull operator γ_* defined by

${\begin{aligned}\gamma _{*}:\ell (G)&\to \ell (B)\\f&\mapsto \gamma _{*}f\end{aligned}}$

where

$\displaystyle \gamma _{*}f(v)={\frac {1}{n}}\sum _{w\in \gamma ^{-1}(v)}f(w)$

Old and New eigenvalues

Let G be a graph cover of a base graph B and γ: G → B a covering map. The eigenvalues of the graph B lift to the graph G, in other words, the eigenvalues of the base graph B are included (up to multiplicity) among the eigenvalues of the cover graph G.

Property

Let f ∈ ℓ(B) be an eigenvector of the base graph B with associated eigenvalue λ, then γ*f ∈ ℓ(G) is an eigenvector of the graph G for the same eigenvalue.

Proof

We simply check that γ*f is an eigenvector with associated eigenvalue λ for the graph G. Let x ∈ VG be a vertex of the graph G and consider the sum $\sum _{y\in t_{H}^{-1}(x)}\gamma ^{*}f(h_{H}(y))$ which, by definition of an eigenvector we want to show equals λγ*f(x). By definition of the lifting operator, we have $\sum _{y\in t_{G}^{-1}(x)}\gamma ^{*}f(h_{G}(y))=\sum _{y\in t_{G}^{-1}(x)}f(\gamma ((h_{G}(y)))$ and since γ is a morphism of graphs we have that $\sum _{y\in t_{H}^{-1}(x)}f(\gamma ((h_{H}(y)))=\sum _{y\in t_{H}^{-1}(x)}f(h_{B}(\gamma (y)))$ The morphism γ being a graph covering, it induces a bijection between the sets tG-1(x) and tB-1(γ(x)). Hence, if we denote by e a generic element of the set tB-1(γ(x)) we can rewrite the sum as $\sum _{y\in t_{H}^{-1}(x)}f(h_{B}(\gamma (y)))=\sum _{e\in t_{B}^{-1}(\gamma (x))}f(h_{B}(e))$ and since we already know that f is an eigenvector for the base graph B we have that $\sum _{e\in t_{B}^{-1}(\gamma (x))}f(h_{B}(e))=\lambda f(\gamma (x))$ which by definition of the lifting operator is $\displaystyle \lambda f(\gamma (x))=\lambda \gamma ^{*}f(x)$ which terminates this proof.