Hostname: page-component-745bb68f8f-v2bm5 Total loading time: 0 Render date: 2025-02-12T01:21:21.756Z Has data issue: false hasContentIssue false
  • English
  • Français

Fast Strategies In Maker–Breaker Games Played on Random Boards

Published online by Cambridge University Press:  10 September 2012

DENNIS CLEMENS ,
ASAF FERBER ,
MICHAEL KRIVELEVICH  and
ANITA LIEBENAU
DENNIS CLEMENS
Affiliation:
Department of Mathematics and Computer Science, Freie Universität Berlin, Germany (e-mail: d.clemens@fu-berlin.de, liebenau@math.fu-berlin.de)
ASAF FERBER
Affiliation:
School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, 69978, Israel (e-mail: ferberas@post.tau.ac.il, krivelev@post.tau.ac.il)
MICHAEL KRIVELEVICH
Affiliation:
School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, 69978, Israel (e-mail: ferberas@post.tau.ac.il, krivelev@post.tau.ac.il)
ANITA LIEBENAU
Affiliation:
Department of Mathematics and Computer Science, Freie Universität Berlin, Germany (e-mail: d.clemens@fu-berlin.de, liebenau@math.fu-berlin.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper we analyse classical Maker–Breaker games played on the edge set of a sparse random board G ~ n,p. We consider the Hamiltonicity game, the perfect matching game and the k-connectivity game. We prove that for p(n) ≥ polylog(n)/n the board G ~ n,p is typically such that Maker can win these games asymptotically as fast as possible, i.e., within n+o(n), n/2+o(n) and kn/2+o(n) moves respectively.

Keywords

Primary 05C8005C5791A4391A46
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 6 , November 2012 , pp. 897 - 915
Copyright
Copyright © Cambridge University Press 2012

References

[1]Alon, N. and Spencer, J. H. (2008) The Probabilistic Method, Wiley.Google Scholar
[2]Beck, J. (1982) Remarks on positional games. Acta Math. Acad. Sci. Hungar. 40 65–71.Google Scholar
[3]Beck, J. (2008) Combinatorial Games: Tic-Tac-Toe Theory, Cambridge University Press.CrossRefGoogle Scholar
[4]Ben-Eliezer, I., Krivelevich, M. and Sudakov, B. (2012) The size Ramsey number of a directed path. J.~Combin. Theory Ser. B 102 743–755.Google Scholar
[5]Ben-Shimon, S., Ferber, A., Hefetz, D. and Krivelevich, M. (2011) Hitting time results for Maker–Breaker games. In Proc. 22nd Symposium on Discrete Algorithms: SODA'11, pp. 900–912.Google Scholar
[6]Chvátal, V. and Erdős, P. (1978) Biased positional games. Ann. of Discrete Math. 2 221–228.Google Scholar
[7]Ferber, A. and Hefetz, D. (2011) Winning strong games through fast strategies for weak games. Electron. J. Combin. 18 P144.Google Scholar
[8]Ferber, A. and Hefetz, D. Weak and strong k-connectivity game. Preprint. www.math.tau.ac.il/~ferberas/papersGoogle Scholar
[9]Ferber, A., Hefetz, D. and Krivelevich, M. (2012) Fast embedding of spanning trees in biased Maker–Breaker games. Europ. J. Combin. 33 1086–1099.CrossRefGoogle Scholar
[10]Hefetz, D., Krivelevich, M., Stojaković, M. and Szabó, T. (2009) Fast winning strategies in Maker–Breaker games. J. Combin. Theory Ser. B 99 39–47.Google Scholar
[11]Hefetz, D., Krivelevich, M. and Szabó, T. (2009) Hamilton cycles in highly connected and expanding graphs. Combinatorica 29 547–568.CrossRefGoogle Scholar
[12]Hefetz, D., Krivelevich, M. and Szabó, T. Sharp threshold for the appearance of certain spanning trees in random graphs. Random Struct. Alg., to appear.Google Scholar
[13]Hefetz, D. and Stich, S. (2009) On two problems regarding the Hamilton cycle game. Electron. J. Combin. 16 R28.Google Scholar
[14]Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley.CrossRefGoogle Scholar
[15]Krivelevich, M. (2010) Embedding spanning trees in random graphs. SIAM J. Discrete Math. 24 1495–1500.Google Scholar
[16]Lehman, A. (1964) A solution to the Shannon switching game. J. Soc. Indust. Appl. Math. 12 687–725.Google Scholar
[17]Stojaković, M. and Szabó, T. (2005) Positional games on random graphs. Random Struct. Alg. 26 204–223.CrossRefGoogle Scholar
[18]West, D. B. (2001) Introduction to Graph Theory, Prentice Hall.Google Scholar