
$\delta$-Connectivity in Random Lifts of Graphs
Author(s) -
Shashwat Silas
Publication year - 2017
Publication title -
the electronic journal of combinatorics/the journal of combinatorics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.703
H-Index - 52
eISSN - 1097-1440
pISSN - 1077-8926
DOI - 10.37236/6639
Subject(s) - mathematics , combinatorics , lift (data mining) , random graph , degree (music) , delta , graph , discrete mathematics , physics , astronomy , computer science , acoustics , data mining
Amit and Linial have shown that a random lift of a connected graph with minimum degree $\delta\ge3$ is asymptotically almost surely (a.a.s.) $\delta$-connected and mentioned the problem of estimating this probability as a function of the degree of the lift. Using a connection between a random $n$-lift of a graph and a randomly generated subgroup of the symmetric group on $n$-elements, we show that this probability is at least $1 - O\left(\frac{1}{n^{\gamma(\delta)}}\right)$ where $\gamma(\delta)>0$ for $\delta\ge 5$ and it is strictly increasing with $\delta$. We extend this to show that one may allow $\delta$ to grow slowly as a function of the degree of the lift and the number of vertices and still obtain that random lifts are a.a.s. $\delta$-connected. We also simplify a later result showing a lower bound on the edge expansion of random lifts. On a related note, we calculate the probability that a subgroup of a wreath product of symmetric groups generated by random generators is transitive, extending a well known result of Dixon which covers the case for subgroups of the symmetric group.