The hitting time of clique factors

Annika Heckel; Marc Kaufmann; Noela Müller; Matija Pasch

doi:10.1002/rsa.21218

The hitting time of clique factors

Annika Heckel
, Marc Kaufmann (Corresponding author)
, Noela Müller
, Matija Pasch

Probability

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

120 Downloads (Pure)

Abstract

In [Trans. Am. Math. Soc. 375 (2022), no. 1, 627–668], Kahn gave the strongest possible, affirmative, answer to Shamir's problem, which had been open since the late 1970s: Let (Formula presented.) and let (Formula presented.) be divisible by (Formula presented.). Then, in the random (Formula presented.) -uniform hypergraph process on (Formula presented.) vertices, as soon as the last isolated vertex disappears, a perfect matching emerges. In the present work, we prove the analogue of this result for clique factors in the random graph process: at the time that the last vertex joins a copy of the complete graph (Formula presented.), the random graph process contains a (Formula presented.) -factor. Our proof draws on a novel sequence of couplings which embeds the random hypergraph process into the cliques of the random graph process. An analogous result is proved for clique factors in the (Formula presented.) -uniform hypergraph process ((Formula presented.)).

Original language	English
Pages (from-to)	275-312
Number of pages	38
Journal	Random Structures and Algorithms
Volume	65
Issue number	2
Early online date	28 Mar 2024
DOIs	https://doi.org/10.1002/rsa.21218
Publication status	Published - Sept 2024

Funding

This project was initiated during the research workshop of Angelika Steger's group in Buchboden, August 2021. We are grateful to Oliver Riordan for a helpful discussion. The research leading to these results has received funding from the European Research Council, ERC grant agreement 772606\u2013PTRCSP, and from the Swedish Research Council, Reg. no. 2022\u201002829. The author gratefully acknowledges support by the Swiss National Science Foundation [grant number 200021_192079]. Research supported by NWO Gravitation project NETWORKS under grant no. 024.002.003. Open access funding provided by Eidgenossische Technische Hochschule Zurich.

Keywords

clique factor
hitting time
hypergraphs
perfect matching
random graphs

Access to Document

10.1002/rsa.21218

pdfFinal published version, 1.77 MBLicence: CC BY

Cite this

@article{df24a3f7571b49c3b85022b4952c28f4,

title = "The hitting time of clique factors",

abstract = "In [Trans. Am. Math. Soc. 375 (2022), no. 1, 627–668], Kahn gave the strongest possible, affirmative, answer to Shamir's problem, which had been open since the late 1970s: Let (Formula presented.) and let (Formula presented.) be divisible by (Formula presented.). Then, in the random (Formula presented.) -uniform hypergraph process on (Formula presented.) vertices, as soon as the last isolated vertex disappears, a perfect matching emerges. In the present work, we prove the analogue of this result for clique factors in the random graph process: at the time that the last vertex joins a copy of the complete graph (Formula presented.), the random graph process contains a (Formula presented.) -factor. Our proof draws on a novel sequence of couplings which embeds the random hypergraph process into the cliques of the random graph process. An analogous result is proved for clique factors in the (Formula presented.) -uniform hypergraph process ((Formula presented.)).",

keywords = "clique factor, hitting time, hypergraphs, perfect matching, random graphs",

author = "Annika Heckel and Marc Kaufmann and Noela M{\"u}ller and Matija Pasch",

year = "2024",

month = sep,

doi = "10.1002/rsa.21218",

language = "English",

volume = "65",

pages = "275--312",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "Wiley",

number = "2",

}

TY - JOUR

T1 - The hitting time of clique factors

AU - Heckel, Annika

AU - Kaufmann, Marc

AU - Müller, Noela

AU - Pasch, Matija

PY - 2024/9

Y1 - 2024/9

N2 - In [Trans. Am. Math. Soc. 375 (2022), no. 1, 627–668], Kahn gave the strongest possible, affirmative, answer to Shamir's problem, which had been open since the late 1970s: Let (Formula presented.) and let (Formula presented.) be divisible by (Formula presented.). Then, in the random (Formula presented.) -uniform hypergraph process on (Formula presented.) vertices, as soon as the last isolated vertex disappears, a perfect matching emerges. In the present work, we prove the analogue of this result for clique factors in the random graph process: at the time that the last vertex joins a copy of the complete graph (Formula presented.), the random graph process contains a (Formula presented.) -factor. Our proof draws on a novel sequence of couplings which embeds the random hypergraph process into the cliques of the random graph process. An analogous result is proved for clique factors in the (Formula presented.) -uniform hypergraph process ((Formula presented.)).

AB - In [Trans. Am. Math. Soc. 375 (2022), no. 1, 627–668], Kahn gave the strongest possible, affirmative, answer to Shamir's problem, which had been open since the late 1970s: Let (Formula presented.) and let (Formula presented.) be divisible by (Formula presented.). Then, in the random (Formula presented.) -uniform hypergraph process on (Formula presented.) vertices, as soon as the last isolated vertex disappears, a perfect matching emerges. In the present work, we prove the analogue of this result for clique factors in the random graph process: at the time that the last vertex joins a copy of the complete graph (Formula presented.), the random graph process contains a (Formula presented.) -factor. Our proof draws on a novel sequence of couplings which embeds the random hypergraph process into the cliques of the random graph process. An analogous result is proved for clique factors in the (Formula presented.) -uniform hypergraph process ((Formula presented.)).

KW - clique factor

KW - hitting time

KW - hypergraphs

KW - perfect matching

KW - random graphs

UR - https://www.scopus.com/pages/publications/85189551376

U2 - 10.1002/rsa.21218

DO - 10.1002/rsa.21218

M3 - Article

SN - 1042-9832

VL - 65

SP - 275

EP - 312

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 2

ER -

The hitting time of clique factors

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this