Hamiltonicity of Random Subgraphs of the Hypercube

Padraig Condon, Alberto Espuny Diaz, Antonio Girao, Daniela Kuhn, Deryk Osthus

ISBN 10: 147047266X / ISBN 13: 9781470472665

Published by American Mathematical Society, US, 2025

About this Item

The Memoirs of the AMS is devoted to the publication of new research in all areas of pure and applied mathematics. The Memoirs is designed particularly to publish long papers of groups of cognate papers in book form, and is under the supervision of the Editorial Committee of the AMS journal Transactions of the American Mathematical Society. All papers are peer-reviewed.

Seller Inventory # LU-9781470472665

Bibliographic Details

• Title: Hamiltonicity of Random Subgraphs of the Hypercube
• Publisher: American Mathematical Society, US
• Publication Date: 2025
• Language: English
• ISBN 10: 147047266X
• ISBN 13: 9781470472665
• Binding: Paperback
• Condition: New

About this title

Synopsis

"We study Hamiltonicity in random subgraphs of the hypercube Qn. Our first main theorem is an optimal hitting time result. Consider the random process which includes the edges of Qn 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 N. Secondly, we obtain a perturbation result: if H Qn satisfies (H) n with 0 fixed and we consider a random binomial subgraph Qnp of Qn with p (0, 1] fixed, then with high probability HQnp contains k edge-disjoint Hamilton cycles, for any fixed k 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 (0, 1] the graph Qnp contains an almost spanning cycle. Our methods involve branching processes, the Rodl nibble, and absorption"-- Provided by publisher.