Random lifts of graphs: perfect matchings (Q2568496): Difference between revisions

A random \(n\)-lift of a graph \(G=(V, E)\) is a random graph on the vertex set \(V \times [n]\). The vertex \((v, j)\) belongs to the \(j\)th level and to the fiber \(F_v\) above \(v\). For each edge \(e=[u, v]\) in \(E(G)\), there is a random (perfect) matching \(F_e\) between \(F_u\) and \(F_v\). For a finite connected graph \(G\), let \(L_n(G)\) be the space of its \(n\)-lifts, where \(n\) is even. The main result is that one of the following holds: 1. Every \(H \in L_n(G)\) has a perfect matching. 2. Not every \(H\) has a perfect matching, but almost all of them do. 3. In almost every \(H \in L_n(G)\), the largest matching misses \(\Theta(\log n)\) vertices. 4. Every matching, in every \(H \in L_n(G)\), misses \(\Omega(n)\) vertices.