2021/06/18 by Alberto Espuny Díaz, Díaz, Alberto Espuny, Yury Person +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2106.10023
openalex publication_date 2021/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We extend a recent argument of Kahn, Narayanan and Park (Proceedings of the AMS, to appear) 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 C4 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 Kr-cycles.