|
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).
|
|
|
|