The hitting time of clique factors

EUROCOMB’23

Annika Heckel Marc Kaufmann Noela Müller Matija Pasch

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-077

PDF
Abstract
In \cite{kahn2022hitting}, Kahn gave the strongest possible, affirmative, answer to Shamir‘s problem, which had been open since the late 1970s: Let $r \ge 3 $ and let $n$ be divisible by $r$. Then, in the random $r$-uniform hypergraph process on $n$ 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 $K_r$, the random graph process contains a $K_r$-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 $s$-uniform hypergraph process ($s \ge 3$).

Pages:
552–560
References

Noga Alon and Raphael Yuster. Threshold functions for H-factors. Combin. Probab. Comput., 2(2):137-144, 1993.
https://doi.org/10.1017/S0963548300000559

Béla Bollobás and Andrew Thomason. Random graphs of small order. In Random graphs '83 (Poznań, 1983), volume 118 of North-Holland Math. Stud., pages 47-97. North-Holland, Amsterdam, 1985.
https://doi.org/10.1016/S0304-0208(08)73612-0

Fan Chung and Ron Graham. Erdős on graphs: His legacy of unsolved problems. AK Peters/CRC Press, 1998.
https://doi.org/10.1201/9781439863879

Pat Devlin and Jeff Kahn. Perfect fractional matchings in k-out hypergraphs. Electron. J. Combin., 24(3):Paper No. 3.60, 12, 2017.
https://doi.org/10.37236/6890

Pál Erdős and Alfréd Rényi. On the existence of a factor of degree one of a connected random graph. Acta Math. Acad. Sci. Hungar., 17:359-368, 1966.
https://doi.org/10.1007/BF01894879

Pál Erdős. On the combinatorial problems which I would most like to see solved. Combinatorica, 1(1):25-42, 1981.
https://doi.org/10.1007/BF02579174

Alan Frieze and Svante Janson. Perfect matchings in random s-uniform hypergraphs. Random Structures & Algorithms, 7(1):41-57, 1995.
https://doi.org/10.1002/rsa.3240070104

Annika Heckel. Random triangles in random graphs. Random Structures & Algorithms, 59(4):616-621, 2021.
https://doi.org/10.1002/rsa.21013

Annika Heckel, Marc Kaufmann, Noela Müller, and Matija Pasch. The hitting time of clique factors. arXiv:2302.08340, 2023.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-077

Svante Janson, Tomasz Łuczak, and Andrzej Ruciński. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000.

Anders Johansson, Jeff Kahn, and Van Vu. Factors in random graphs. Random Structures Algorithms, 33(1):1-28, 2008.
https://doi.org/10.1002/rsa.20224

Jeff Kahn. Asymptotics for Shamir's problem. arXiv:1909.06834, 2019.

Jeff Kahn. Hitting times for Shamir's problem. Trans. Amer. Math. Soc., 375(1):627-668, 2022.
https://doi.org/10.1090/tran/8508

Jeong Han Kim. Perfect matchings in random uniform hypergraphs. Random Struct. Algorithms, 23(2):111-132, 2003.
https://doi.org/10.1002/rsa.10093

Michael Krivelevich. Triangle factors in random graphs. Combinatorics, Probability and Computing, 6:337 - 347, 1997.
https://doi.org/10.1017/S0963548397003106

Julius Petersen. Die theorie der regulären graphs. Acta Math., 15:193-220, 1891.
https://doi.org/10.1007/BF02392606

Oliver Riordan. Random cliques in random graphs and sharp thresholds for F -factors. Random Structures & Algorithms, 61(4):619-637, 2022.
https://doi.org/10.1002/rsa.21111

Andrzej Ruciński. Matching and covering the vertices of a random graph by copies of a given graph. Discrete Math., 105(1-3):185-197, 1992.
https://doi.org/10.1016/0012-365X(92)90141-2

Jeanette Schmidt and Eli Shamir. A threshold for perfect matchings in random d-pure hypergraphs. Discrete Mathematics, 45(2):287-295, 1983.
https://doi.org/10.1016/0012-365X(83)90044-4

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Annika Heckel, Marc Kaufmann, Noela Müller, Matija Pasch

PDF