דילוג לניווט ראשי דילוג לחיפוש דילוג לתוכן הראשי

A sharp threshold for the hamilton cycle Maker-Breaker game

  • Dan Hefetz
  • , Michael Krivelevich
  • , Miloš Stojakovič
  • , Tibor Szabó

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

21 ציטוטים ‏(Scopus)

תקציר

We study the Hamilton cycle Maker-Breaker game, played on the edges of the random graph G(n,p). We prove a conjecture from (Stojaković and Szabó, Random Struct and Algorithms 26 (2005), 204-223.), asserting that the property that Maker is able to win this game, has a sharp threshold at log n/n. Our theorem can be considered a game-theoretic strengthening of classical results from the theory of random graphs: not only does G(n,p) almost surely admit a Hamilton cycle for p = (1 + ε) log n/n, but Maker is able to build one while playing against an adversary.

שפה מקוריתאנגלית
עמודים (מ-עד)112-122
מספר עמודים11
כתב עתRandom Structures and Algorithms
כרך34
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - ינו׳ 2009
פורסם באופן חיצוניכן

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'A sharp threshold for the hamilton cycle Maker-Breaker game'. יחד הם יוצרים טביעת אצבע ייחודית.

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