English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Amit and Linial showed that a random lift of a graph with minimum degree$\delta\ge3$ is asymptotically almost surely $\delta$-connected, and mentionedthe problem of estimating this probability as a function of the degree of thelift. 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 estimatealong with related results. We also improve their later result showing a lowerbound on the edge expansion on random lifts. Our proofs rely on new ideas fromgroup theory which make several improvements possible. We exactly calculate theprobability 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 ofthe symmetric group generated by $l$ random elements is transitive. We alsocalculate the probability that a subgroup of a wreath product of symmetricgroups generated by $l$ random generators is transitive. We show the existenceof homotopy invariants in random covering graphs which reduces some of theirproperties to those of random regular multigraphs, and in particular makes itpossible to compute the exact probability with which random regular multigraphsare connected. All our results about random lifts easily extend to iteratedrandom lifts.

Randomly Generated Subgroups of the Symmetric Group and Random Lifts of Graphs