Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-07T10:23:48.578Z Has data issue: false hasContentIssue false
  • English
  • Français

Winning Fast in Sparse Graph Construction Games

Published online by Cambridge University Press:  01 November 2008

OHAD N. FELDHEIM  and
MICHAEL KRIVELEVICH
OHAD N. FELDHEIM
Affiliation:
School of Mathematical Sciences, Tel Aviv University, Tel Aviv, 69978, Israel (e-mail: ohad_f@netvision.net.il; krivelev@post.tau.ac.il)
MICHAEL KRIVELEVICH
Affiliation:
School of Mathematical Sciences, Tel Aviv University, Tel Aviv, 69978, Israel (e-mail: ohad_f@netvision.net.il; krivelev@post.tau.ac.il)
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.

A graph construction game is a Maker–Breaker game. Maker and Breaker take turns in choosing previously unoccupied edges of the complete graph KN. Maker's aim is to claim a copy of a given target graph G while Breaker's aim is to prevent Maker from doing so. In this paper we show that if G is a d-degenerate graph on n vertices and N > d1122d+9n, then Maker can claim a copy of G in at most d1122d+7n rounds. We also discuss a lower bound on the number of rounds Maker needs to win, and the gap between these bounds.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 6 , November 2008 , pp. 781 - 791
Copyright
Copyright © Cambridge University Press 2008

References

[1]Alon, N., Krivelevich, M., Spencer, J. and Szabó, T. (2005) Discrepancy games. Electron. J. Combin. 12 R51.Google Scholar
[2]Beck, J. (1994) Deterministic graph games and a probabilistic intuition. Combin. Probab. Comput. 3 13–26.CrossRefGoogle Scholar
[3]Beck, J. (2002) Ramsey games. Discrete Math. 249 3–30.Google Scholar
[4]Beck, J. (2005) Positional games. Combin. Probab. Comput. 14 649–696.Google Scholar
[5]Beck, J. (2008) Combinatorial Games: Tic-Tac-Toe Theory, Encyclopedia of Mathematics, Cambridge University Press.Google Scholar
[6]Burr, S. A. and Erdős, P. (1975) The magnitude of generalized Ramsey numbers for graphs. In Infinite and Finite Sets I, Vol. 10 of Colloquia Mathematica Societatis Janos Bolyai, pp. 214–240.Google Scholar
[7]Erdős, P. and Selfridge, J. (1973) On a combinatorial game. J. Combin. Theory Ser. A 14 298–301.Google Scholar
[8]Pekeč, A. (1996) A winning strategy for the Ramsey graph game. Combin. Probab. Comput. 5 267–276.Google Scholar
[9]Székely, L. A. (1984) On two concepts of discrepancy in a class of combinatorial games. In Infinite and Finite Sets, Vol. 37 of Colloquia Mathematica Societatis Janos Bolyai, pp. 679–683.Google Scholar