Perfect Matchings and Loose Hamilton Cycles in the Semirandom Hypergraph Model

Authors:
Open Access
Publisher website
Google Scholar
Abstract
We study the 2‐offer semirandom 3‐uniform hypergraph model on 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 steps. Both results extend to ‐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 ‐out subgraph of a random bipartite graph, and this tool may be useful in other contexts.
Funding Information
  • Natural Sciences and Engineering Research Council of Canada (RGPIN‐2022‐03804, RGPIN‐2019‐06522)

This publication has 17 references indexed in Scilit: