Maker-Breaker games on randomly perturbed graphs

DOI10.1137/20M1385044zbMATH Open1479.05224arXiv2009.14583OpenAlexW3212807627MaRDI QIDQ5013573FDOQ5013573

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)

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.

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

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

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)

Cites Work

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

Cited In (13)

• 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
• Component games on regular graphs
• Title not available (Why is that?)
• Maker-breaker games on random geometric graphs
• The Maker-Breaker Rado game on a random set of integers

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)