Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-07T12:11:09.049Z Has data issue: false hasContentIssue false

On Biased Positional Games

Published online by Cambridge University Press:  01 December 1998

MAŁGORZATA BEDNARSKA
Affiliation:
Department of Discrete Mathematics, Adam Mickiewicz University, Poznán, Poland (e-mail: mbed@amu.edu.pl)
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.

Let TBin(N, n, q) be the game on the complete graph KN in which two players, the Breaker and the Maker, alternately claim one and q edges, respectively. The Maker's aim is to build a binary tree on n<N vertices in n−1 turns while the Breaker tries to prevent him from doing so. It is shown that, for every constant ε>0, there exists n0 such that, for every n[ges ]n0, the Breaker has a winning strategy in TBin(N, n, q) if q>(1+ε)N/logn, while, for q<(1−ε)N/logn, the game TBin(N, n, q) can be won by the Maker provided that n=o(N).

Information

Type
Research Article
Copyright
1998 Cambridge University Press