### Abstract

In this article, 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(logn), the threshold for Hamiltonicity is n ^{logn, i.e., typically we can construct a Hamilton cycle K} times faster that in the usual random graph process. When K = ω(logn) 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 = Θ (logn), the threshold has order n and we obtain upper and lower bounds that differ by a multiplicative factor of 3.

Original language | English (US) |
---|---|

Pages (from-to) | 1-24 |

Number of pages | 24 |

Journal | Random Structures and Algorithms |

Volume | 37 |

Issue number | 1 |

DOIs | |

State | Published - Aug 2010 |

### Keywords

- Hamilton cycles
- Random graph processes

### ASJC Scopus subject areas

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Hamiltonicity thresholds in Achlioptas processes'. Together they form a unique fingerprint.

## Cite this

*Random Structures and Algorithms*,

*37*(1), 1-24. https://doi.org/10.1002/rsa.20302