论文标题
HyperCube随机子图的汉密尔顿性
Hamiltonicity of random subgraphs of the hypercube
论文作者
论文摘要
我们在HyperCube $ \ Mathcal {Q}^n $的随机子图中研究Hamiltonicity。我们的第一个主要定理是最佳打击时间结果。根据均匀选择的随机订购，考虑包括$ \ Mathcal {q}^n $的边缘的随机过程。然后，有了很高的概率，一旦此过程产生的图形最低度$ 2K $，它包含$ k $ edge-dissjoint汉密尔顿周期，对于任何固定的$ k \ in \ mathbb {n} $。其次，我们获得一个扰动结果：如果$ h \ subseteq \ Mathcal {q}^n $满足$Δ（h）\geqαn$，$α> 0 $固定，我们考虑一个随机的二项式子图$ \ Mathcal {q}^q}^n_p $ of $ \ n_p $ of $ \ ny \ nired，in $ \ nation $ with $ \ nirst $ with $ with $ with $ with $ with $ with $ with $ with $ with $ with $ with $ po}概率$ h \ cup \ Mathcal {q}^n_p $包含$ k $ edge-dischint hamilton Cycles，对于任何固定的$ k \ in \ mathbb {n} $，这两个结果尤其是由bollobás的长期构想。 $ 1/2 $。我们的技术还表明，对于所有固定的$ p \ in（0,1] $，图$ \ Mathcal {q}^n_p $都包含一个几乎跨度的周期。我们的方法涉及分支过程，RödlNibble和吸收。
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 $δ(H)\geqαn$ with $α>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 Bollobás, 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 Rödl nibble, and absorption.
