On the threshold for the maker-breaker H-game

DOI10.1002/RSA.20628zbMATH Open1349.05316arXiv1401.4384OpenAlexW2593199250MaRDI QIDQ2830239FDOQ2830239

Authors: Rajko Nenadov, Angelika Steger, Miloš Stojaković 

Publication date: 9 November 2016

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

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$.

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

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

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)

Cites Work

• Threshold functions for small subgraphs
• Decomposition of Finite Graphs Into Forests
• Avoider-Enforcer games
• Positional games
• Hypergraph containers
• Independent sets in hypergraphs
• On a combinatorial game
• Biased positional games for which random strategies are nearly optimal
• Positional games on random graphs
• Threshold functions
• Threshold Functions for Ramsey Properties
• Title not available (Why is that?)
• Random graphs with monochromatic triangles in every edge coloring
• Biased positional games and small hypergraphs with large covers
• A threshold for the maker-breaker clique game
• A Short Proof of the Random Ramsey Theorem

Cited In (20)

• Playing to retain the advantage
• An algorithmic framework for obtaining lower bounds for random Ramsey problems
• Maker-breaker percolation games. II: Escaping to infinity
• Multistage positional games
• Creating cycles in walker-breaker games
• Fast strategies in Waiter-Client games
• Waiter-client triangle-factor game on the edges of the complete graph
• Positional games and the second moment method
• SYMMETRIC AND ASYMMETRIC RAMSEY PROPERTIES IN RANDOM HYPERGRAPHS
• Connector-breaker games on random boards
• The Maker--Breaker Rado Game on a Random Set of Integers
• Maker-Breaker Games on Randomly Perturbed Graphs
• Maker‐breaker games on random geometric graphs
• Complexity of maker-breaker games on edge sets of graphs
• Hitting time results for maker-breaker games
• Client-waiter games on complete and random graphs
• \(\boldsymbol{H}\)-Games Played on Vertex Sets of Random Graphs
• A sharp threshold for the Hamilton cycle Maker–Breaker game
• Probabilistic intuition holds for a class of small subgraph games
• Title not available (Why is that?)

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)