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

פרסום מחקרי: פרסום בכתב עת › מאמר › ביקורת עמיתים

8 ציטוטים ‏(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
מזהי עצם דיגיטלי (DOIs)	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 - http://www.scopus.com/inward/record.url?scp=84953319379&partnerID=8YFLogxK

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

תקציר

גישה למסמך

קבצים וקישורים אחרים

טביעת אצבע

פורמט ציטוט ביבליוגרפי