Algorithms, Combinatorics and Optimization Seminar Patrick Bennet
Western Michigan University
Title: Rainbow Hamilton cycles in random geometric graphs

Abstract: Given a graph on n vertices and an assignment of colors to the edges, a rainbow Hamilton cycle is a cycle of length n visiting each vertex once and with pairwise different colors on the edges. Consider n points (i.e. vertices) chosen independently and uniformly at random from the unit square. Form a sequence of graphs on these n vertices by adding edges one by one between each possible pair of vertices. Edges are added in increasing order of length. Each time a new edge is added, it receives a color chosen uniformly at random and with repetition from a set of Kn colors, where K is a large constant. Then, w.h.p. the first graph in the sequence with minimum degree at least 2 contains a rainbow Hamilton cycle. Joint work with Deepak Bal, Xavier Pérez-Giménez, and Paweł Prałat.

Date: Wednesday, November 30, 2016
Time: 3:30 pm
Location: Wean Hall 8220
Note: unusual day.