Hamiltonicity of Random Subgraphs of the Hypercube

We study Hamiltonicity in random subgraphs of the hypercube <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper Q Superscript n"> <mml:semantics> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">Q</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> <mml:annotation encoding="application/x-tex">\mathcal {Q}^n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Our first main theorem is an optimal hitting time result. Consider the random process which includes the edges of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper Q Superscript n"> <mml:semantics> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">Q</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> <mml:annotation encoding="application/x-tex">\mathcal {Q}^n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> according to a uniformly chosen random ordering. Then, with high probability, as soon as the graph produced by this process has minimum degree <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 k"> <mml:semantics> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>k</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">2k</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, it contains <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> edge-disjoint Hamilton cycles, for any fixed <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k element-of double-struck upper N"> <mml:semantics> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>∈</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">N</mml:mi> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">k\in \mathbb {N}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Secondly, we obtain a perturbation result: if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H subset-of-or-equal-to script upper Q Superscript n"> <mml:semantics> <mml:mrow> <mml:mi>H</mml:mi> <mml:mo>⊆</mml:mo> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">Q</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">H\subseteq \mathcal {Q}^n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> satisfies <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="delta left-parenthesis upper H right-parenthesis greater-than-or-equal-to alpha n"> <mml:semantics> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>H</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>≥</mml:mo> <mml:mi>α</mml:mi> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\delta (H)\geq \alpha n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="alpha greater-than 0"> <mml:semantics> <mml:mrow> <mml:mi>α</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">\alpha &gt;0</mml:annotation> </mml:semantics> </mml:math> </inline-formula> fixed and we consider a random binomial subgraph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper Q Subscript p Superscript n"> <mml:semantics> <mml:msubsup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">Q</mml:mi> </mml:mrow> <mml:mi>p</mml:mi> <mml:mi>n</mml:mi> </mml:msubsup> <mml:annotation encoding="application/x-tex">\mathcal {Q}^n_p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper Q Superscript n"> <mml:semantics> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">Q</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> <mml:annotation encoding="application/x-tex">\mathcal {Q}^n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p element-of left-parenthesis 0 comma 1 right-bracket"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>∈</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">]</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">p\in (0,1]</mml:annotation> </mml:semantics> </mml:math> </inline-formula> fixed, then with high probability <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H union script upper Q Subscript p Superscript n"> <mml:semantics> <mml:mrow> <mml:mi>H</mml:mi> <mml:mo>∪</mml:mo> <mml:msubsup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">Q</mml:mi> </mml:mrow> <mml:mi>p</mml:mi> <mml:mi>n</mml:mi> </mml:msubsup> </mml:mrow> <mml:annotation encoding="application/x-tex">H\cup \mathcal {Q}^n_p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> contains <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> edge-disjoint Hamilton cycles, for any fixed <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k element-of double-struck upper N"> <mml:semantics> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>∈</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">N</mml:mi> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">k\in \mathbb {N}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. 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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1 slash 2"> <mml:semantics> <mml:mrow> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">1/2</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Our techniques also show that, with high probability, for all fixed <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p element-of left-parenthesis 0 comma 1 right-bracket"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>∈</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">]</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">p\in (0,1]</mml:annotation> </mml:semantics> </mml:math> </inline-formula> the graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper Q Subscript p Superscript n"> <mml:semantics> <mml:msubsup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">Q</mml:mi> </mml:mrow> <mml:mi>p</mml:mi> <mml:mi>n</mml:mi> </mml:msubsup> <mml:annotation encoding="application/x-tex">\mathcal {Q}^n_p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> contains an almost spanning cycle. Our methods involve branching processes, the Rödl nibble, and absorption.