Positional games on random graphs
| dc.creator | Stojakovic, Milos | |
| dc.creator | Szabo, Tibor | |
| dc.date | 2006-01-26 | |
| dc.date.accessioned | 2026-07-07T06:59:21Z | |
| dc.date.available | 2026-07-07T06:59:21Z | |
| dc.description | We introduce and study Maker/Breaker-type positional games on random graphs. Our main concern is to determine the threshold probability $p_{F}$ for the existence of Maker's strategy to claim a member of $F$ in the unbiased game played on the edges of random graph $G(n,p)$, for various target families $F$ of winning sets. More generally, for each probability above this threshold we study the smallest bias $b$ such that Maker wins the $(1\:b)$ biased game. We investigate these functions for a number of basic games, like the connectivity game, the perfect matching game, the clique game and the Hamiltonian cycle game. | |
| dc.identifier | https://arxiv.org/abs/math/0601659 | |
| dc.identifier | http://arxiv.org/abs/math/0601659 | |
| dc.identifier | Random Structures & Algorithms 26 (2005), 204-223 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/107717 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.subject | 91A24; 05C80 | |
| dc.title | Positional games on random graphs | |
| dc.type | text |