Speaker: Theo Molla
Title: Powers of Hamiltonian cycles in multipartite graphs
Abstract:
The minimum proportional degree of a multipartite graph is the minimum over all vertices v and all parts U not containing v of the number of neighbors of v in U divided by the order of U. In 1963 Moon and Moser proved that every balanced bipartite graph with minimum proportional degree greater than 1/2 contains a Hamiltonian cycle.  In this talk, we will discuss the following related result: For every positive integer r, if a multipartite graph on n vertices has minimum proportional degree at least 1 - 1/r + o(1) and no part has order greater than n/r, then there exists a cyclic ordering of the vertices in which every set of r consecutive vertices is a clique.
  
This is joint work with Louis DeBiasio and Ryan Martin.