Manipulative waiters with probabilistic intuition

DOI10.1017/S0963548315000310zbMATH Open1378.91035arXiv1407.8391OpenAlexW2963951405MaRDI QIDQ5366922FDOQ5366922

Authors: Małgorzata Bednarska-Bzdȩga, Dan Hefetz, Michael Krivelevich, Tomasz Łuczak 

Publication date: 10 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: For positive integers $n$ and $q$ and a monotone graph property $cA$, we consider the two player, perfect information game $WC(n,q,cA)$, which is defined as follows. The game proceeds in rounds. In each round, the first player, called Waiter, offers the second player, called Client, $q+1$ edges of the complete graph $K_n$ which have not been offered previously. Client then chooses one of these edges which he keeps and the remaining $q$ edges go back to Waiter. If at the end of the game, the graph which consists of the edges chosen by Client satisfies the property $cA$, then Waiter is declared the winner; otherwise Client wins the game. In this paper we study such games (also known as Picker-Chooser games) for a variety of natural graph theoretic parameters, such as the size of a largest component or the length of a longest cycle. In particular, we describe a phase transition type phenomenon which occurs when the parameter $q$ is close to $n$ and is reminiscent of phase transition phenomena in random graphs. Namely, we prove that if $qleq(1-varepsilon)n$, then Client can avoid connected components of order $cvarepsilo{n}^{-2}lnn$ for some absolute constant $c>0$, whereas, for $qgeq(1+varepsilon)n$, Waiter can force a giant, linearly sized, connected component in Client's graph. We also prove that Waiter can force Client's graph to be pancyclic for every $qleqcn$, where $c>0$ is an appropriate constant.

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

Recommendations

• Waiter-client and client-waiter Hamiltonicity games on random graphs
• Client-waiter games on complete and random graphs
• Fast strategies in Waiter-Client games
• Waiter-client clique-factor game
• Waiter-Client and Client-Waiter planarity, colorability and minor games

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Games involving graphs (91A43) Combinatorial games (91A46)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Expanding graphs contain all small trees
• Paths in graphs
• On chooser-picker positional games
• Positional games and the second moment method
• On weight function methods in chooser-picker games
• Avoider-Enforcer games
• Positional games
• Picker-chooser fixed graph games
• Asymptotic random graph intuition for the biased connectivity game
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• Remarks on positional games. I
• Regularity and Positional Games
• Biased Positional Games
• Combinatorial Games
• A Solution of the Shannon Switching Game
• On a combinatorial game
• The picker-chooser diameter game
• Avoider-enforcer: the rules of the game
• Generating random graphs in biased maker-breaker games
• Hamiltonian circuits in random graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Title not available (Why is that?)
• Biased positional games and small hypergraphs with large covers
• The phase transition in random graphs: a simple proof
• Biased positional games and the phase transition
• Cycles in random graphs
• Title not available (Why is that?)

Cited In (10)

• Waiter-Client and Client-Waiter planarity, colorability and minor games
• On the odd cycle game and connected rules
• Finding and using expanders in locally sparse graphs
• Fast strategies in Waiter-Client games
• Waiter-client triangle-factor game on the edges of the complete graph
• 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
• Probabilistic intuition holds for a class of small subgraph games
• Waiter-client clique-factor game

This page was built for publication: Manipulative waiters with probabilistic intuition

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