Name
Abstract | ||
|---|---|---|
We study biased Maker-Breaker games on the edges of the complete graph, as introduced by Chvátal and Erdős. We show that Maker, occupying one edge in each of his turns, can build a spanning tree, even if Breaker occupies b ≤ (1 - o(1)) · $ {n \over \ln n} $ edges in each turn. This improves a result of Beck, and is asymptotically best possible as witnessed by the Breaker-strategy of Chvátal and Erdős. We also give a strategy for Maker to occupy a graph with minimum degree c (where c = c(n) is a slowly growing function of n) while playing against a Breaker who takes b ≤ (1 - o(1)) · $ {n \over \ln n} $ edges in each turn. This result improves earlier bounds by Krivelevich and Szabó. Both of our results support the surprising random graph intuition: the threshold bias is asymptotically the same for the game played by two “clever” players and the game played by two “random” players. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1002/rsa.v35:4 | Random Struct. Algorithms |
Keywords | Field | DocType |
random graph,spanning tree,complete graph,connectivity,random graphs | Discrete mathematics,Geometric graph theory,Complete graph,Random regular graph,Combinatorics,Line graph,Minimum degree spanning tree,Random graph,Degree (graph theory),Mathematics,Complement graph | Journal |
Volume | Issue | ISSN |
35 | 4 | 1042-9832 |
Citations | PageRank | References |
20 | 1.32 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Heidi Gebauer | 1 | 83 | 11.07 |
| Tibor Szabó | 2 | 420 | 45.51 |