Client-waiter games on complete and random graphs

zbMATH Open1353.05085arXiv1603.05429MaRDI QIDQ504971FDOQ504971

Authors: Oren Dean, Michael Krivelevich 

Publication date: 18 January 2017

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: For a graph G, a monotone increasing graph property P and positive integer q, we define the Client-Waiter game to be a two-player game which runs as follows. In each turn Waiter is offering Client a subset of at least one and at most q+1 unclaimed edges of G from which Client claims one, and the rest are claimed by Waiter. The game ends when all the edges have been claimed. If Client's graph has property P by the end of the game, then he wins the game, otherwise Waiter is the winner. In this paper we study several Client-Waiter games on the edge set of the complete graph, and the H-game on the edge set of the random graph. For the complete graph we consider games where Client tries to build a large star, a long path and a large connected component. We obtain lower and upper bounds on the critical bias for these games and compare them with the corresponding Waiter-Client games and with the probabilistic intuition. For the H-game on the random graph we show that the known results for the corresponding Maker-Breaker game are essentially the same for the Client-Waiter game, and we extend those results for the biased games and for trees.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Fast strategies in Waiter-Client games
• Waiter-client and client-waiter Hamiltonicity games on random graphs
• Waiter-Client and Client-Waiter planarity, colorability and minor games
• Manipulative waiters with probabilistic intuition
• Waiter-client clique-factor game

zbMATH Keywords

random graphcombinatorial gamesclient-waiter games

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Cites Work

• On the Distribution of the Number of Successes in Independent Trials
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random graphs.
• The size Ramsey number of a directed path
• Decomposition of Finite Graphs Into Forests
• On chooser-picker positional games
• Positional games and the second moment method
• On weight function methods in chooser-picker games
• Waiter-client and client-waiter Hamiltonicity games on random graphs
• Positional games
• Waiter-Client and Client-Waiter planarity, colorability and minor games
• Picker-chooser fixed graph games
• Regularity and Positional Games
• Hypergraph containers
• Manipulative Waiters with Probabilistic Intuition
• Combinatorial Games
• A Solution of the Shannon Switching Game
• On a combinatorial game
• Biased positional games for which random strategies are nearly optimal
• On the threshold for the maker-breaker \(H\)-game
• On the KŁR conjecture in random graphs
• The longest path in a random graph
• The phase transition in random graphs: a simple proof
• Biased positional games and the phase transition
• A threshold for the maker-breaker clique game
• Title not available (Why is that?)

Cited In (2)

• \(\boldsymbol{H}\)-Games Played on Vertex Sets of Random Graphs
• Finding and Using Expanders in Locally Sparse Graphs

This page was built for publication: Client-waiter games on complete and random graphs

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