Product rule wins a competitive game

Authors:
Andrew Beveridge, Tom Bohman, Alan Frieze and Oleg Pikhurko

Journal:
Proc. Amer. Math. Soc. **135** (2007), 3061-3071

MSC (2000):
Primary 05C80

Published electronically:
May 14, 2007

MathSciNet review:
2322735

Full-text PDF Free Access

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 . 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.

**1.**Tom Bohman and Alan Frieze,*Avoiding a giant component*, Random Structures Algorithms**19**(2001), no. 1, 75–85. MR**1848028**, 10.1002/rsa.1019**2.**Tom Bohman, Alan Frieze, and Nicholas C. Wormald,*Avoidance of a giant component in half the edge set of a random graph*, Random Structures Algorithms**25**(2004), no. 4, 432–449. MR**2099213**, 10.1002/rsa.20038**3.**Tom Bohman and Jeong Han Kim,*A phase transition for avoiding a giant component*, Random Structures Algorithms**28**(2006), no. 2, 195–214. MR**2198497**, 10.1002/rsa.20085**4.**Tom Bohman and David Kravitz,*Creating a giant component*, Combin. Probab. Comput.**15**(2006), no. 4, 489–511. MR**2238042**, 10.1017/S0963548306007486**5.**Abraham Flaxman, David Gamarnik, and Gregory B. Sorkin,*Embracing the giant component*, LATIN 2004: Theoretical informatics, Lecture Notes in Comput. Sci., vol. 2976, Springer, Berlin, 2004, pp. 69–79. MR**2095182**, 10.1007/978-3-540-24698-5_11**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.

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:
http://dx.doi.org/10.1090/S0002-9939-07-08853-3

Received by editor(s):
February 1, 2006

Received by editor(s) in revised form:
June 15, 2006

Published electronically:
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

Article copyright:
© Copyright 2007
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.