Hamilton cycles in random graphs

The existence of Hamilton cycles in the basic models of random graphs is well studied, so we consider three new models of random graphs.; First, we consider random lifts of graphs. An n-lift of a graph K, is a graph with vertex set V( K) x [n] and for each edge (i,j) ∈ E(K) there is a perfect matching between {lcub} i{rcub} x [n] and {lcub}j{rcub} x [n]. If these matchings are chosen independently and uniformly at random then we say that we have a random n-lift. We show that there are constants h1,h 2 such that if h ≥ h1 then a random n-lift of the complete graph K h is Hamiltonian whp and if h ≥ h2 then a random n-lift of the complete bipartite graph Kh,h is Hamiltonian whp .; Next, we consider random graphs with two specified vertex degrees. Let Gnd1,d2 ,b be the space of random graphs on n vertices in which (1 - beta)n vertices have degree d 1 and betan have degree d2 . We prove that there exists a constant 0 < beta < 1 such that G ∈ Gn4,5,b is Hamiltonian whp. The proof relies on the analysis of a random greedy algorithm via the differential equation method.; Lastly, we consider the existence of Hamilton cycles in random graphs with n vertices and m random edges subject to a lower bound on minimum vertex degree. We show that for integer values of c ≥ 11 a random graph with m = cn/2 random edges and minimum vertex degree 3 has a Hamilton cycle whp. The proof relies on the analysis of a random greedy algorithm similar to that in the previous problem.