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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

5 Downloads (Pure)

Samenvatting

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.)).

Originele taal-2	Engels
Pagina's (van-tot)	275-312
Aantal pagina's	38
Tijdschrift	Random Structures and Algorithms
Volume	65
Nummer van het tijdschrift	2
Vroegere onlinedatum	28 mrt. 2024
DOI's	https://doi.org/10.1002/rsa.21218
Status	Gepubliceerd - sep. 2024

Financiering

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.

Financiers	Financiernummer
European Research Council	772606
Vetenskapsrådet	2022‐02829
Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung	200021_192079
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	024.002.003

Toegang tot document

10.1002/rsa.21218

pdfDefinitieve gepubliceerde versie, 1,77 MBLicentie: CC BY

Andere bestanden en links

Link naar publicatie in Scopus

Citeer dit

@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 - http://www.scopus.com/inward/record.url?scp=85189551376&partnerID=8YFLogxK

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

Samenvatting

Financiering

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit