Sandbox:DavidKohler/Relativized Alon Conjecture/Random cover model

A model that generates graph covering of any desired degree of a given base graph allow to make probabilistic statements. The Random cover model is such a model.

Definition

Let B be a fixed connected base graph and choose an orientation of its edges. We will denote its vertices and oriented edges by

$V_B=\{v_1,\dots ,v_s\}{\overrightarrow{E}}_B=\{e_1,\dots ,e_a\}$

A covering of degree n is obtained by choosing a permutation of n objects for each oriented edge of the base graph. Let σ = (σ₁, ..., σ_a) be a choice of permutations of n objects, then we construct a covering, B[σ] as follow. Its vertices is simply the set

$V_{B[\sigma ]}=V_B\times \{1,\dots ,n\}$

and its directed edges the set

${\overrightarrow{E}}_{B[\sigma ]}={\overrightarrow{E}}_B\times \{1,\dots ,n\}$

where

${\overrightarrow{E}}_B=\{e_1,e_1^{-1},\dots ,e_a,e_a^{-1}\}$

where e_i = e_i^-1 if that edge is a half-loop. The tail and head maps are given as follow:

$\begin{array}{rl}{t}_{B[\sigma ]}(e_i,j)& =(t_B(e_i),j)\\ h_{B[\sigma ]}(e_i,j)& =(h_B(e_i),{\sigma }_{e_i}(j))\\ t_{B[\sigma ]}(e_i^{-1},j)& =(h_B(e_i),{\sigma }_{e_i}(j))\\ h_{B[\sigma ]}(e_i^{-1},j)& =(t_B(e_i),j)\end{array}$

and where the opposite edge to the directed edge (e_i, j) is the directed edge (e_i^-1, j). It is easy to verify that this makes B[σ] a cover graph of the base graph B of degree n.

We put a uniform distribution on the choice of permutations and obtain a probabilistic model for coverings of degree n of the base graph B. Note that this is not equivalent to a uniform distribution on all coverings of degree n of the base graph as different choices of permutations can yield the same covering graph.

Special case: Regular graphs

Let d be an even integer and consider the base graph B consisting of d/2 whole-loops on one vertex. Graph coverings of degree n of this graph are d-regular graphs on n vertices.