论文标题
汉密尔顿周期的正方形在随机扰动图中
The square of a Hamilton cycle in randomly perturbed graphs
论文作者
论文摘要
我们在随机扰动图的模型中研究了汉密尔顿周期平方的外观，该模型对于给定的$α\ in（0,1）$，即任何$ n $ vertex图的结合，具有最低度$ a $ $αn$和二项式随机图$ g（n，p）$。当$α> 1/2 $ $时，这是已知的，我们确定在所有剩余情况下，即对于每种$α\ le 1/2 $的确切扰动阈值概率。我们证明，随着$α$在间隔$（0,1）$上的范围，阈值执行的“跳跃”数量可观。我们的结果对$ 2 $ universality的扰动阈值具有影响，我们还充分解决了所有开放式案例。
We investigate the appearance of the square of a Hamilton cycle in the model of randomly perturbed graphs, which is, for a given $α\in (0,1)$, the union of any $n$-vertex graph with minimum degree $αn$ and the binomial random graph $G(n,p)$. This is known when $α> 1/2$, and we determine the exact perturbed threshold probability in all the remaining cases, i.e., for each $α\le 1/2$. We demonstrate that, as $α$ ranges over the interval $(0,1)$, the threshold performs a countably infinite number of `jumps'. Our result has implications on the perturbed threshold for $2$-universality, where we also fully address all open cases.
