Random graph coverings. I: General theory and graph connectivity (Q700369)

The authors introduce random graph covering: If \(G\) is a graph and \(n\) is an integer then replace each vertex of \(G\) by \(n\) copies of vertices and join these sets by random matchings whenever the corresponding vertices are adjacent in \(G\). The main result (to be followed by others about girth, chromatic number etc. in subsequent papers of the authors) is that if \(\delta \geq 3\) is the smallest vertex degree in \(G\) then almost all \(n\)-covers are \(\delta\)-connected.