Perfect Matchings in the Semirandom Graph Process

DOI10.1137/21M1446939zbMath1490.05247arXiv2105.13455OpenAlexW3170779178MaRDI QIDQ5864217

Calum MacRury, Paweł Prałat, Pu Gao

Publication date: 3 June 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2105.13455

zbMATH Keywords

random graphsperfect matchingssemirandom process

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Games on graphs (graph-theoretic aspects) (05C57)

Related Items

Power of \(k\) choices in the semi-random graph process, Sharp thresholds in adaptive random graph processes

Cites Work

• Unnamed Item
• Corrigendum to: ``Existence of a perfect matching in a random \((1+e^{-1})\)-out bipartite graph
• Hamilton cycles in the semi-random graph process
• Hamilton cycles in 3-out
• Semi‐random graph process
• Very fast construction of bounded-degree spanning graphs via the semi-random graph process