Back to Search Start Over

Picker–Chooser fixed graph games

Authors :
Dan Hefetz
Tomasz Łuczak
Małgorzata Bednarska-Bzdęga
Source :
Journal of Combinatorial Theory, Series B. 119:122-154
Publication Year :
2016
Publisher :
Elsevier BV, 2016.

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 classes of graphs H such as complete graphs and trees.

Details

ISSN :
00958956
Volume :
119
Database :
OpenAIRE
Journal :
Journal of Combinatorial Theory, Series B
Accession number :
edsair.doi...........c564b58bf87e6a3027156dbbe85bea3f
Full Text :
https://doi.org/10.1016/j.jctb.2015.12.008