ACO The ACO Seminar (2016–2017)

Feb. 16, 3:30pm, Wean 8220
Joseph Briggs, CMU
Coloring directed Hamilton cycles online


Consider a directed analogue of the random graph process on n vertices, whereby the n2-n directed edges are ordered uniformly at random and revealed one at a time, giving a nested sequence of directed graphs D0,D1,...,Dm,... . 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 DX contains q Hamilton cycles with pairwise empty intersection. This certainly is always at least T, the first time that DT 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 Di 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 DT in all q colors. This work is joint with Michael Anastos.

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

Back to the ACO home page