A threshold for the Maker‐Breaker clique game1. Issue 2 (5th March 2013)

• Record Type: Journal Article
• Authors: Müller, Tobias; Stojaković, Miloš
• Is Part Of: Random structures & algorithms. Volume 45:Issue 2(2014)
• Page Start: 318
• Page End: 341
• Publication Date: 2013-03-05
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20489
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>ABSTRACT</title> <p>We study the Maker‐Breaker <italic>k</italic>‐clique game played on the edge set of the random graph <italic>G</italic>(<italic>n, p</italic>). In this game, two players, Maker and Breaker, alternately claim unclaimed edges of <italic>G</italic>(<italic>n, p</italic>), until all the edges are claimed. Maker wins if he claims all the edges of a <italic>k</italic>‐clique; Breaker wins otherwise. We determine that the threshold for the graph property that Maker can win this game is at <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghv4p2n5c" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20489:rsa20489-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mfrac><mml:mn>2</mml:mn><mml:mrow><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:mfrac></mml:mrow></mml:msup></mml:mrow></mml:math></alternatives></inline-formula>, for all <italic>k</italic> > 3, thus proving a conjecture from Ref. [Stojaković and Szabó, Random Struct Algor 26 (2005), 204–223]. More precisely, we conclude that there exist constants <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghv4p2n6w" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20489:rsa20489-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>c</mml:mi><mml:mo>, </mml:mo><mml:mi>C</mml:mi><mml:mo>></mml:mo><mml:mn>0</mml:mn></mml:mrow></mml:math></alternatives></inline-formula> such that when <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghv4p2n3b" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20489:rsa20489-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>p</mml:mi><mml:mo>></mml:mo><mml:mi>C</mml:mi><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mfrac><mml:mn>2</mml:mn><mml:mrow><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:mfrac></mml:mrow></mml:msup></mml:mrow></mml:math></alternatives></inline-formula> the game is Maker's win a.a.s., and when <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghv4p2n4v" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20489:rsa20489-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>p</mml:mi><mml:mo><</mml:mo><mml:mi>c</mml:mi><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mfrac><mml:mn>2</mml:mn><mml:mrow><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:mfrac></mml:mrow></mml:msup></mml:mrow></mml:math></alternatives></inline-formula> it is Breaker's win a.a.s.</p> <p>For the triangle game, when <italic>k</italic> = 3, we give a more precise result, describing the hitting time of Maker's win in the random graph process. We show that, with high probability, Maker can win the triangle game exactly at the time when a copy of <italic>K</italic><sub>5</sub> with one edge removed appears in the random graph process. As a consequence, we are able to give an expression for the limiting probability of Maker's win in the triangle game played on the edge set of <italic>G</italic>(<italic>n, p</italic>). © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 318–341, 2014</p> </abstract>