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

$\displaystyle V_{B}=\{v_{1},\ldots ,v_{s}\}\quad {\vec {E}}_{B}=\{e_{1},\ldots ,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

$\displaystyle V_{B[\sigma ]}=V_{B}\times \{1,\ldots ,n\}$

and its directed edges the set

$\displaystyle {\vec {E}}_{B[\sigma ]}={\vec {E}}_{B}\times \{1,\ldots ,n\}$

where

$\displaystyle {\vec {E}}_{B}=\{e_{1},e_{1}^{-1},\ldots ,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{aligned}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{aligned}}$

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.