TITLE: Hamilton cycles in random graphs (Dissertation Proposal)
SPEAKER: Kelley Burgin
WHEN: January 30, 1:30pm
WHERE: Porter Hall A19
ABSTRACT: We discuss the existence of Hamilton cycles in three different models of random graphs. In doing so, we present general proof techniques which include the differential equation method.
The first model is the random lift model introduced by Linial and Amit. For a fixed base graph K=(V,E), a random lift has vertex set V x [n] and for each edge (i,j) in E, there is a random perfect matching between {i} x [n] and {j} x [n]. We show that random lifts of the complete graph and complete bipartite graph contain a Hamilton cycle whp.
The second model is a random graph on n vertices in which (1-b)n vertices have degree 4 and the other bn vertices have degree 5. We show that for certain values of b, the graph is Hamiltonian whp.
The last model is a sparse random graph on n vertices with cn/2 random edges and minimum degree 3. We show that this random graph is Hamiltonian for c at least 3.01.
