Fast strategies in Waiter-Client games

DOI10.37236/9451MaRDI QIDQ2200433zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 21 September 2020

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

• A Solution of the Shannon Switching Game
• Asymptotic random graph intuition for the biased connectivity game
• Biased Positional Games
• Biased positional games for which random strategies are nearly optimal
• Building spanning trees quickly in maker-breaker games
• Combinatorial Games
• Doubly biased maker-breaker connectivity game
• Embedding spanning trees in random graphs
• Fast embedding of spanning trees in biased maker-breaker games
• Fast strategies in biased Maker-Breaker games
• Fast winning strategies in maker-breaker games
• Generating random graphs in biased maker-breaker games
• Hamiltonian circuits in random graphs
• How fast can maker win in fair biased games?
• Manipulative waiters with probabilistic intuition
• On a combinatorial game
• On chooser-picker positional games
• On the threshold for the maker-breaker \(H\)-game
• On two problems regarding the Hamiltonian cycle game
• On weight function methods in chooser-picker games
• Pancyclic graphs. I
• Positional games
• Positional games on random graphs
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• Weak and strong \(k\)-connectivity games

Cited in

(8)

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

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)