论文标题
半随机图过程中的汉密尔顿周期
Hamilton Cycles in the Semi-random Graph Process
论文作者
论文摘要
半随机图进程是一个单人游戏，其中最初在$ n $顶点上显示了一个空图。在每回合中，将一个顶点$ u $随机地独立和统一地呈现给玩家。然后，播放器会自适应地选择一个顶点$ V $，然后将Edge $ UV $添加到图表中。对于固定的单调图属性，播放器的目的是强迫图形以尽可能少的弹性在很小的弹药中以高概率满足该属性。 我们专注于在尽可能少的回合中构建汉密尔顿周期的问题。特别是，我们为玩家提出了一种新的策略，该策略以$（2+4e^{ - 2}+0.07+O（1））\，n <2.61135 \，n $ rounds，假设特定的非convex优化问题具有负面解决方案（我们的数字支持）。假设这种技术条件成立，这将在$ 3 \，n $ nodles的先前最著名的上限上有所改善。我们还表明，先前最佳的下限$（\ ln 2 + \ ln（1+ \ ln 2） + o（1））\，n $并不紧。
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 Hamilton cycle in as few rounds as possible. In particular, we present a novel strategy for the player which achieves a Hamiltonian cycle in $(2+4e^{-2}+0.07+o(1)) \, n < 2.61135 \, n$ rounds, assuming that a specific non-convex optimization problem has a negative solution (a premise we numerically support). Assuming that this technical condition holds, this improves upon the previously best known upper bound of $3 \, n$ rounds. We also show that the previously best lower bound of $(\ln 2 + \ln (1+\ln 2) + o(1)) \, n$ is not tight.
