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 ∈ VG, 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 γ: 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
- The averaged pull operator γ* defined by
where
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 which, by definition of an eigenvector we want to show equals λγ*f(x). By definition of the lifting operator, we have and since γ is a morphism of graphs we have that 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 and since we already know that f is an eigenvector for the base graph B we have that which by definition of the lifting operator is which terminates this proof. |