On the threshold for the maker-breaker H-game

DOI10.1002/RSA.20628MaRDI QIDQ2830239zbMATHOpenAlexFDO

Authors Rajko Nenadov, Angelika Steger, Miloš Stojaković

Publication date 9 November 2016

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

random graphspositional gamesmaker-breaker game

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) 2-person games (91A05) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Abstract: We study the Maker-Breaker $H$-game played on the edge set of the random graph $G_{n,p}$. In this game two players, Maker and Breaker, alternately claim unclaimed edges of $G_{n,p}$, until all the edges are claimed. Maker wins if he claims all the edges of a copy of a fixed graph $H$; Breaker wins otherwise. In this paper we show that, with the exception of trees and triangles, the threshold for an $H$-game is given by the threshold of the corresponding Ramsey property of $G_{n,p}$ with respect to the graph $H$.

Recommendations

• A threshold for the maker-breaker clique game
• A threshold for the maker-breaker clique game
• Positional games on random graphs
• A sharp threshold for the Hamilton cycle Maker–Breaker game
• Maker-Breaker games on randomly perturbed graphs

Cites work

• scientific article; zbMATH DE number 524135 (Why is no real title available?)
• A short proof of the random Ramsey theorem
• A threshold for the maker-breaker clique game
• Avoider-Enforcer games
• Biased positional games and small hypergraphs with large covers
• Biased positional games for which random strategies are nearly optimal
• Decomposition of Finite Graphs Into Forests
• Hypergraph containers
• Independent sets in hypergraphs
• On a combinatorial game
• Positional games
• Positional games on random graphs
• Random graphs with monochromatic triangles in every edge coloring
• Threshold Functions for Ramsey Properties
• Threshold functions
• Threshold functions for small subgraphs

Cited in

(26)

• Picker-chooser fixed graph games
• Walker-breaker games
• Connector-breaker games on random boards
• scientific article; zbMATH DE number 7069683 (Why is no real title available?)
• Maker-Breaker games on randomly perturbed graphs
• Playing to retain the advantage
• Complexity of maker-breaker games on edge sets of graphs
• \(\boldsymbol{H}\)-Games Played on Vertex Sets of Random Graphs
• Waiter-client triangle-factor game on the edges of the complete graph
• Creating cycles in walker-breaker games
• An algorithmic framework for obtaining lower bounds for random Ramsey problems
• Shutout games on graphs
• Maker-breaker games on random geometric graphs
• Maker-breaker percolation games. II: Escaping to infinity
• A sharp threshold for the Hamilton cycle Maker–Breaker game
• Positional games and the second moment method
• Symmetric and asymmetric Ramsey properties in random hypergraphs
• Ramsey, paper, scissors
• Multistage positional games
• Hitting time results for maker-breaker games (extended abstract)
• Hitting time results for maker-breaker games
• Playing to retain the advantage
• The Maker-Breaker Rado game on a random set of integers
• Client-waiter games on complete and random graphs
• Fast strategies in Waiter-Client games
• Probabilistic intuition holds for a class of small subgraph games

This page was built for publication: On the threshold for the maker-breaker \(H\)-game

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