Printer Friendly

Avoider-enforcer star games.

In this paper, we study (1:b) Avoider-Enforcer games played on the edge set of the complete graph on n vertices. For every constant k [greater than or equal to] 3 we analyse the k-star game, where Avoider tries to avoid claiming k edges incident to the same vertex. We consider both versions of Avoider-Enforcer games--the strict and the monotone--and for each provide explicit winning strategies for both players. We determine the order of magnitude of the threshold biases [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where F is the hypergraph of the game.

Keywords: positional games, complete graph, Avoider-Enforcer

1 Introduction

Let a and b be two positive integers, let X be a finite set and let F [??] [2.sup.X] be a family of subsets of X. In an (a : b) Avoider-Enforcer game F, two players, called Avoider and Enforcer, alternately claim a and b previously unclaimed elements of X per move, respectively. If the number of unclaimed elements is strictly less than a (respectively b) before Avoider's (respectively Enforcer's) move, then he claims all these elements. The game ends when all the elements of X have been claimed by either of the players. Avoider loses the game if by the end of the game he has claimed all the elements of some F [member of] F, and wins otherwise. Throughout this paper we assume that Avoider is the first player to play, although usually it makes very little difference. We refer to X as the board of the game, to F as the target sets, and to a and b as the bias of Avoider and Enforcer, respectively. Since the pair (X, F) is a hypergraph that represents the game, we often refer to F as the hypergraph of the game, or as the game itself.

Avoider-Enforcer games are the misere version of the well-studied Maker-Breaker games. In an (a : b) Maker-Breaker game F, the two players are called Maker and Breaker, they claim respectively a and b elements of X per move, and Maker wins if and only if by the end of the game he has claimed all the elements of some F [member of] F. Both Maker-Breaker and Avoider-Enforcer games are finite, perfect information games, and there is no possibility of a draw. Hence, for every given setup--a, b, F--one of the players has a winning strategy. We say that this player wins the game.

It is very natural to play both Avoider-Enforcer and Maker-Breaker games on the edge set of a given graph G, and specifically for G = [K.sub.n], the complete graph on n vertices. In this case the board is X = E([K.sub.n]) and the target sets are [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For example: in the connectivity game [C.sub.n] the target sets are all edge sets of connected graphs on n vertices; in the perfect matching game [M.sub.n] the target sets are all graphs on n vertices containing a perfect matching (we assume n is even here); in the Hamiltonicity game [H.sub.n] the target sets are all edge sets of graphs on n vertices containing a Hamilton cycle. We usually omit the subindex n in our notation. These three games were initially studied in Maker-Breaker version by Chvatal and Erdos in their seminal paper [4].

Many natural games played on the edges of [K.sub.n] (including all the above mentioned ones) are drastically in favor of Maker, i.e. Maker wins in the unbiased (1 : 1) version in (almost) minimal number of moves required to create a winning set. Therefore, it makes sense to give more power to Breaker in order to even out the odds, and typically the (1 : b) version is considered. In addition, Maker-Breaker games are bias monotone: if Maker wins some game F with bias (a : b), he also wins this game with bias (a' : b'), for every a' [greater than or equal to] a and b' [less than or equal to] b. This bias monotonicity enables the definition of the threshold bias: for a given hypergraph F, the threshold bias [f.sub.F] is the unique integer for which Maker wins the (1 : b) game F for every b < [f.sub.F], and Breaker wins the (1:b) game F for every b [greater than or equal to] [f.sub.F].

Unfortunately, Avoider-Enforcer games are not bias monotone in general (see e.g. [6], [7]): although intuitively each player wishes to claim as few elements as possible, it is sometimes a disadvantage to claim fewer elements per move, for any of the players. This makes the analysis of these games much more difficult, and it is not possible to define the threshold bias in the same manner as in Maker-Breaker games. Therefore, Hefetz, Krivelevich and Szabo introduced in [7] the following parameters. The lower threshold bias [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the largest integer such that Enforcer wins the (1 : b) game F for every b [less than or equal to] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The upper threshold bias [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the smallest non-negative integer such that Avoider wins the (1 : b) game F for every b > [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Except for some trivial cases, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] always exist and satisfy [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [less than or equal to] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. When [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] we call this number [f.sub.F] and refer to it as the threshold bias of the game F.

In order to overcome this bias monotonicity obstacle, Hefetz, Krivelevich, Stojakovic and Szabo proposed in [6] a bias monotone version for Avoider-Enforcer games: they suggested that Avoider and Enforcer will claim at least a and b board elements per move, respectively. It is easy to see that this new version is indeed bias monotone, i.e. each player can only benefit from lowering his bias. This fact allowed them to define for any given hypergraph F the monotone threshold bias [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as the largest non-negative integer for which Enforcer wins the (1 : b) game F under the new set of rules if and only if b [less than or equal to] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Throughout this paper we refer to this new set of rules as the monotone rules, to distinguish it from the strict rules. Accordingly, we refer to the games played under the two sets of rules as monotone games and as strict games, respectively.

Interestingly, these seemingly minor adjustments in the rules can completely change the outcome of the game. For example, even in such a natural game as the connectivity game, the two versions of the game are essentially different. In [7] it was shown that Avoider wins the strict (1 : b) connectivity game played on E([K.sub.n]) if and only if at the end of the game he has at most n - 2 edges, therefore the threshold bias exists and is of linear order. On the other hand, the monotone threshold bias for this game is of order [n/in n] [6, 9].

Naturally, one may ask about the relationship between [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Specifically, it could be expected that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] holds for every family F. The above mentioned connectivity game shows that this is not true in general, even when there exists a threshold bias in the strict game.

In [7], Hefetz, Krivelevich and Szabo provided a general sufficient condition for Avoider's win in (a : b) Avoider-Enforcer games played under both sets of rules. This criterion takes only Avoider's bias into account. In [2], Bednarska-Bzdega introduced a new sufficient condition for Avoider's win under both sets of rules, which depends on both parameters a and b, and gives a better result than the one in [7] in cases where the hypergraph of the game has rank smaller than b.

In [6], Hefetz et al. investigated (1:b) Avoider-Enforcer games played on the edge set of [K.sub.n], where Avoider wants to avoid claiming a copy of some fixed graph H. In this case X = E([K.sub.n]), and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] consists of all subgraphs of [K.sub.n] containing H as a subgraph. These games are referred to as H-games. They conjectured that for any fixed graph H, the thresholds [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are not of the same order of magnitude, and wondered about the connection between monotone H-games and strict [H.sup.-]-games, where [H.sup.-] is H with one edge missing. They investigated H-games where H = [K.sub.3] (a triangle) and H = [P.sub.3] (a path on three vertices) and established the following:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

They used this example to support their conjecture, as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are indeed not of the same order. They also noted that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are of the same order, and that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Bednarska-Bzdega established in [2] general upper and lower bounds on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for every fixed graph H, but these bounds are not tight for every graph H. In order to prove our main result of this paper we prove a number theoretic fact, which we later use independently in order to improve one of Bednarska-Bzdega's bounds. We elaborate on that in Section 5.

Our main objective in this paper is to study monotone and strict H-games played on the edges of [K.sup.n], where H is the k-star [K.sub.1,k], denoted by [S.sub.k], for any fixed k [greater than or equal to] 3. We refer to this game as the star game, or more specifically, for a given k, we call this game the k-star game. Studying the star game is very natural, since avoiding a k-star in Avoider's graph is exactly keeping its maximal degree strictly below k. We analyse this game, provide explicit winning strategies for both players under both sets of rules, and obtain the following.

Theorem 1.1. For every k [greater than or equal to] 3 and for every large enough n the following bounds hold:

(i) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII];

(ii) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII];

(iii) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

These results show that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are not of the same order for any given k [greater than or equal to] 3, supporting the conjecture of Hefetz et al. from [6]. In addition, as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], an immediate consequence of Theorem 1.1 is that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are of the same order, showing a strong connection between the monotone H-game and the strict [H.sup.-]-game in this case. Note that [S.sub.2] = [P.sub.3], so the k-star game for k = 2 is already covered in [6]. In fact, the results there match ours, if we generalize Theorem 1.1 to include the case k = 2. However, since these results are known, and in order to avoid some technical difficulties in our proofs, we only consider the case k [greater than or equal to] 3.

The outcome of some (1 : b) positional games played on the edges of [K.sub.n], where the target sets possess some graph property P, is the same as in the corresponding games where the players play randomly. This phenomenon was first observed by Chvatal and Erdos in [4] for the Maker-Breaker connectivity game, and is known as the random graph intuition. The reason for this name is that when both players play randomly the (1 : b) game, the graph of the player with bias 1 (either Maker or Avoider) at the end of the game satisfies G ~ G(n, m), where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For this given m, the graph G(n, m) behaves in many ways similarly to G(n, [1/b+1]), the random graph on n vertices where each potential edge appears in the graph independently with probability [1/b+1] [8]. In other words, the threshold bias b* for these games is asymptotically equal to 1/p*, where p* is the threshold probability for the appearance of P in G ~ G(n, p).

The k-star game is a very good example for this phenomenon, as indeed the properties of the random graph G ~ G((n, [1/b+1]) suggest the outcome of the Avoider-Enforcer (1 : b) k-star game. All the following statements about G hold w.h.p. (i.e. with probability tending to 1 as n tends to infinity). For details the reader may refer to [3], Theorem 3.1.

* For [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the maximal degree in G is at most k - 2, and Avoider wins the (1 : b) game (both strict and monotone).

* At [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], vertices of degree k - 1 emerge in G. If Avoider claims the last edge in the (1 : b) game, the appearance of a vertex of degree k - 1 in his graph before the last round means he loses, and this is indeed the order of magnitude of f [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where presumably Avoider claims the last edge.

* When [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the maximal degree in G is exactly k - 1. The outcome of the strict (1 : b) game heavily depends on the number of free edges Avoider will be able to choose from in his last move, and so the outcome oscillates.

Finally, for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where C is a sufficiently small constant, vertices of degree k emerge in G, and Enforcer wins the (1 : b) game (both strict and monotone).

The rest of the paper is organized as follows: in Section 3 we provide Avoider's strategy for the k-star game which applies for both versions of the game. In Section 4 we provide Enforcer's strategies for the k-star game, one strategy for the monotone game and one for the strict game. In Section 5 we improve one of Bednarska-Bzdega's bounds for general H-games. Finally, in Section 6 we present some concluding remarks and open problems.

2 Preliminaries

Throughout this paper we use the following notation.

A previously unclaimed edge is called a free edge. The act of claiming one free edge by one of the players is called a step. In the strict game, Enforcer's b (respectively Avoider's 1) successive steps are called a move. In the monotone game, each move consists of at least b steps, respectively at least one step. A round in the game consists of one move of the first player (Avoider), followed by one move of the second player (Enforcer). Whenever one of the players claims an edge incident to some vertex u, we say that the player touched u.

Our graph-theoretic notation is standard and follows that of [10]. In particular, throughout the paper G stands for a simple graph with vertex set V = V(G) and edge set E = E(G). For any subset U [??] V we say that an edge uv lies inside U if u, v [member of] U. For i [greater than or equal to] 0, we denote by Ai and [E.sub.i] the graphs with vertex set V, whose edges were claimed by Avoider, respectively Enforcer, in the first i rounds. For every vertex v [member of] V and every i [greater than or equal to] 0, let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the degree of v in [A.sub.i], respectively [E.sub.i]. We sometimes omit the subindex i when its value is clear or irrelevant. In these cases we also refer to [d.sub.A](v) as the A-degree of v. Whenever we consider the end of the ith round for the case i = 0, we simply refer to the beginning of the game, before any move was played.

The set of all free edges at the end of the ith round is denoted by [F.sub.i]. A free edge is called a threat if it is incident to a vertex of A-degree k - 1.

For the sake of simplicity and clarity of presentation, no real effort has been made here to optimize the constants appearing in our results. We also omit floor and ceiling signs whenever these are not crucial. Our results are asymptotic in nature and whenever necessary we assume that n is sufficiently large. We use o(1) to denote a positive function of n, tending to zero as n tends to infinity.

For every two integers n and b let r = r(n, b) be the integer for which 1 [less than or equal to] r [less than or equal to] b + 1 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] mod (b + 1) hold. The value of r is the number of free edges before the last round of the strict game, and since Avoider is the first player, r is actually the number of edges which remain for Avoider to choose from in his last move. Therefore, this value may be very significant in determining the identity of the winner in the strict game. In order to estimate r in some cases, we need the following two number theoretical statements.

Fact 2.1. Let c and [alpha] be two constants such that either [alpha] = 1 and c [greater than or equal to] 1, or [alpha] [member of] (1,2) and c > 0. For any sufficiently large integer n there exists an integer q = (2 - o(1)) [cn.sup.[alpha]] such that the remainder of the division of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by q is larger than [cn.sup.[alpha]].

Proof: Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], N' = N - [cn.sup.[alpha]] - 1, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and q = [N'/m]. Note that N' = qm + r for some 0 [less than or equal to] r < m and that q = (2 - o(1)) [cn.sup.[alpha]]. Since N - qm = [cn.sup.[alpha]] + r + 1 < q, it follows that the remainder of the division of N by q is larger than [cn.sup.[alpha]].

Fact 2.2. For every sufficiently large integer n and for every constant k [greater than or equal to] 3 there exists a c = c(n, k) such that 1/5 < c < 1/4 and the remainder r of the division of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]is positive and satisfies r = [omicron]n).

Proof: Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The least common multiple of the elements in M is at least [n.sup.2.5] so there exists an element m [member of] M which does not divide N. Let q = [N/m] and note that q = (1/4 -o(1)) [n.sup.[k/k-1]]. Since N - m < qm < N, the remainder r of the division of N by q satisfies 0 < r < m = o(1)) [n.sup.[k/k-1]]. Since N - m < qm < N, the remainder r of the division of N by q satisfies 0 < r < m = o(n).(n).

3 Avoider's strategy

In this section we establish upper bounds on the threshold biases [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We provide Avoider with the following trivial strategy [S.sub.A]: in every move Avoider claims one arbitrary edge which does not increase the maximal degree in his graph if such an edge exists, and an arbitrary edge otherwise. Clearly Avoider can follow this strategy. Note that this is a valid strategy for both the monotone and the strict versions of the game.

Consider the course of a game (either strict or monotone) in which Avoider plays according to [S.sub.A] and Enforcer plays according to some fixed strategy. For every i, let [I.sub.i] denote the set of vertices of maximal A-degree at the end of round i. Let s be the maximal A-degree at the end of the game. For every 0 [less than or equal to] j [less than or equal to] s, let [i.sub.j] be the largest integer such that the maximal A-degree at the end of round [i.sub.j] is j. Note that the maximal A-degree is never increased by more than one according to [S.sub.A], and so 0 = [i.sub.0] < [i.sub.1] < [??] < [i.sub.s].

Lemma 3.1. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for every 0 [less than or equal to] j [less than or equal to] s.

Proof: Observe that at the end of round [i.sub.j] (for every j) every free edge has at least one endpoint in [I.sub.ij], as otherwise Avoider will not increase the maximal degree in his graph in his subsequent move. Therefore, if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since the number of free edges at the game is obviously [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], it suffices to show that if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], for every 0 [less than or equal to] j < s.

