## 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 | |

Publication status | E-pub ahead of print - 28 Mar 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.

Funders | Funder number |
---|---|

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 |

## Keywords

- clique factor
- hitting time
- hypergraphs
- perfect matching
- random graphs