Random lifts of graphs are highly connected (Q1953505)

Summary: In this note we study asymptotic properties of random lifts of graphs introduced by Amit and Linial as a new model of random graphs. Given a base graph \(G\) and an integer \(n\), a random lift of \(G\) is obtained by replacing each vertex of \(G\) by a set of \(n\) vertices, and joining these sets by random matchings whenever the corresponding vertices of \(G\) are adjacent. In this paper we study connectivity properties of random lifts. We show that the size of the largest topological clique in typical random lifts, with \(G\) fixed and \(n\rightarrow\infty\), is equal to the maximum degree of the core of \(G\) plus one. A similar idea can be used to prove that for any graph \(G\) with \(\delta(G)\geq2k-1\) almost every random lift of \(G\) is \(k\)-linked.