  Amit and Linial showed that a random lift of a graph with minimum degree
$\delta\ge3$ is asymptotically almost surely $\delta$-connected, and mentioned
the problem of estimating this probability as a function of the degree of the
lift. We relate a randomly generated subgroup of the symmetric group on $n$
elements to random $n$-lifts of a graph and use it to provide such an estimate
along with related results. We also improve their later result showing a lower
bound on the edge expansion on random lifts. Our proofs rely on new ideas from
group theory which make several improvements possible. We exactly calculate the
probability that a random lift of a connected graph with first Betti number $l$
is connected by showing that it is equal to the probability that a subgroup of
the symmetric group generated by $l$ random elements is transitive. We also
calculate the probability that a subgroup of a wreath product of symmetric
groups generated by $l$ random generators is transitive. We show the existence
of homotopy invariants in random covering graphs which reduces some of their
properties to those of random regular multigraphs, and in particular makes it
possible to compute the exact probability with which random regular multigraphs
are connected. All our results about random lifts easily extend to iterated
random lifts.
