Product rule wins a competitive game

Beveridge, Andrew; Bohman, Tom; Frieze, Alan; Pikhurko, Oleg

doi:10.1090/S0002-9939-07-08853-3

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.