Indeed, as both players claim altogether at least b + 1 edges, for every 0 [less than or equal to] j < s the number of rounds in the game after round [i.sub.j] cannot be greater than [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since Avoider claims exactly one edge per move, in each round after round [i.sub.j] at most two new vertices of A-degree j + 1 appear. Therefore, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now it is easy to see that [S.sub.A] is a winning strategy for Avoider in the (1 : b) Avoider-Enforcer k-star game for any b [greater than or equal to] [2n.sup.[k/k+1] and under both sets of rules, thus obtaining the upper bounds in Theorem 1.1 (i) and (ii). Indeed, it follows by Lemma 3.1 that if [i.sub.k-2] exists then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Therefore no threat appears before Avoider's last move and so he wins.

We now prove the upper bound for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] given in Theorem 1.1 (iii). By Fact 2.1, with c = 1 and [alpha] = [k+1/k], there exists an integer [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Assume that s [greater than or equal to] k - 1 for this b (otherwise Avoider obviously wins). It follows by Lemma 3.1 that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. However, by the assumption on r there are more free edges than [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] before any move of Avoider, so [i.sub.k-1] is the last round of the game, meaning s = k - 1.

Remark 3.2. All arguments in this section are still valid even if we include the case k = 2.

4 Enforcer's strategies

In this section we establish the lower bounds given in Theorem 1.1. Unlike Avoider's strategy, which was valid for both versions of the game, here we distinguish between the two cases. We start with the monotone game which is simpler to analyse and establish the lower bound on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then we proceed to the strict game, explain the adjustments we make to Enforcer's strategy and establish the lower bounds on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

4.1 The monotone game

We provide a strategy for Enforcer for the monotone (1 : b) k-star game for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. At any point during the game, let I denote the set of isolated vertices in Enforcer's graph, and let C = V \ I. Furthermore, let [I.sub.i] and [C.sub.i] denote the respective sets of vertices at the end of the ith round. Initially, of course, [I.sub.0] = V and [C.sub.0] = [empty set]. Whenever Enforcer touches a vertex previously isolated in his graph, we say that he moved that vertex from I to C.

For every i [greater than or equal to] 0, Enforcer plays his (i + 1)st move as follows.

(1) If there exists a vertex of A-degree at least k, or if there are at most b free edges remaining, Enforcer claims all free edges on the board. We refer to this move as the trivial move.

(2) Otherwise, if there exists a vertex v [member of] I of A-degree k - 1, then Enforcer claims all free edges on the board, except one, incident to v. We refer to this move as the end move.

(3) Otherwise, let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], be an enumeration of the vertices in [I.sub.i] such that for every 1 [less than or equal to] j < |[I.sub.i], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and let [s.sub.i] be the smallest integer such that the number of free edges inside [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is at least b. Enforcer claims all the free edges inside [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We refer to this move as the base move.

We have to show that Enforcer can follow the proposed strategy, and that by doing so he wins the game. Starting with the former, it is evident that Enforcer can play the trivial move; Enforcer can play the end move since there are more than b free edges on the board, and since there are n - k free edges incident to v; finally, Enforcer can play the base move since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and there are more than b free edges on the board.

We now prove that the proposed strategy is indeed a winning strategy for Enforcer. Consider the course of the game in which Enforcer plays according to the proposed strategy and Avoider plays according to some fixed arbitrary strategy. If at any point during the game the maximal A-degree in the graph increases to at least k then Enforcer wins. He also wins if he plays the end move at some point. So assume for contradiction that neither of these events happen. Therefore, by the description of his strategy, it is clear that Enforcer plays the base move for l rounds, for some l [greater than or equal to] 0, and then either the game ends or in his last move he plays the trivial move since there are at most b free edges remaining.

Observation 4.1. Throughout the game, the following properties hold.

(i) There are at least n - k free edges incident to every vertex in I.

(ii) After every move, by either player, every free edge has at least one endpoint in I.

(iii) The number of edges claimed by both players in each round of the game is at most (1 + o(1))b.

Proof:

(i) This is obvious since every vertex in I is isolated in Enforcer's graph and every vertex has A-degree less than k.

(ii) The claim is true after each base move played by Enforcer by his strategy, and there are no free edges left after he plays the trivial move, if he does. Recall that by assumption he never plays the end move. In addition, Avoider does not change the set I, so the claim remains true after his moves as well.

(iii) Whenever Enforcer plays the base move he does not claim more than b + n = (1 + o(1))b edges. If he plays the trivial move this is obviously still true. Finally, Avoider claims at most [kn/2]= o(b) edges throughout the game, otherwise a vertex of A-degree at least k must exist.

Now we wish to estimate the A-degrees of vertices in I. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the average A-degree of the vertices in [I.sub.i] at the end of round i. Note that by definition T(0) = 0, and that T(i) > T(i - 1) if Enforcer plays the base move in his ith move. Indeed, since throughout the game all free edges have at least one endpoint in I, Avoider in his ith move increases the sum of A-degrees in I (while not changing the set itself), and Enforcer in his subsequent move removes from I vertices of minimal A-degree, so he does not decrease the average A-degree in I.

Claim 4.2. For every 0 [less than or equal to] j [less than or equal to] k - 2, the following holds. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some i, then T(i) [greater than or equal to] j.

Proof: We prove the claim by induction on j. The claim trivially holds for j = 0, as T(i) [greater than or equal to] 0 for every i. Suppose now for contradiction that for some 1 <[less than or equal to]j [less than or equal to] k - 2, the claim holds for j - 1, but not for j. Then there exists an integer i such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], but T(i) < j, which implies [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let [i.sub.0] [less than or equal to] i be the minimal index such that T([i.sub.0]) [greater than or equal to] j - 1 (by the induction hypothesis and the size of [I.sub.i], such an index exists), and for every [i.sub.0] [less than or equal to] s [less than or equal to] i let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that W(i) < |[I.sub.i]| by the assumption on the index i.

Since T(i) < j, there are vertices of A-degree less than j in [I.sub.i], and therefore, according to his strategy, Enforcer has only moved vertices of A-degree less than j from I to C in his first i moves. In addition, Avoider increases the sum of A-degrees of the vertices in I in each of his moves. It follows that W(s + 1) > W(s) for every [I.sub.0] [less than or equal to] s < i. Since W([I.sub.0]) [greater than or equal to] 0 by definition of [I.sub.0], and since W(s) is an integer for every s, we get that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It follows that between rounds [I.sub.0] and i, including round [I.sub.0] if [I.sub.0] > 0, Enforcer has claimed at most [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] edges.

On the other hand, consider the vertices that were moved from I to C by Enforcer between rounds [I.sub.0] and i. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and I* = [I.sub.0] = V otherwise (note that [I.sub.0] = 0 if and only if j = 1). Since throughout the game every vertex in I has at least n - k free edges incident to it, and by using the induction hypothesis, we conclude that during the specified rounds Enforcer must have claimed at least

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

edges, a contradiction.

Let i be the maximal index such that |[I.sub.i]| > 0 and T(i) < k - 2 (there exists such an index since both inequalities hold for i = 0). By Claim 4.2 we get [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence, either |[I.sub.i]| [greater than or equal to] [n/1000] and then |[F.sub.i]| = [THETA]([n.sup.2]) = [omega](b), or

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Therefore, |[F.sub.i+1]| > [11/10]b by Part (iii) of Observation 4.1, and T(i + 1) [greater than or equal to] k - 2 by definition of i. Hence, after Avoider's (i + 2)nd move, either there exists a vertex of A-degree at least k, or there exists a vertex v [member of] I with A-degree k - 1, while there are still more than b free edges on the board, in which case Enforcer plays the end move. In either case, this is a contradiction to the assumption on Avoider's strategy. This completes the proof.

4.2 The strict game

Recall that r = r(n, b) denotes the integer which satisfies 1 [less than or equal to] r [less than or equal to] b + 1 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] mod (b + 1), i.e. the number of free edges at the beginning of the last round of the game. Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Claim 4.3. For every sufficiently large integer n and for every integer k [greater than or equal to] 3 the following bounds hold:

(i) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII];

(ii) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof:

(i) By Fact 2.2 there exists an integer [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that r(n,b) = o(n), and since

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in this case, the desired inequality holds.

(ii) Note that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and since r [less than or equal to] b + 1 trivially holds, we get [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The lower bounds in Theorem 1.1 (ii) and (iii) follow directly from Claim 4.3 and the following lemma.

Lemma 4.4. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] hold for every k [greater than or equal to] 3 and sufficiently large n.

Proof: Throughout this proof we assume that Enforcer's bias b satisfies [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For simplicity, we first assume that b also satisfies b = [omega](n). We propose a strategy for Enforcer which is very similar to the proposed strategy in the monotone game. However, some modifications are inevitable. One major difference between the two versions of the game is that the appearance of one threat (recall that a threat is a free edge incident to a vertex of A-degree k - 1) does not secure Enforcer's win, so he has to make sure that r threats appear before the last round. We therefore say that the game is in a winning position if either the maximal degree in Avoider's graph is at least k or there exist at least r threats. Since Enforcer cannot increase Avoider's degrees or the number of threats, Enforcer wins the game if and only if the game is in a winning position after Avoider's penultimate move. For convenience we denote [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (i.e. the game lasts exactly l + 1 rounds).

Another difference between the two versions of the game is that in the strict game Enforcer cannot maintain the property that every free edge is incident to at least one vertex isolated in his graph. However, he is able to maintain a partition V = I [union] C (where [I.sub.i] and [C.sub.i] denote the respective sets at the end of the ith round) with some similar properties. The exact construction of the sets I and C will be explained shortly. Initially, as in the monotone game, [I.sub.0] = V and [C.sub.0] = [empty set]. Once again we denote by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the average A-degree of the vertices in [I.sub.i] at the end of round i.

Enforcer's strategy involves dividing the course of the game into two stages. The game begins at Stage I; for every 0 < i < l, if the game is in a winning position before Enforcer's ith move then Stage I is over and Enforcer immediately proceeds to Stage II. Otherwise, he keeps playing in Stage I. If before Enforcer's lth move the game is still in Stage I, he proceeds to Stage II even if the game is not in a winning position. So, for some 1 [less than or equal to] i [less than or equal to] l Avoider's ith move is the last move in Stage I and Enforcer's ith move is the first move in Stage II. In each stage, Enforcer plays as follows.

Stage I: For every i [greater than or equal to] 0 such that Enforcer plays his (i + 1)st move in this stage, let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be an enumeration of the vertices in [I.sub.i] for which [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], for 1 [less than or equal to] j [less than or equal to] |[I.sub.i]|. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and let [s.sub.i] be the largest integer such that the number of free edges inside [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is at most b. Every move consists of two parts.

In the first part of every move Enforcer claims all the free edges inside [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and he moves [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from I to C, i.e. defines [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For the second part of every move, let [l.sub.i+1] denote the number of edges Enforcer must claim in order to complete his (i + 1)st move. For every vertex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], Enforcer claims either [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] arbitrary free edges vu such that u [member of] [C.sub.i+1], to get a total of [l.sub.i+1] edges, thus completing his move. We say that these edges are attached to v.

Stage II: In every step of every move in this stage, Enforcer claims an arbitrary edge which is not a threat if such an edge exists, and an arbitrary threat otherwise. He no longer maintains the partition V = I [union] C.

First we show that Enforcer can follow the proposed strategy. This is obvious for Stage II and for the first part of every move in Stage I. Assume now that Enforcer is trying to play the second part of his ith move in Stage I for some i > 0, after playing successfully all his previous moves according to the proposed strategy, including the first part of the ith move. In particular, the partition V = [I.sub.i] [union] [C.sub.i] has been determined. It is easy to see that at this point, exactly as in the monotone game, every free edge has at least one endpoint in [I.sub.i]. Therefore, if there are less than 4k vertices in [I.sub.i] then there are only [OMICRON](n) = o(b) free edges remaining (by our assumption b = [omega](n)), which implies i [greater than or equal to] l, in contradiction to the assumption that Enforcer is playing his ith move in Stage I.

Hence, it only remains to show that Enforcer will be able to attach enough edges to every vertex among the first 4k of [I.sub.i]. Observe that [I.sub.i] < |[C.sub.i]| by definition of [s.sub.i-1] and that |[C.sub.j]| = [omega](1) for every j > 0. The following claim shows that Enforcer can indeed follow the second part of his moves in Stage I.

Claim 4.5. Throughout Stage I there are at least (2/4 - o(1)) |C| free edges between every vertex in I and C.

Proof: Since [d.sub.A](v) < k for every v [member of] V throughout Stage I, it suffices to show that for every round i in this stage, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for every v [member of] [I.sub.i].

Let v [member of] [I.sub.i] be a vertex that was touched by Enforcer in his ith move. If Avoider does not touch v in his (i + 1)st move, then in every proper enumeration of the vertices in [I.sub.i] before Enforcer's (i + 1)st move, v will be among the first 4k vertices. Indeed, let u be a vertex that was placed after the first [s.sub.i] + 4k vertices of [I.sub.i-1] in the ith enumeration. By the properties of the enumeration and our assumption we get [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In case of equality we get [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Enforcer will then add v to [C.sub.i+1] since b > 4kn. So, v remains in I only if Avoider touches it in his (i + 1)st move and therefore every vertex can have edges attached to it by Enforcer in at most k rounds.

Now consider a vertex v [member of] [I.sub.i] for some i > 0 (the claim is trivial for i = 0). Since [I.sub.j+1] < |[C.sub.j+1]| [less than or equal to] |[C.sub.i]| for every j < i, the number of edges attached to v cannot be more than k [|[[C.sub.i]|/4k]] = (1/4 + o(1)) |[C.sub.i]|.

We now wish to examine the course of the game in which Avoider plays according to some fixed strategy and Enforcer plays according to the proposed strategy, in order to obtain a sufficient condition for Enforcer's win, thus proving the lemma. Note that if Enforcer plays according to Stage II of the strategy at any move before his lth, he wins the game. Assume, then, that this does not happen. It is immediate to observe that some properties hold exactly as in the monotone game.

Observation 4.6. The following properties hold throughout Stage I.

(i) After every move, by either player, every free edge has at least one endpoint in I.

(ii) Enforcer has no edges inside I.

(iii) T(0) = 0 and T(i + 1) > T(i).

The following claim is the strict analogue of Claim 4.2, showing that as I gets smaller, the average A-degree of its vertices becomes larger.

Claim 4.7. For every 0 [less than or equal to] j [less than or equal to] k - 2 the following holds. If for some i Enforcer plays his ith move according to Stage I of his strategy and 0 < |[I.sub.i]| < [9/10]n [([n/2b]).sup.j], then T(i) [greater than or equal to] j.

Proof: We prove the claim by induction on j. The claim trivially holds for j = 0, as T(i) [greater than or equal to] 0 for every i. Suppose now for contradiction that for some 1 [less than or equal to] j [less than or equal to] k - 2, the claim holds for j - 1, but not for j. Then there exists an integer i such that 0 < |[I.sub.i]| < [9/10]n [([n/2b]).sup.j], but T(i) < j.

As in the proof of Claim 4.2, we denote by [i.sub.0] [less than or equal to] i the minimal index such that T([i.sub.0]) [greater than or equal to] j - 1. Since the integer-valued weight function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is non-negative for [i.sub.0], and is strictly increasing for s [less than or equal to] i, we conclude that i - [i.sub.0] + 1 [less than or equal to] W(i) + 1 [less than or equal to] |[I.sub.i]| and thus between rounds [i.sub.0] and i Enforcer has claimed at most b|[I.sub.i]| < [9/20][n.sup.2] [([n/2b]).sup.j-1] edges.

We now show that according to his strategy Enforcer had to claim more edges than that during these rounds. We distinguish between the following cases:

For j = 1, Avoider could not have claimed any edge inside [C.sub.i], so the number of edges Enforcer had to claim is at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For j > 1, note that [i.sub.0] > 0. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] it means that Enforcer claimed a quadratic number of edges in the specified rounds (all edges inside [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], except at most kn edges that could have been claimed by Avoider). On the other hand, if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], note that Enforcer had to claim all the edges between [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] that were free before round [i.sub.0], except at most kn edges. By Claim 4.5 and the induction hypothesis, the number of these edges is at least

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In either case, we get a contradiction.

Let g be the maximal index such that |[I.sub.g]| > 0 and T(g) < k - 2 (there exists such an index since both inequalities hold for g = 0). The next claim shows that as the game goes on after the gth round, more and more vertices of A-degree k - 1 appear in the graph.

Claim 4.8. For every i [greater than or equal to] 0, after Avoider's (g + 1 + i)th move either Avoider's graph contains an [S.sub.k] or there are at least i vertices in [I.sub.g+i] of A-degree k - 1.

Proof: Let [v.sub.1],... ,[v.sub.t] denote the vertices of [I.sub.g+1] with A-degree at most k - 3 after the (g + 1)st round, and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If Avoider has not yet created an [S.sub.k], all vertices have A-degree at most k - 1, thus after the (g + 1)st round there are at least m vertices in [I.sub.g+1] with A-degree k - 1, as the average A-degree in [I.sub.g+1] is at least k - 2 by definition of g. Since all free edges have at least one endpoint in I, as long as Enforcer removes from I only vertices of A-degree at most k - 2, in every round after the (g + 1 + m)th the number of vertices of A-degree k - 1 is increased, or an [S.sub.k] appears in Avoider's graph. If Enforcer removes from I a vertex of A-degree at least k - 1, then if the maximal degree in Avoider's graph is k - 1 at that point, it will be increased to k in Avoider's subsequent move (if such a move exists).

By Claim 4.7 we get |[I.sub.g]| [greater than or equal to] [9/10]n [([n/2b]).sup.k-2]. Hence, either [I.sub.g] is of linear order and then |[F.sub.g]| = [THETA]([n.sup.2]) (since at most k|I| edges can be claimed inside I throughout Stage I), or |[I.sub.g]| = (1 - o(1))n and then by Claim 4.5 we get:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, the number of rounds remaining in the game after the gth round satisfies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

Using our assumption [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], a simple calculation yields (as k [greater than or equal to] 3):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

By Claim 4.8 we have that after Avoider's lth move there are at least l - g - 1 vertices of A-degree k - 1 in [I.sub.l-1]. Since every such vertex creates at least ([3/4] - o(1)) n unique threats, by using (1) and (2) we get that the number of threats after Avoider's lth move is at least

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

As already mentioned, if the maximal degree in [A.sub.l] is less than k, then Enforcer wins if and only if there are at least r threats after Avoider's lth move.

By definition of [f.sup.+] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by Claim 4.3, it is clear that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. However, in order to show that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] holds as well, we must show in addition that Enforcer has a winning strategy if b = [OMICRON](n). Indeed, if b = o(n) Enforcer wins no matter how he plays since Avoider will have [omega](n) edges in his final graph, so assume b = [THETA](n). Enforcer does the following: before the game starts he chooses an arbitrary set U [??] V of size \U\ = [(2b).sup.[k/k+1]]< n, and in each step he claims some arbitrary free edge with at least one endpoint outside U until he can no longer do so, i.e. until all free edges lie completely inside U. Then he pretends to start a new game on n' = [(2b).sup.[k/k+1]] vertices with bias [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] according to the strategy for the case b = [omega](n). This is not exactly a new game because there may be some edges inside U already claimed by Avoider, and the "new" game may start during Enforcer's move. However, since Avoider can claim only a constant number of edges incident to each vertex, and since Enforcer makes at most b additional steps before Avoider's first move in the new game, these factors have no significant effect. They only affect the case j = 1 in the proof of Claim 4.7, and it is easy to see that the analysis there is still valid. The number of free edges before the last round (i.e. r(n', b)) is also affected, but since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Enforcer wins regardless of the exact value of r.

5 An application of Fact 2.1

We mentioned in the introduction that Bednarska-Bzdega in [2] obtained bounds on the different threshold biases for general H-games. For every fixed graph H with at least two edges, let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where v(F) and e(F) denote the number of vertices and number of edges of the subgraph F, respectively. Bednarska-Bzdega proved the following ([2], Theorems 1.9 and 1.10):

(i) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(ii) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(iii) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] holds for infinitely many values of n.

In the proof of (iii) she uses her general criterion for Avoider's win and shows that for f = [cn.sup.1/mH] (for some constant c [greater than or equal to] 1), if r(n, f') > f, then Avoider wins the strict (1 : f') H-game played on the edges of [K.sub.n]. She uses two number theoretical facts to show that there always exists such an f' satisfying f' [less than or equal to] 4m(H)f ln f, and that for infinitely many values of n there exists such an f' satisfying f' [less than or equal to] 2f. She only considers the case m(H) > 1/2 (the other case is trivial), and so by applying Fact 2.1 we obtain the following corollary.

Corollary 5.1. If m(H) [less than or equal to] 1 then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. That is, we obtain the better bound for all n in this case. Note that m(H) [less than or equal to] 1 if and only if H is a

graph in which every connected component contains at most one cycle. Our results show that these bounds are far from being tight for the star game, except for the "improved" upper bound on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] given in Corollary 5.1, where we got exactly the same result. We proved the bound for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in our paper explicitly anyway, since it is straightforward to obtain by using Fact 2.1 and our other arguments. The gaps in (i) and (ii) are not very surprising, as these bounds are valid for every fixed graph H. However, at least the upper bound on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] cannot be improved in general, since it is tight for the case H = [K.sub.3]. In addition, the constant exponent 1/m(H) in both bounds of (iii), as well as in Corollary 5.1, cannot be improved in general, because for H = [P.sub.3] we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], as observed by Bednarska-Bzdega herself in [2]. In this paper we provided an infinite family of graphs for which this bound is tight.

