Fast strategies in Waiter-Client games

DOI10.37236/9451zbMATH Open1448.05141arXiv2003.09247OpenAlexW3104046156MaRDI QIDQ2200433FDOQ2200433

Authors: Yanyan Li 

Publication date: 21 September 2020

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

Abstract: Waiter-Client games are played on some hypergraph $(X,mathcalF)$, where $mathcalF$ denotes the family of winning sets. For some bias $b$, during each round of such a game Waiter offers to Client $b+1$ elements of $X$, of which Client claims one for himself while the rest go to Waiter. Proceeding like this Waiter wins the game if she forces Client to claim all the elements of any winning set from $mathcalF$. In this paper we study fast strategies for several Waiter-Client games played on the edge set of the complete graph, i.e. $X=E(K_n)$, in which the winning sets are perfect matchings, Hamilton cycles, pancyclic graphs, fixed spanning trees or factors of a given graph.

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

Recommendations

• Client-waiter games on complete and random graphs
• Waiter-client and client-waiter Hamiltonicity games on random graphs
• Waiter-Client and Client-Waiter planarity, colorability and minor games
• Waiter-client clique-factor game
• Waiter-client triangle-factor game on the edges of the complete graph

zbMATH Keywords

strong gamesperfect matching game

Mathematics Subject Classification ID

Trees (05C05) 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

• Pancyclic graphs. I
• On chooser-picker positional games
• On weight function methods in chooser-picker games
• Positional games
• Asymptotic random graph intuition for the biased connectivity game
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• Biased Positional Games
• 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 two problems regarding the Hamiltonian cycle game
• Weak and strong \(k\)-connectivity games
• Fast winning strategies in maker-breaker games
• On the threshold for the maker-breaker \(H\)-game
• Generating random graphs in biased maker-breaker games
• Positional games on random graphs
• Hamiltonian circuits in random graphs
• Embedding spanning trees in random graphs
• Doubly biased maker-breaker connectivity game
• Fast embedding of spanning trees in biased maker-breaker games
• Fast strategies in biased Maker-Breaker games
• How fast can maker win in fair biased games?
• Building spanning trees quickly in maker-breaker games

Cited In (8)

• Waiter-Client and Client-Waiter planarity, colorability and minor games
• On winning fast in Avoider-Enforcer games
• Waiter-client triangle-factor game on the edges of the complete graph
• Manipulative waiters with probabilistic intuition
• Waiter-client and client-waiter colourability and \(k\)-SAT games
• Waiter-client and client-waiter Hamiltonicity games on random graphs
• Client-waiter games on complete and random graphs
• Waiter-client clique-factor game

This page was built for publication: Fast strategies in Waiter-Client games

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