Picker-chooser fixed graph games

DOI10.1016/J.JCTB.2015.12.008zbMATH Open1334.05086arXiv1402.7308OpenAlexW2227260335MaRDI QIDQ273174FDOQ273174

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)

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.

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

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

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)

Cites Work

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

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
• Manipulative waiters with probabilistic intuition
• On weight function methods in chooser-picker games
• 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)