Picker-chooser fixed graph games

DOI10.1016/J.JCTB.2015.12.008MaRDI QIDQ273174zbMATH OpenOpenAlexFDO

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

Publication date 21 April 2016

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

counting subgraphspositional gamesprobabilistic intuitionrandom graphsTalagrand's inequalitythreshold function

Mathematics Subject Classification ID

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

Abstract: Given a fixed graph $H$ and a positive integer $n$, a Picker-Chooser $H$-game is a biased game played on the edge set of $K_n$ in which Picker is trying to force many copies of $H$ and Chooser is trying to prevent him from doing so. In this paper we conjecture that the value of the game is roughly the same as the expected number of copies of $H$ in the random graph $G(n,p)$ and prove our conjecture for special cases of $H$ such as complete graphs and trees.

Recommendations

• The picker-chooser diameter game
• On weight function methods in chooser-picker games
• Biased positional games for which random strategies are nearly optimal
• On chooser-picker positional games
• On the threshold for the maker-breaker H-game

Cites work

• Avoider-Enforcer games
• Avoider-enforcer: the rules of the game
• Avoiding small subgraphs in Achlioptas processes
• Biased positional games for which random strategies are nearly optimal
• Combinatorial Games
• Concentration of measure and isoperimetric inequalities in product spaces
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Offline thresholds for Ramsey-type games on random graphs
• On chooser-picker positional games
• On weight function methods in chooser-picker games
• Positional games and the second moment method
• Remarks on positional games. I
• Small subgraphs in random graphs and the power of multiple choices
• Threshold functions for small subgraphs
• When are small subgraphs of a random graph normally distributed?

Cited in

(14)

• On chooser-picker positional games
• On weight function methods in chooser-picker games
• Waiter-client clique-factor game
• On the odd cycle game and connected rules
• Waiter-client and client-waiter Hamiltonicity games on random graphs
• Waiter-client and client-waiter colourability and \(k\)-SAT games
• Waiter-Client and Client-Waiter planarity, colorability and minor games
• On the complexity of chooser-picker positional games
• Sharp thresholds for half-random games. I.
• Client-waiter games on complete and random graphs
• Manipulative waiters with probabilistic intuition
• Probabilistic intuition holds for a class of small subgraph games
• \(\boldsymbol{H}\)-Games Played on Vertex Sets of Random Graphs
• The picker-chooser diameter game

This page was built for publication: Picker-chooser fixed graph games

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