Picker-Chooser fixed graph games

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

doi:10.1016/j.jctb.2015.12.008

Picker-Chooser fixed graph games

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

نتاج البحث: نشر في مجلة › مقالة › مراجعة النظراء

9 اقتباسات (Scopus)

ملخص

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.

اللغة الأصلية	الإنجليزيّة
الصفحات (من إلى)	122-154
عدد الصفحات	33
دورية	Journal of Combinatorial Theory. Series B
مستوى الصوت	119
المعرِّفات الرقمية للأشياء	https://doi.org/10.1016/j.jctb.2015.12.008
حالة النشر	نُشِر - 1 يوليو 2016
منشور خارجيًا	نعم

الوصول إلى المستند

10.1016/j.jctb.2015.12.008

الملفات والروابط الأخرى

Link to publication in Scopus

قم بذكر هذا

@article{013f7b23d15b4ba88a42c5d473669a8f,

title = "Picker-Chooser fixed graph games",

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 Kn 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.",

keywords = "Counting subgraphs, Positional games, Probabilistic intuition, Random graphs, Talagrand's inequality, Threshold function",

author = "Ma{\l}gorzata Bednarska-Bzdȩga and Dan Hefetz and Tomasz {\L}uczak",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier Inc.",

year = "2016",

month = jul,

day = "1",

doi = "10.1016/j.jctb.2015.12.008",

language = "אנגלית",

volume = "119",

pages = "122--154",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Picker-Chooser fixed graph games

AU - Bednarska-Bzdȩga, Małgorzata

AU - Hefetz, Dan

AU - Łuczak, Tomasz

PY - 2016/7/1

Y1 - 2016/7/1

N2 - 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 Kn 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.

AB - 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 Kn 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.

KW - Counting subgraphs

KW - Positional games

KW - Probabilistic intuition

KW - Random graphs

KW - Talagrand's inequality

KW - Threshold function

UR - https://www.scopus.com/pages/publications/84953319379

U2 - 10.1016/j.jctb.2015.12.008

DO - 10.1016/j.jctb.2015.12.008

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:84953319379

SN - 0095-8956

VL - 119

SP - 122

EP - 154

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Picker-Chooser fixed graph games

ملخص

الوصول إلى المستند

الملفات والروابط الأخرى

بصمة

قم بذكر هذا