Hamiltonicity of random subgraphs of the hypercube
Hamiltonicity of random subgraphs of the hypercube
复制标题
DOI：
10.1137/1.9781611976465.56
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Padraig Condon;Alberto Espuny Díaz;António Girão;D. Kühn;Deryk Osthus
中科院分区：
文献类型：
--
作者：
Padraig Condon;Alberto Espuny Díaz;António Girão;D. Kühn;Deryk Osthus
研究了超立方体{q}^n$的随机子图的哈密顿性。我们的第一个主要定理是最优命中时间结果。考虑一个随机过程，它按照一个统一选择的随机顺序包含$\mathcal{q}^n$的边。然后，大概率地，只要这个过程产生的图具有最小度$2k$，它就包含$k$边不相交的哈密尔顿圈，对于任何固定的$k\in\mathbb{N}$.其次，我们得到了一个扰动结果：如果$H\subseteq\mathcal{q}^n$满足$\Delta(H)\geq\alphan$且$α>；0$固定，并且我们考虑$\mathcal{q}^n$的随机二项式子图$\mathcal{q}^n_p$且$p\in(0，1]$固定，则对于任何固定的$k\in(0，1)$，$H\cup\mathcal{q}^n_p$包含$k$边不相交的哈密顿圈.特别是，这两个结果解决了一个长期存在的猜想，例如由Bollobas提出的，即超立方体的随机二项式子图的哈密顿性的阈值概率等于$1/2$。我们的技巧还表明，对于(0，1]$中所有固定的$p，图$\数学{q}^n_p$包含一个几乎生成圈。我们的方法包括分枝过程、罗德尔啃食和吸收。
We study Hamiltonicity in random subgraphs of the hypercube $\mathcal{Q}^n$. Our first main theorem is an optimal hitting time result. Consider the random process which includes the edges of $\mathcal{Q}^n$ according to a uniformly chosen random ordering. Then, with high probability, as soon as the graph produced by this process has minimum degree $2k$, it contains $k$ edge-disjoint Hamilton cycles, for any fixed $k\in\mathbb{N}$. Secondly, we obtain a perturbation result: if $H\subseteq\mathcal{Q}^n$ satisfies $\delta(H)\geq\alpha n$ with $\alpha>0$ fixed and we consider a random binomial subgraph $\mathcal{Q}^n_p$ of $\mathcal{Q}^n$ with $p\in(0,1]$ fixed, then with high probability $H\cup\mathcal{Q}^n_p$ contains $k$ edge-disjoint Hamilton cycles, for any fixed $k\in\mathbb{N}$. In particular, both results resolve a long standing conjecture, posed e.g. by Bollobas, that the threshold probability for Hamiltonicity in the random binomial subgraph of the hypercube equals $1/2$. Our techniques also show that, with high probability, for all fixed $p\in(0,1]$ the graph $\mathcal{Q}^n_p$ contains an almost spanning cycle. Our methods involve branching processes, the Rodl nibble, and absorption.