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

random graphsthreshold functioncounting subgraphspositional gamesprobabilistic intuitionTalagrand's inequality

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• 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
• 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)

• Waiter-Client and Client-Waiter planarity, colorability and minor games
• On the odd cycle game and connected rules
• The picker-chooser diameter game
• Sharp thresholds for half-random games. I.
• On chooser-picker positional games
• On the complexity of chooser-picker positional games
• On weight function methods in chooser-picker games
• 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
• \(\boldsymbol{H}\)-Games Played on Vertex Sets of Random Graphs
• Probabilistic intuition holds for a class of small subgraph games
• Waiter-client clique-factor 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)