Marcin Witkowski

University of Oxford

Random lifts of graphs are highly connected

In the talk we present several results on random lifts of graphs, a random graph model defined by Amit and Linial. For graphs $G$ and $H$, a map $\pi:V(H)\rightarrow~V(G)$ is a covering map from $H$ to $G$ if for every $v \in V(H)$ the restriction of $\pi$ to the neighborhood of $v$ is a bijection onto the neighborhood of $\pi(v) \in V(G)$. If such a mapping exists, we say that $H$ is a lift of $G$. Moreover, if the number of vertices of $H$ mapped to a vertex $v$ of the base graph $G$ is $n$ for all vertices $v \in G$, we say that $H$ is an $n$-lift of $G$. The set of all $n$-lifts of $G$ we denote as $L_n(G)$. The random $n$-lift of a graph $G$ is obtained by choosing uniformly at random one graph from the set $L_n(G)$. Equivalently, the random $n$-lift of $G$ can be generated by choosing independently and uniformly at random for every edge $\{u,v\} \in E(G)$ a perfect matching between the set of $n$ vertices that are mapped to $u$ and the set of $n$ vertices mapped to $v$. In this talk we briefly survey some basic properties of random lifts and its applications. In particular, we show lifts applications and present a closer insight into connectivity and Hamiltonicity of random lifts.