Perfect matchings and loose Hamilton cycles in the semirandom hypergraph model

Molloy, Michael, Pralat, Pawel and Sorkin, Gregory B. (2025) Perfect matchings and loose Hamilton cycles in the semirandom hypergraph model. Random Structures and Algorithms, 66 (2). ISSN 1042-9832

Text (Random Struct Algorithms - 2025 - Molloy - Perfect Matchings and Loose Hamilton Cycles in the Semirandom Hypergraph Model) - Published Version Available under License Creative Commons Attribution. Download (410kB)

• Scopus publication

Abstract

We study the 2-offer semirandom 3-uniform hypergraph model on n vertices. At each step, we are presented with 2 uniformly random vertices. We choose any other vertex, thus creating a hyperedge of size 3. We show a strategy that constructs a perfect matching, and another that constructs a loose Hamilton cycle, both succeeding asymptotically almost surely within Θ(n) steps. Both results extend to s-uniform hypergraphs. Our methods are qualitatively different from those that have been used for semirandom graphs. Much of the analysis is done on an auxiliary graph that is a uniform k-out subgraph of a random bipartite graph, and this tool may be useful in other contexts.

Item Type:	Article
Additional Information:	© 2025 The Author(s)
Divisions:	Mathematics
Subjects:	Q Science > QA Mathematics
Date Deposited:	30 Oct 2024 15:06
Last Modified:	26 Sep 2025 20:24
URI:	http://eprintstest.lse.ac.uk/id/eprint/125930

Actions (login required)

View Item