תקציר
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'. יחד הם יוצרים טביעת אצבע ייחודית.פורמט ציטוט ביבליוגרפי
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver