Abstract
Positional Games is a branch of Combinatorics which focuses on a variety of two player games, ranging from well-known games such as Tic-Tac-Toe and Hex, to purely abstract games played on graphs. The field has experienced quite a growth in recent years, with more than a few applications in related areas.
We aim to introduce the basic notions, approaches and tools, as well as to survey the recent developments, open problems and promising research directions, keeping the main focus on the games played on graphs.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Beck, J.: Combinatorial Games: Tic-Tac-Toe Theory. Encyclopedia of Mathematics and Its Applications, vol. 114. Cambridge University Press (2008)
Bednarska, M., Luczak, T.: Biased positional games for which random strategies are nearly optimal. Combinatorica 20, 477–488 (2000)
Ben-Shimon, S., Ferber, A., Hefetz, D., Krivelevich, M.: Hitting time results for Maker-Breaker games. Random Structures and Algorithms 41, 23–46 (2012)
Chvátal, V., Erdős, P.: Biased positional games. Annals of Discrete Mathematics 2, 221–228 (1978)
Gale, D.: The game of Hex and the Brouwer fixed-point theorem. The American Mathematical Monthly 86, 818–827 (1979)
Gebauer, H., Szabó, T.: Asymptotic random graph intuition for the biased connectivity game. Random Structures and Algorithms 35, 431–443 (2009)
Hefetz, D., Krivelevich, M., Szabó, T.: Avoider-Enforcer games. Journal of Combinatorial Theory Series A 114, 840–853 (2007)
Hefetz, D., Krivelevich, M., Stojaković, M., Szabó, T.: A sharp threshold for the Hamilton cycle Maker-Breaker game. Random Structures and Algorithms 34, 112–122 (2009)
Hefetz, D., Krivelevich, M., Stojaković, M., Szabó, T.: Avoider-Enforcer: The rules of the Game. Journal of Combinatorial Theory Series A 117, 152–163 (2010)
Hefetz, D., Krivelevich, M., Stojaković, M., Szabó, T.: Positional Games. Ober- wolfach Seminars, vol. 44. Birkhäuser (2014)
Krivelevich, M.: The critical bias for the Hamiltonicity game is (1 + o(1))n/ ln n. Journal of the American Mathematical Society 24, 125–131 (2011)
Krivelevich, M., Szabó, T.: Biased positional games and small hypergraphs with large covers. Electronic Journal of Combinatorics 15, R70 (2008)
Lehman, A.: A solution of the Shannon switching game. Journal of the Society for Industrial and Applied Mathematics 12, 687–725 (1964)
Müller, T., Stojaković, M.: A threshold for the Maker-Breaker clique game. Random Structures and Algorithms (to appear)
Stojaković, M.: Games on Graphs, PhD Thesis. ETH Zürich (2005)
Stojaković, M., Szabó, T.: Positional games on random graphs. Random Structures and Algorithms 26, 204–223 (2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Stojaković, M. (2014). Games on Graphs. In: Hernandez, N., Jäschke, R., Croitoru, M. (eds) Graph-Based Representation and Reasoning. ICCS 2014. Lecture Notes in Computer Science(), vol 8577. Springer, Cham. https://doi.org/10.1007/978-3-319-08389-6_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-08389-6_4
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08388-9
Online ISBN: 978-3-319-08389-6
eBook Packages: Computer ScienceComputer Science (R0)