Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

 

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 $ [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 [Enhancements On Off] (What's this?)


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: http://dx.doi.org/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
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.