Sandbox:DavidKohler/Relativized Alon Conjecture/Graph cover

From UBC Wiki

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 γ: GB 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 wVG, the edge map γE induces a bijection between tG-1(w) and tB-1(γ(w)) and a bijection between hG-1(w) and hB-1(γ(w)).

If γ: GB 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 γ GB.

Basic definitions

Let γ: GB 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
  • The averaged pull operator γ* defined by

where

Old and New eigenvalues

Let G be a graph cover of a base graph B and γ: GB 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.