Hamiltonicity of random subgraphs of the hypercube / Padraig Condon, Alberto Espuny Díaz, António Girão, Daniela Kühn, Deryk Osthus.

Format:

Book

Author/Creator:

Condon, Padraig, author.

Espuny Díaz, Alberto, author.

Girão, António, author.

Kühn, Daniela, author.

Osthus, Deryk, author.

Series:

Memoirs of the American Mathematical Society ; 0065-9266 no. 1534.

Memoirs of the American Mathematical Society, 0065-9266 ; number 1534

Language:

English

Subjects (All):

Hypercube.

Physical Description:

v, 132 pages ; 26 cm

Place of Publication:

Providence, RI, USA : American Mathematical Society, [2024]

Contents:

Cover

Title page

Chapter 1. Introduction

1.1. Spanning subgraphs in hypercubes

1.2. Hamilton cycles in binomial random graphs

1.3. Hamilton cycles in binomial random subgraphs of the hypercube

1.4. Hitting time results

1.5. Randomly perturbed graphs

1.6. Percolation on the hypercube

1.7. Organisation of the paper

Chapter 2. Outline of the main proofs

2.1. Overall outline

2.2. Building block I: Trees via branching processes

2.3. Building block II: Cube tilings via the nibble

2.4. Constructing a long cycle

2.5. Constructing a Hamilton cycle

2.6. Hitting time for the appearance of a Hamilton cycle

2.7. Edge-disjoint Hamilton cycles

Chapter 3. Notation

Chapter 4. Probabilistic tools

Chapter 5. Auxiliary results

5.1. Results about matchings

5.2. Properties of random subgraphs of the hypercube

Chapter 6. Tiling random subgraphs of the hypercube with small cubes

6.1. The Rödl nibble

6.2. Iterating the nibble

Chapter 7. Near-spanning trees in random subgraphs of the hypercube

7.1. Constructing a bounded degree near-spanning tree

7.2. Extending the tree

7.3. The repatching lemma

Chapter 8. Hamilton cycles in randomly perturbed dense subgraphs of the hypercube

8.1. Layers, molecules, atoms, and absorbing structures

8.2. Bondless and bondlessly surrounded molecules

8.3. Connecting cubes

8.4. Proof of \cref{THM:MAIN1}

8.5. Proofs of \cref{THM:ALMOST,THM:MAIN,THM:THRESHOLDK}

Chapter 9. Hitting time result

9.1. Absorbing structures for vertices with small degree

9.2. Auxiliary lemmas

9.3. Hamilton cycles in robust subgraphs of the cube

9.4. Proofs of \cref{THM:KEDGEHIT} and \cref{THM:HITTING}

Bibliography

Index

Back Cover

Notes:

"December 2024, volume 304, number 1534 (seventh of 7 numbers)"

Includes bibliographical references (pages 127-129) and index.

ISBN:

9781470472665

147047266X

OCLC:

1503921483