Hamiltonicity thresholds in Achlioptas processes
Hamiltonicity thresholds in Achlioptas processes
复制标题
Achlioptas 过程中的哈密顿度阈值
DOI：
10.1002/rsa.20302
复制
发表时间：
2008
影响因子：
1
通讯作者：
B. Sudakov
中科院分区：
文献类型：
--
作者：
Michael Krivelevich;E. Lubetzky;B. Sudakov
在这篇文章中，我们分析了一个汉密尔顿循环的出现在以下随机过程。该过程从nlabeled顶点上的空图开始。在每一轮中，我们都会看到K = K（n）条边，这些边是从缺失的边中随机均匀选择的，并要求我们将其中一条边添加到当前图中。我们的目标是尽快创造一个汉密尔顿周期。我们表明，这个问题有三个政权，取决于K的值。对于K = o（log n），哈密尔顿性的阈值是${1 + o（1）\over 2K}$n log n，即，典型地，我们可以构造比通常的随机图过程快K倍的汉密尔顿循环。当K = ω（log n）时，我们基本上可以几乎不浪费边，并且以高概率在n + o（n）轮中创建汉密尔顿循环。最后，在K = Θ（log n）的中间状态中，阈值具有阶数，我们获得相差3倍的上界和下界。© 2010 Wiley Periodicals，Inc.随机结构算法，2010
In this article, we analyze the appearance of a Hamilton cycle in the following random process. The process starts with an empty graph on nlabeled 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) \over 2K}$n log n, 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 nand we obtain upper and lower bounds that differ by a multiplicative factor of 3. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010