Hamilton cycles in random lifts of graphs

An nn-lift   of a graph KK is a graph with vertex set V(K)×[n]V(K)×[n], and for each edge (i,j)∈E(K)(i,j)∈E(K) there is a perfect matching between {i}×[n]{i}×[n] and {j}×[n]{j}×[n]. If these matchings are chosen independently and uniformly at random then we say that we have a random nn-lift. We show that there are constants h1,h2h1,h2 such that if h≥h1h≥h1 then a random nn-lift of the complete graph KhKh is hamiltonian whp and if h≥h2h≥h2 then a random nn-lift of the complete bipartite graph Kh,hKh,h is hamiltonian whp.