Hostname: page-component-6bf8c574d5-9nwgx Total loading time: 0 Render date: 2025-02-16T15:58:44.676Z Has data issue: false hasContentIssue false
  • English
  • Français

Spanning $F$-cycles in random graphs

Part of: Graph theory

Published online by Cambridge University Press:  09 June 2023

Alberto Espuny Díaz Open the ORCID record for Alberto Espuny Díaz [Opens in a new window]  and
Yury Person Open the ORCID record for Yury Person [Opens in a new window]
Alberto Espuny Díaz*
Affiliation:
Institut für Mathematik, Technische Universität Ilmenau, Ilmenau, Germany
Yury Person
Affiliation:
Institut für Mathematik, Technische Universität Ilmenau, Ilmenau, Germany
*
Corresponding author: Alberto Espuny Díaz; Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We extend a recent argument of Kahn, Narayanan and Park ((2021) Proceedings of the AMS 149 3201–3208) about the threshold for the appearance of the square of a Hamilton cycle to other spanning structures. In particular, for any spanning graph, we give a sufficient condition under which we may determine its threshold. As an application, we find the threshold for a set of cyclically ordered copies of $C_4$ that span the entire vertex set, so that any two consecutive copies overlap in exactly one edge and all overlapping edges are disjoint. This answers a question of Frieze. We also determine the threshold for edge-overlapping spanning $K_r$-cycles.

Keywords

Random graphsthresholdspanning subgraph

MSC classification

Primary: 05C80: Random graphs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 32 , Issue 5 , September 2023 , pp. 833 - 850
Check for updates
Copyright
© The Author(s), 2023. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alweiss, R., Lovett, S., Wu, K. and Zhang, J. (2020) Improved bounds for the sunflower lemma, pp. 624–630, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Association for Computing Machinery, New York, NY, USA. doi: 10.1145/3357713.3384234, ISBN 9781450369794.CrossRefGoogle Scholar
Bell, T. and Frieze, A. (2022) Rainbow powers of a Hamilton cycle in $G_{n,p}$ . arXiv e-prints. arXiv: 2210.08534.Google Scholar
Bell, T., Frieze, A. and Marbach, T. G. (2021) Rainbow thresholds. arXiv e-prints. arXiv: 2104.05629.Google Scholar
Bollobás, B. (1981) Threshold functions for small subgraphs. Math. Proc. Camb. Philos. Soc. 90(2) 197–206. doi: 10.1017/S0305004100058655.CrossRefGoogle Scholar
Böttcher, J. (2017) Large-scale structures in random graphs. Surveys in combinatorics 2017, University of Strathclyde, Glasgow, UK, Cambridge: Cambridge University Press, pp. 87–140, Papers Based on the 26th British Combinatorial Conference, ISBN 978-1-108-41313-8/pbk; 978-1-108-33103-6/ebook.CrossRefGoogle Scholar
Erdős, P. and Rényi, A. (1960) On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. Ser. A 5 17–61. doi: 10.1515/9781400841356.38.Google Scholar
Erdős, P. and Rényi, A. (1966) On the existence of a factor of degree one of a connected random graph. Acta Math. Acad. Sci. Hungar. 17(3-4) 359–368. doi: 10.1007/BF01894879.CrossRefGoogle Scholar
Frankston, K., Kahn, J., Narayanan, B. and Park, J. (2021) Thresholds versus fractional expectation-thresholds. Ann. Math. 194(2) 475–495. doi: 10.4007/annals.2021.194.2.2.CrossRefGoogle Scholar
Friedgut, E. (2005) Hunting for sharp thresholds. Random Struct. Algorithms 26(1-2) 37–51. doi: 10.1002/rsa.20042.CrossRefGoogle Scholar
Frieze, A. (2020) A note on spanning $K_r$ -cycles in random graphs. AIMS Math. 5(5) 4849–4852. doi: 10.3934/math.2020309.CrossRefGoogle Scholar
Heckel, A. (2021) Random triangles in random graphs. Random Struct. Algorithms 59(4) 616–621. doi: 10.1002/rsa.21013.CrossRefGoogle Scholar
Janson, S., Łuczak, T. and Ruciński, A. (2000) Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization. New York, Wiley-Interscience. doi: 10.1002/9781118032718, ISBN 0-471-17541-2.Google Scholar
Johansson, A., Kahn, J. and Vu, V. (2008) Factors in random graphs. Random Struct. Algorithms 33(1) 1–28. doi: 10.1002/rsa.20224.CrossRefGoogle Scholar
Kahn, J. and Kalai, G. (2007) Thresholds and expectation thresholds. Combin. Probab. Comput. 16(3) 495–502. doi: 10.1017/S0963548307008474.CrossRefGoogle Scholar
Kahn, J., Narayanan, B. and Park, J. (2021) The threshold for the square of a Hamilton cycle. Proc. Am. Math. Soc. 149(8) 3201–3208. doi: 10.1090/proc/15419.CrossRefGoogle Scholar
Koršunov, A. D. (1977) Solution of a problem of P. Erdős and A. Rényi on Hamiltonian cycles in undirected graphs. Metody Diskretn. Anal. 31 17–56.Google Scholar
Kühn, D. and Osthus, D. (2012) On Pósa’s conjecture for random graphs. SIAM J. Discrete Math. 26(3) 1440–1457. doi: 10.1137/120871729.CrossRefGoogle Scholar
Montgomery, R. (2019) Spanning trees in random graphs. Adv. Math. 356 92pp. doi:10.1016/j.aim.2019.106793. Id/No 106 793.CrossRefGoogle Scholar
Narayanan, B. and Schacht, M. (2020) Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs. Random Struct. Algorithms 57(1) 244–255. doi: 10.1002/rsa.20919.CrossRefGoogle Scholar
Parczyk, O. and Person, Y. (2016) Spanning structures and universality in sparse hypergraphs. Random Struct. Algorithms 49(4) 819–844. doi: 10.1002/rsa.20690.CrossRefGoogle Scholar
Park, J. and Pham, H. T. (2022) A proof of the Kahn-Kalai conjecture, Journal of the American Mathematical Society, to appearGoogle Scholar
Pósa, L. (1976) Hamiltonian circuits in random graphs. Discrete Math. 14(4) 359–364. doi: 10.1016/0012-365X(76)90068-6.CrossRefGoogle Scholar
Riordan, O. (2000) Spanning subgraphs of random graphs. Combin. Probab. Comput. 9(2) 125–148. doi: 10.1017/S0963548399004150.CrossRefGoogle Scholar
Riordan, O. (2022) Random cliques in random graphs and sharp thresholds for $F$ -factors. Random Struct. Algorithms 61(4) 619–637. doi 10.1002/rsa.21111.CrossRefGoogle Scholar
Spiro, S. (2021) A smoother notion of spread hypergraphs. arXiv e-prints. arXiv: 2106.11882.Google Scholar
Talagrand, M. (2010) Are many small sets explicitly small? Association for Computing Machinery (ACM), New York, NY, pp. 13–36, Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, STOC’10, June 5-8, 2010, Cambridge, MA, USA, ISBN 978-1-60558-817-9.Google Scholar