6 Concluding remarks and open problems

In Section 4 we propose a very natural strategy for Enforcer in the k-star game to enforce the appearance of a vertex of large degree in Avoider's graph. In [5], Gebauer and Szabo use a very similar approach; they study the change of the average degree in Breaker's graph over some subset of vertices during the game and show that it cannot get too large, and thus Maker's graph has a large minimum degree. So, enforcing a large average degree (and thus the maximal degree) in Avoider's graph over a subset of vertices complements in a way the method of Gebauer and Szabo.

In this paper we show that for every sufficiently large n and every k [greater than or equal to] 3, the threshold biases [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are not of the same order, thus supporting the conjecture of Hefetz et al. from [6]. In that paper they also showed that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are of the same order for H = [K.sub.3]; we showed the same for H = [S.sub.k]. Observe that [H.sup.-] = [P.sub.3] for both H = [K.sub.3] and H = [S.sub.3], and so [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is of the same order in both cases. It would be interesting to further investigate the relation between the monotone H-games and the strict [H.sup.-] -games and to determine whether indeed there is a connection between the two. Note that for a general graph H, the graph [H.sup.-] is not uniquely determined (unlike the [K.sub.3 and [S.sub.3 cases) and so for different choices of [H.sup.-] there are different outcomes. Therefore, choosing the "correct" [H.sup.-] must also be considered.

In Theorem 1.1 we provided the bounds for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] that are tight up to a constant factor. We could actually get some better (tighter) bounds--for example, by refining Avoider's strategy we could show that the constant in the upper bound in all three cases is 1 + [epsilon], for any [epsilon] > 0, rather than 2--but since we could not close the gap completely we decided to provide slightly weaker bounds with simpler proofs. It would be nice to determine the exact values of [C.sub.1], [C.sub.2] and [C.sub.3] for which [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In addition, note that our results for the k-star game only hold for a constant k.

Let us comment on the case when k = k(n) tends to infinity along with n. Clearly, as long as the bias b satisfies b [less than or equal to] (1 - [epsilon])[n/k], Avoider is doomed as at the end of the game even the average degree of his graph will be larger than k. Thus [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] holds. On the other hand, Avoider could win when b [greater than or equal to] (1 + [epsilon])[n/k] provided he could keep all degrees asymptotically the same. This kind of discrepancy games were studied first by Erdos, and the following general result of Beck tells us the order of magnitude of the threshold biases when k = [omega](log n). He considered the game of Balancer (playing with bias p) and Unbalancer (playing with bias q) in which they claim elements of a board X.

Theorem 6.1 (Theorem 17.5 in [1]). Let F be an arbitrary N -uniform hypergraph. Balancer and Unbalancer play the (p : q) game: they alternate, Balancer takes p new points and Unbalancer takes q new points per move. Then Balancer, as the first player, can force that, at the end of the play, for every A [member of] F, his part in A is strictly between [[p+[epsilon]]/[p+q]]N and [[p-[epsilon]]/[p+q]]N, where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Avoider can use Balancer's strategy in the above game with p = 1, q [greater than or equal to] (1 + [epsilon])[n/k], N = n - 1 and |F| = n with F consisting of the edge sets of the stars of [K.sub.n]. An easy calculation shows that if k = [omega](log n), then [epsilon] can be chosen to satisfy [epsilon] = o(1). Thus we obtain [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for these values of k. The case [omega](1) = k = [OMICRON](log n) remains open.

Acknowledgements

The research was initiated at the 4th Emlektabla Workshop held in Tihany, August 6-9, 2012. The authors would like to thank Asaf Ferber and Milos Stojakovic for their useful comments and suggestions. Also, the authors would like to express their gratitude to the referees whose thorough remarks greatly improved the paper. Furthermore, Fact 2.2 was pointed out by one of the referees along with the remark about the case k [right arrow] [infinity] in the last section.

References

[1] J. Beck, Combinatorial Games: Tic-Tac-Toe Theory, Cambridge University Press, 2008

[2] M. Bednarska-Bzdega, Avoider-Forcer games on hypergraphs with small rank, Electronic Journal of Combinatorics, 21(1) (2014), P1.2.

[3] B. Bollobas, Random Graphs, Cambridge University Press, 2001.

[4] V. Chvatal and P. Erdos, Biased positional games, Annals of Discrete Mathematics 2 (1978), 221-228.

[5] H. Gebauer and T. Szabo, Asymptotic random graph intuition for the biased connectivity game, Random Structures and Algorithms, 35 (2009), 431-443.

[6] D. Hefetz, M. Krivelevich, M. Stojakovic and T. Szabo, Avoider-Enforcer: The rules of the game, Journal of Combinatorial Theory Series A 117 (2010), 152-163.

[7] D. Hefetz, M. Krivelevich and T. Szabo, Avoider-Enforcer games, Journal of Combinatorial Theory Series A 114 (2007), 840-853.

[8] S. Janson, T. Luczak, A. Rucinski, Random Graphs, John Wiley & Sons, Inc., 2000.

[9] M. Krivelevich and T. Szabo, Biased positional games and small hypergraphs with large covers, Electronic Journal of Combinatorics, 15 (2008), R70.

[10] D. B. West, Introduction to Graph Theory, Prentice Hall, 2001.

Andrzej Grzesik (1*) Mirjana Mikalacki (2[dagger]) Zoltan Lorant Nagy (3[double dagger]) Alon Naor (4[section]) Balazs Patkos (3,5[paragrapg]) Fiona Skerman (6[parallel])

(1) Theoretical Computer Science Dep., Fac. of Math. and Computer Science, Jagiellonian Univ., Krakow, Poland

(2) Department of Mathematics and Informatics, Fac. of Sciences, University of Novi Sad, Serbia

(3) Alfred Renyi Institute of Mathematics, Budapest, Hungary

(4) School of Mathematical Sciences, Raymond and Beverly Sackler Fac. of Exact Sciences, Tel Aviv University, Israel

(5) MTA-ELTE Geometric and Algebraic Combinatorics Research Group, Budapest, Hungary

(6) University of Oxford, Department of Statistics, Oxford, United Kingdom

received 10th July 2013, revised 29th Jan. 2015, accepted 9th Mar. 2015.

(*) Email: andrzej.grzesik@uj.edu.pl.

([dagger]) Email: mirjana.mikalacki@dmi.uns.ac.rs. Research partly supported by Ministry of Education and Science, Republic of Serbia, and Provincial Secretariat for Science, Province of Vojvodina.

([double dagger]) Email: nagy.zoltan.lorant@renyi.mta.hu. Supported by Hungarian National Scientific Research Funds (OTKA) grant 81310.

([section]) Email: alonnaor@post.tau.ac.il.

([paragraph]) Email: patkosb@cs.elte.hu and patkos@renyi.hu. Research supported by the Janos Bolyai Research Scholarship of the Hungarian Academy of Sciences.

([parallel]) Email: skerman@stats.ox.ac.uk.
COPYRIGHT 2015 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Grzesik, Andrzej; Mikalacki, Mirjana; Nagy, Zoltan Lorant; Naor, Alon; Patkos, Balazs; Skerman, Fion
Publication:DMTCS Proceedings
Article Type:Report
Date:Jan 1, 2015
Words:10136
Previous Article:Bootstrapping and double-exponential limit laws.
Next Article:Guarded subgraphs and the domination game.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters