The ACO Seminar (2016–2017)

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.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.