论文标题
半随机图过程中哈密顿周期的完全自适应策略
A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process
论文作者
论文摘要
半随机图进程是一个单人游戏，其中最初在$ n $顶点上显示了一个空图。在每回合中，将一个顶点$ u $随机地独立和统一地呈现给玩家。然后，播放器会自适应地选择一个顶点$ V $，然后将Edge $ UV $添加到图表中。对于固定的单调图属性，播放器的目的是强迫图形以尽可能少的弹性在很小的弹药中以高概率满足该属性。 我们专注于在尽可能少的一轮中构建哈密顿周期的问题。特别是，我们为玩家提出了一种自适应策略，该策略以$αn$ rounds的形式实现，其中$α<2.01678 $是从解决方案派生到某些微分方程系统的。我们还表明，玩家无法在不到$βn$ rounds的情况下实现所需的物业，其中$β> 1.26575 $。这些结果提高了以前最著名的边界，因此，上限和下限之间的差距从1.39162降低到0.75102。
The semi-random graph process is a single player game in which the player is initially presented an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the player independently and uniformly at random. The player then adaptively selects a vertex $v$, and adds the edge $uv$ to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a Hamiltonian cycle in as few rounds as possible. In particular, we present an adaptive strategy for the player which achieves it in $αn$ rounds, where $α< 2.01678$ is derived from the solution to some system of differential equations. We also show that the player cannot achieve the desired property in less than $βn$ rounds, where $β> 1.26575$. These results improve the previously best known bounds and, as a result, the gap between the upper and lower bounds is decreased from 1.39162 to 0.75102.
