Available in electronic format
Available in print format
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826 (e) ISSN 0002-9939 (p)
     

Product rule wins a competitive game

Author(s): Andrew Beveridge; Tom Bohman; Alan Frieze; Oleg Pikhurko
Journal: Proc. Amer. Math. Soc. 135 (2007), 3061-3071.
MSC (2000): Primary 05C80
Posted: May 14, 2007
Retrieve article in: PDF DVI PostScript

Abstract | References | Similar articles | Additional information

Abstract: We consider a game that can be viewed as a random graph process. The game has two players and begins with the empty graph on vertex set $ [n]$. During each turn a pair of random edges is generated and one of the players chooses one of these edges to be an edge in the graph. Thus the players guide the evolution of the graph as the game is played. One player controls the even rounds with the goal of creating a so-called giant component as quickly as possible. The other player controls the odd rounds and has the goal of keeping the giant from forming for as long as possible. We show that the product rule is an asymptotically optimal strategy for both players.


References:

1.
T. Bohman and A. Frieze, Avoiding a giant component. Random Structures and Algorithms 19 (2001), 75-85.MR 1848028 (2002g:05169)

2.
T. Bohman, A. Frieze and N. Wormald, Avoidance of a giant component in half the edge set of a random graph. Random Structures and Algorithms 25 (2004) 432-449.MR 2099213 (2005f:05151)

3.
T. Bohman and J. H. Kim, A phase transition for avoiding a giant component. Random Structures and Algorithms 28 (2006) 195-214. MR 2198497

4.
T. Bohman and D. Kravitz, Creating a giant component. Combinatorics, Probability and Computing 15 (2006) 489-511. MR 2238042

5.
A. Flaxman, D. Gamarnik and G. Sorkin, Embracing the giant component. pp. 69-79 in Latin 2004: Theoretical Informatics, Farach and Coltin eds. Springer 2004.MR 2095182

6.
J. Spencer, Percolating thoughts. Unpublished manuscript dated January 31, 2001.

7.
J. Spencer and N. Wormald, Birth Control for Giants. Combinatorica, to appear.

8.
N. Wormald, The differential equations method for random graph processes and greedy algorithms. pp. 73-155 in Lectures on Approximation and Randomized Algorithms, Karonski and Prömel eds. PWN, Warsaw 1999.


Similar Articles:

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 05C80

Retrieve articles in all Journals with MSC (2000): 05C80


Additional Information:

Andrew Beveridge
Affiliation: Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvannia 15213
Email: ajbever@andrew.cmu.edu

Tom Bohman
Affiliation: Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvannia 15213
Email: tbohman@math.cmu.edu

Alan Frieze
Affiliation: Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvannia 15213
Email: alan@random.math.cmu.edu

Oleg Pikhurko
Affiliation: Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvannia 15213
Email: pikhurko@andrew.cmu.edu

DOI: 10.1090/S0002-9939-07-08853-3
PII: S 0002-9939(07)08853-3
Received by editor(s): February 1, 2006
Received by editor(s) in revised form: June 15, 2006
Posted: May 14, 2007
Additional Notes: The second author was supported in part by NSF grant DMS-0401147
The third author was supported in part by NSF grant CCR-0502793
The fourth author was supported in part by NSF grant DMS-0457512
Communicated by: Jim Haglund
Copyright of article: Copyright 2007, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google