Hamiltonicity thresholds in Achlioptas processes

Details Hamiltonicity thresholds in Achlioptas processes Hamiltonicity thresholds in Achlioptas processes

2008-04-29

arxiv.org/abs/0804.4707v1

Mathematics

Combinatorics

23 pages

Scientific paper

In this paper we analyze the appearance of a Hamilton cycle in the following random process. The process starts with an empty graph on n labeled vertices. At each round we are presented with K=K(n) edges, chosen uniformly at random from the missing ones, and are asked to add one of them to the current graph. The goal is to create a Hamilton cycle as soon as possible. We show that this problem has three regimes, depending on the value of K. For K=o(\log n), the threshold for Hamiltonicity is (1+o(1))n\log n /(2K), i.e., typically we can construct a Hamilton cycle K times faster that in the usual random graph process. When K=\omega(\log n) we can essentially waste almost no edges, and create a Hamilton cycle in n+o(n) rounds with high probability. Finally, in the intermediate regime where K=\Theta(\log n), the threshold has order n and we obtain upper and lower bounds that differ by a multiplicative factor of 3.

Affiliated with

Also associated with

No associations

Rating

Hamiltonicity thresholds in Achlioptas processes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hamiltonicity thresholds in Achlioptas processes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hamiltonicity thresholds in Achlioptas processes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-576463