The Taub Faculty of Computer Science Events and Talks

Consider a directed analogue of the random graph process on $n$ vertices, whereby the $n^2-n$ directed edges are ordered uniformly at random and revealed one at a time, giving a nested sequence of directed graphs $D_0,D_1,\dots,D_m, \dots$. 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. more details» copy to my calendar»