Perfect matchings in the semirandom graph process

DOI10.1137/21M1446939MaRDI QIDQ5864217zbMATH OpenOpenAlexFDO

Authors Pu Gao, Calum MacRury, Paweł Prałat

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

perfect matchingsrandom graphssemirandom process

Mathematics Subject Classification ID

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

Abstract: The semi-random graph process is a single player game in which the player is initially presented an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the player independently and uniformly at random. The player then adaptively selects a vertex $v$, and adds the edge $uv$ to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a perfect matching in as few rounds as possible. In particular, we present an adaptive strategy for the player which achieves a perfect matching in $$ rounds, where the value of $$ is derived from a solution to some system of differential equations. This improves upon the previously best known upper bound of $(1+2/e+o(1)),n<1.736,n$ rounds. We also improve the previously best lower bound of $(ln2+o(1)),n>0.693,n$ and show that the player cannot achieve the desired property in less than $alphan$ rounds, where the value of $alpha>0.932$ is derived from a solution to another system of differential equations. As a result, the gap between the upper and lower bounds is decreased roughly four times.

Recommendations

• Hamilton cycles in the semi-random graph process
• Semi-random process without replacement
• Semi-random graph process
• Very fast construction of bounded-degree spanning graphs via the semi-random graph process
• Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process

Cites work

• Corrigendum to: ``Existence of a perfect matching in a random \((1+e^{-1})\)-out bipartite graph
• Hamilton cycles in 3-out
• Hamilton cycles in the semi-random graph process
• scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• Semi-random graph process
• Very fast construction of bounded-degree spanning graphs via the semi-random graph process

Cited in

(15)

• A Fast Perfect-Matching Algorithm in Random Graphs
• On the switch Markov chain for perfect matchings
• Semi-random graph process
• Very fast construction of bounded-degree spanning graphs via the semi-random graph process
• Exact matching of random graphs with constant correlation
• Power of \(k\) choices in the semi-random graph process
• Sharp thresholds in adaptive random graph processes
• Cliques, chromatic number, and independent sets in the semi-random process
• Subgraph games in the semi-random graph process and its generalization to hypergraphs
• Creating subgraphs in semi-random hypergraph games
• Fast construction on a restricted budget
• Perfect matchings and loose Hamilton cycles in the semirandom hypergraph model
• Building Hamiltonian cycles in the semi-random graph process in less than 2n rounds
• The semi-random tree process
• On the pre- and post-positional semi-random graph processes

This page was built for publication: Perfect matchings in the semirandom graph process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5864217)