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