Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
Carnegie Melllon University Title: Coloring directed Hamilton cycles online Abstract: 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. |