Algorithms, Combinatorics and Optimization Seminar Joseph Briggs
Carnegie Melllon University
Title: Coloring directed Hamilton cycles online

Abstract: Consider a directed analogue of the random graph process on n vertices, whereby the n²-n directed edges are ordered uniformly at random and revealed one at a time, giving a nested sequence of directed graphs D₀,D₁,...,D_m,... . In this setting, one may ask about events that hold with probability 1-o(1) (whp) as n tends to infinity.

In particular, for a fixed q=O(1), we wish to study the hitting time for the emergence of q edge-disjoint directed Hamilton cycles. This is the smallest X for which D_X contains q Hamilton cycles with pairwise empty intersection. This certainly is always at least T, the first time that D_T has both minimum in-degree and out-degree at least q, but in fact Alan Frieze has shown that X=T whp.

Consider an online coloring process in which each newly appearing edge of D_i is painted irrevocably with one of q colors. In this talk, we present a randomized coloring algorithm that gives an online version of Frieze's result, that is, yielding a Hamilton cycle in D_T in all q colors. This work is joint with Michael Anastos.

Date: Thursday, February 16, 2017
Time: 3:30 pm
Location: Wean Hall 8220
Note: Before the talk, at 3:10 pm, there will be tea and cookies in Wean Hall 6220.