Hostname: page-component-7c8c6479df-27gpq Total loading time: 0 Render date: 2024-03-29T07:08:34.579Z 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)

Abstract

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).

Type
Research Article
Copyright
1998 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)