Hamiltonicity thresholds in Achlioptas processes
| dc.creator | Krivelevich, Michael | |
| dc.creator | Lubetzky, Eyal | |
| dc.creator | Sudakov, Benny | |
| dc.date | 2008-04-29 | |
| dc.date.accessioned | 2026-07-07T09:35:58Z | |
| dc.date.available | 2026-07-07T09:35:58Z | |
| dc.description | 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=ω(\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=Θ(\log n), the threshold has order n and we obtain upper and lower bounds that differ by a multiplicative factor of 3. | |
| dc.description | 23 pages | |
| dc.identifier | https://arxiv.org/abs/0804.4707 | |
| dc.identifier | http://arxiv.org/abs/0804.4707 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/160014 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.subject | 05C80; 60C05 | |
| dc.title | Hamiltonicity thresholds in Achlioptas processes | |
| dc.type | text |