Discrete Mathematics and Optimization Seminar
April 6th, 2009
Embracing Hamiltonicity in Achlioptas processes
Michael Krivelevich
Tel Aviv University
Consider the following model of random graphs. We are given a monotone graph property P (Hamiltonicity, non-3-colorability, containment of a copy of a fixed graph H etc.) and an integer parameter r=r(n)>=1. At each round, we are presented with r random edges from the set of edges of the complete graph K_n on n vertices and are asked to choose one of them. The task is to design an online edge choice algorithm that will be able to postpone (avoid) or to facilitate (embrace) almost surely the appearance of P. This model is sometimes called the Achlioptas process, after Dimitris Achlioptas who suggested it for the case r=2 and the property P being the existence of a linear sized connected component (the so called giant component) in the graph.

In this talk I will discuss the question of embracing Hamiltonicity in the Achlioptas process with parameter r. Here an algorithm chooses one edge at each round so as to create a Hamilton cycle as quickly as possible. Obviously, a Hamilton cycle cannot be created before it appears in the union of all edges presented to the algorithm, which (given the threshold of n\ln n/2 for the appearance of a Hamilton cycle in the model G(n,m)) supplies immediately a lower bound of n\ln n/(2r). Also, it is clearly impossible to create a Hamilton cycle in less than n rounds.

We prove that the above described combined lower bound is tight for r=o(log n), and also for r>>log n. For the intermediate regime r=c log n, Hamiltonicity can be achieved almost surely in c'n rounds.

Joint work with Eyal Lubetzky (Microsoft Research) and Benny Sudakov (UCLA).