Product rule wins a competitive game
HTML articles powered by AMS MathViewer
- by Andrew Beveridge, Tom Bohman, Alan Frieze and Oleg Pikhurko PDF
- Proc. Amer. Math. Soc. 135 (2007), 3061-3071 Request permission
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
- Tom Bohman and Alan Frieze, Avoiding a giant component, Random Structures Algorithms 19 (2001), no. 1, 75–85. MR 1848028, DOI 10.1002/rsa.1019
- 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, DOI 10.1002/rsa.20038
- 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, DOI 10.1002/rsa.20085
- Tom Bohman and David Kravitz, Creating a giant component, Combin. Probab. Comput. 15 (2006), no. 4, 489–511. MR 2238042, DOI 10.1017/S0963548306007486
- 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, DOI 10.1007/978-3-540-24698-5_{1}1
- J. Spencer, Percolating thoughts. Unpublished manuscript dated January 31, 2001.
- J. Spencer and N. Wormald, Birth Control for Giants. Combinatorica, to appear.
- N. Wormald, The differential equations method for random graph processes and greedy algorithms. pp. 73-155 in Lectures on Approximation and Randomized Algorithms, Karoński and Prömel eds. PWN, Warsaw 1999.
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
- 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
- © Copyright 2007
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 135 (2007), 3061-3071
- MSC (2000): Primary 05C80
- DOI: https://doi.org/10.1090/S0002-9939-07-08853-3
- MathSciNet review: 2322735