Maker-Breaker games on randomly perturbed graphs

DOI10.1137/20M1385044MaRDI QIDQ5013573zbMATH OpenOpenAlexFDO

Authors Dennis Clemens, Fabian Hamann, Yannick Mogge, O. Parczyk

Publication date 1 December 2021

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

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

zbMATH Keywords

connectivityHamilton cyclepositional gamessubgraphsrandomly perturbed graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45) Connectivity (05C40) Games on graphs (graph-theoretic aspects) (05C57) Hypergraphs (05C65) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Abstract: Maker-Breaker games are played on a hypergraph $(X,mathcalF)$, where $mathcalFsubseteq{2}^X$ denotes the family of winning sets. Both players alternately claim a predefined amount of edges (called bias) from the board $X$, and Maker wins the game if she is able to occupy any winning set $FinmathcalF$. These games are well studied when played on the complete graph $K_n$ or on a random graph $G_{n,p}$. In this paper we consider Maker-Breaker games played on randomly perturbed graphs instead. These graphs consist of the union of a deterministic graph $G_{a}lpha$ with minimum degree at least $alphan$ and a binomial random graph $G_{n,p}$. Depending on $alpha$ and Breaker's bias $b$ we determine the order of the threshold probability for winning the Hamiltonicity game and the $k$-connectivity game on $G_{alpha}cup{G}_{n,p}$, and we discuss the $H$-game when $b=1$. Furthermore, we give optimal results for the Waiter-Client versions of all mentioned games.

Recommendations

• Positional games on random graphs
• Random-player maker-breaker games
• Biased games on random boards
• Connector-breaker games on random boards
• On the threshold for the maker-breaker \(H\)-game

Cites work

• scientific article; zbMATH DE number 437525 (Why is no real title available?)
• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 3549021 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• A sharp threshold for the Hamilton cycle Maker–Breaker game
• A threshold for the maker-breaker clique game
• Adding random edges to dense graphs
• Asymptotic random graph intuition for the biased connectivity game
• Bart--Moe games, JumbleG and discrepancy
• Biased Positional Games
• Biased games on random boards
• Biased positional games for which random strategies are nearly optimal
• Combinatorial Games
• Dependent random choice
• Factors in random graphs
• Generating random graphs in biased maker-breaker games
• Hamilton cycles in highly connected and expanding graphs
• Hamiltonian circuits in random graphs
• Hitting time results for maker-breaker games
• How many random edges make a dense graph hamiltonian?
• On smoothed analysis in dense graphs and formulas
• On the strength of connectedness of a random graph
• On the structure of linear graphs
• On the threshold for the maker-breaker \(H\)-game
• Playing to retain the advantage
• Positional games
• Positional games on random graphs
• Probability Inequalities for Sums of Bounded Random Variables
• Ramsey properties of randomly perturbed graphs: cliques and cycles
• Random graphs.
• Remarks on positional games. I
• Robust Hamiltonicity of Dirac graphs
• Some Theorems on Abstract Graphs
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• The threshold bias of the clique-factor game
• Tilings in randomly perturbed dense graphs
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu

Cited in

(13)

• Component games on regular graphs
• scientific article; zbMATH DE number 7069683 (Why is no real title available?)
• Maker-breaker games on random geometric graphs
• The Maker-Breaker Rado game on a random set of integers
• Maker-breaker percolation games. II: Escaping to infinity
• Maker-breaker domination game on trees when Staller wins
• Powers of Hamilton cycles in dense graphs perturbed by a random geometric graph
• Random-player maker-breaker games
• Doubly biased maker-breaker connectivity game
• Generating random graphs in biased maker-breaker games
• Maker–Breaker percolation games I: crossing grids
• Odd and even cycles in maker-breaker games
• On the threshold for the maker-breaker \(H\)-game

This page was built for publication: Maker-Breaker games on randomly perturbed graphs

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