Nov. 30, 3:30pm, Wean 8220 (Note unusual day)

Patrick Bennet, Western Michigan University

Rainbow Hamilton cycles in random geometric graphs

Patrick Bennet, Western Michigan University

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.

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