Silvio Capobianco
email: silvio.capobianco@gmail.com

Multidimensional cellular automata and generalization of Fekete's lemma

Keywords: Mathematics Subject Classification 2000: 00A05, 37B15, 68Q80 subadditive function, product ordering, cellular automaton

Fekete's lemma is a well-known combinatorial result on number sequences: we extend it to functions defined on dtuples of integers. As an application of the new variant, we show that nonsurjective d-dimensional cellular automata are characterized by loss of arbitrarily much information on finite supports, at a growth rate greater than that of the support's boundary determined by the automaton's neighbourhood index.

Introduction

Let f : {1, 2, . . .} → [0, +∞). Fekete's lemma [START_REF] Fekete | Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten[END_REF][START_REF] Van Lint | A Course in Combinatorics[END_REF] states that, if f (n + k) ≤ f (n) + f (k) for every n and k, then

lim n→∞ f (n) n = inf n≥1 f (n) n . (1)
The consequences of this simple statement are many and deep, such as the definition of topological entropy for dynamical systems [START_REF] Koiran | The Topological Entropy of Iterated Piecewise Affine Maps is Uncomputable[END_REF] and Arratia's bound on the number of permutations avoiding a given pattern [START_REF] Arratia | On the Stanley-Wilf Conjecture for the Number of Permutations Avoiding a Given Pattern[END_REF]. More recently, in a joint work with T. Toffoli and P. Mentrasti [START_REF] Toffoli | When-and how-can a cellular automaton be rewritten as a lattice gas?[END_REF], we have made use of (1) to prove a result about cellular automata (CA). These are presentations of global dynamics in local terms: each global state is a d-dimensional configuration, and the global evolution rule changes the state locally at a site by considering only the states of neighbouring sites. The task of retrieving global properties from such local descriptions is in general very difficult, and often leads to undecidability issues. In [START_REF] Toffoli | When-and how-can a cellular automaton be rewritten as a lattice gas?[END_REF], we were especially concerned with surjectivity, a subject on which a vast and fascinating literature exists.

The most straightforward characterization of surjective CA (cf. [START_REF] Moore | Machine models of self-reproduction[END_REF][START_REF] Myhill | The converse of Moore's Garden-of-Eden theorem[END_REF]) follows from the compactness of the space of configurations: the global evolution function of a CA is surjective if and only if every pattern (i.e., sub-configuration on a finite region of the space) has at least one predecessor according to the evolution rule. From this "simple" argument, and from the properties of the group Z d , many beautiful theorems follow; of these, Moore-Myhill's theorem [START_REF] Moore | Machine models of self-reproduction[END_REF][START_REF] Myhill | The converse of Moore's Garden-of-Eden theorem[END_REF] and Maruoka-Kimura's balancement theorem [START_REF] Maruoka | Condition for Injectivity of Global Maps for Tessellation Automata[END_REF] deserve more than a mere citation, and shall be stated later in this paper.

The presence of "Garden-of-Eden patterns" can be restated by saying that nonsurjective CA lose variety within finite range, "variety" being the logarithm V (n) of the number of output states on a "patch" (finite connected region) of size n. This quantity is easily checked to be subadditive; we could thus apply [START_REF] Amoroso | Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures[END_REF] and deduce that, in nonsurjective CA, the "loss of variety" n -V (n) must, for n large enough, be larger that δn for some δ > 0, and in particular, larger than the size of the support's boundary determined by the neighborhood index. This loss, in turn, allows compressing the state of both the support above and its boundary, into as much as it can be encoded by the support alone. Relying on this fact, we have devised a general algorithm [START_REF] Toffoli | When-and how-can a cellular automaton be rewritten as a lattice gas?[END_REF] to translate from a presentation using an n-inputs, 1-output local map (i.e., CA) to one employing n-inputs, n-outputs events, characteristic of a different class of presentations, specifically, that of lattice gases (LG).

In this paper, we state and prove a multivariate version of Fekete's lemma. The motivation for this, is to provide a support to the conjecture that the translation algorithm in [START_REF] Toffoli | When-and how-can a cellular automaton be rewritten as a lattice gas?[END_REF] could be extended to arbitrary dimension; in particular, we want to prove that the loss of variety of nonsurjective CA grows sufficiently large to encode the boundary, regardless of the dimension of the space. This is not immediate, because for d > 1 the boundary grows with the support; but seems feasible, because the boundary grows, in a certain sense, "less" than the support-which, incidentally, is one of the properties of Z d that make Moore-Myhill's theorem true. To prove our generalization, we rearrange a proof of (1) so that it works on sequences of integer d-tuples, after a suitable ordering on these is defined. As applications for the newfound formula, we prove two facts. The first one tells that loss of variety for d-dimensional nonsurjective CA is sufficient, on supports large enough, to allow encoding the state of the boundary: which is noteworthy, because for d > 1 the size of the boundary increases with that of the region. Incidentally, we get a criterion for CA surjectivity-if the loss of variety is bounded, then the CA is surjective-which, as far as we know, is first stated in this paper. The second fact is that the Weyl pseudodistance, introduced by [START_REF] Blanchard | Cellular automata in Cantor, Besicovitch, and Weyl topological spaces[END_REF] in the study of CA dynamics and defined as an upper limit, is in fact a limit: this property is not shared by its main "competitor", the Besicovitch pseudodistance.

Fekete's lemma, multivariate

A subadditive, nonnegative, univariate function f (n) can be thought of as the maximum information achievable with n observations of some given phenomenon. Then Fekete's lemma says that the average maximum information per observation converges to its greatest lower bound.

To extend (1) to several variables-which, at the best of our knowledge, has never been done beforewe first need to understand what the meaning of an inequality a ≤ b should be when a and b are vectors; this should reduce to the standard ordering of integers in the case of unidimensional arrays. Next, we have to identify a notion of limit which is in accord with that meaning. Finally, we must write down a version of (1) that keeps into account the number d of components, and reduces to (1) for d = 1.

Let Z + = Z ∩ (0, +∞). Consider the product ordering on Z d + defined by x ≤ π y iff x i ≤ y i for every i ∈ {1, . . . , d}. This is the kind of ordering used, e.g., in linear programming, by writing Ax ≤ b to indicate a set of constraints a 1,1 x 1 + . . . + a 1,n x n ≤ b 1 , . . . , a m,1 x 1 + . . . + a m,n x n ≤ b m ; it is also the finest ordering that makes the projections monotonic. Observe that

Z d = (Z d + , ≤ π ) is a directed set, i.e., for any two x, y ∈ Z d + there exists z ∈ Z d + such that both x ≤ π z and y ≤ π z. If X = (X, ≤) is a
directed set and f : X → R, the lower and upper limit of f in X are defined as usual, i.e.,

lim inf x∈X f (x) = sup x∈X inf y≥x f (y) and lim sup x∈X f (x) = inf x∈X sup y≥x f (y) ; moreover, f has limit L ∈ R in X , written lim x∈X f (x) = L, if for every ε > 0 there exists x ε ∈ X such that |f (x) -L| < ε for every x ≥ x ε . For example, if r 1 , . . . , r d ∈ N = Z + ∪ {0} are fixed, then lim (x1,...,x d )∈Z d (x 1 + r 1 ) • • • (x d + r d ) x 1 • • • x d = 1 . (2)
It follows from the definitions that lim inf x∈X f (x) ≤ lim sup x∈X f (x), and that

lim x∈X f (x) = L iff lim inf x∈X f (x) = lim sup x∈X f (x) = L.
In this case, the limit L can be recovered on any path going to infinity. More formally, suppose that a sequence {x n } n∈N ⊆ X satisfies the following property: for every x ∈ X there exists n x ∈ N such that x n ≥ x for every n > n x . Then the sequence {f

(x n )} n∈N ⊆ R converges to L in the usual sense. Theorem 1 Let f : Z d + → [0, +∞) satisfy f (x 1 , . . . , x j + y j , . . . , x d ) ≤ f (x 1 , . . . , x j , . . . , x d ) + f (x 1 , . . . , y j , . . . , x d ) (3)
for every x 1 , . . . , x n , y j ∈ Z + , j ∈ {1, . . . , d}. Then

L = lim (x1,...,x d )∈Z d f (x 1 , . . . , x d ) x 1 • • • x d (4)
exists, and equals

inf x1,...,x d ∈Z+ f (x 1 , . . . , x d ) x 1 • • • x d . (5)
Proof: Because of (3), for every j ∈ {1, . . . , d}, x 1 , . . . , x d ∈ Z + , if x j = qt + r with q ∈ N and r ∈ Z + , then

f (x 1 , . . . , x j , . . . , x d ) ≤ q • f (x 1 , . . . , t, . . . , x d ) + f (x 1 , . . . , r, . . . , x d ) . (6)
Fix t 1 , . . . , t d ∈ Z + . For each (x 1 , . . . , x d ) ∈ Z d + , d pairs (q j , r j ) ∈ N × Z + are uniquely determined by x j = q j t j + r j and 1 ≤ r j ≤ t j . By repeatedly applying [START_REF] Koiran | The Topological Entropy of Iterated Piecewise Affine Maps is Uncomputable[END_REF] to all of the x j 's, for y (0) j = r j and y

(1) j = t j we find f (x 1 , . . . , x d ) ≤ α∈{0,1} d q α1 1 • • • q α d d • f y (α1) 1 , . . . , y (α d ) d . (7)
Note how, on the right-hand side of [START_REF] Maruoka | Condition for Injectivity of Global Maps for Tessellation Automata[END_REF], each occurrence of f has k arguments chosen from the t j 's and dk chosen from the r j 's, is multiplied by the q j 's corresponding to the t j 's, and is bounded from above by the constant ). By dividing both sides of ( 7) by

M = t 1 • • • t d • f (1, . . . , 1
x 1 • • • x d we get f (x 1 , . . . , x d ) x 1 • • • x d ≤ q 1 • • • q d x 1 • • • x d f (t 1 , . . . , t d ) + M • α∈{0,1} d \{1 d } q α1 1 • • • q α d d x 1 • • • x d . (8)
Now, by construction, lim xj →∞ q j /x j = 1/t j . If all the x j 's are large enough, the first summand in [START_REF] Moore | Machine models of self-reproduction[END_REF] becomes very close to f (t 1 , . . . , t d )/t 1 • • • t d , and the other ones become very small; in other words, for every ε > 0, there exist x

(ε) 1 , . . . , x (ε)
d ∈ Z + such that, if x i ≥ x (ε) i for each i = 1, . . . , d, then f (x 1 , . . . , x d ) x 1 • • • x d < f (t 1 , . . . , t d ) t 1 • • • t d + ε .
From this and the definition of ≤ π follows lim sup

(x1,...,x d )∈Z d f (x 1 , . . . , x d ) x 1 • • • x d ≤ f (t 1 , . . . , t d ) t 1 • • • t d ;
this is true whatever the t j 's are, hence lim sup

(x1,...,x d )∈Z d f (x 1 , . . . , x d ) x 1 • • • x d ≤ inf t1,...,t d ∈Z+ f (t 1 , . . . , t d ) t 1 • • • t d .
Equality between ( 4) and ( 5) follows then from

inf t1,...,t d ∈Z+ f (t 1 , . . . , t d ) t 1 • • • t d ≤ lim inf (x1,...,x d )∈Z d f (x 1 , . . . , x d ) x 1 • • • x d .

✷

We propose the following interpretation of Theorem 1. For a function f satisfying (3), the quantity f (x 1 , . . . , x j , . . . , x d ) can be thought of as the maximum joint information obtainable by the observations of d independent observers, when the j-th of them has performed x j observation. Theorem 1 then says that the average maximum joint information per observation per observer converges to its greatest lower bound. Note that, for d = 1, Theorem 1 is the same as Fekete's lemma.

Corollary 2 Let f and L be as in Theorem 1. If lim n→∞ x j,n = +∞ for every j ∈ {1, . . . , d}, then

lim n→∞ f (x 1,n , . . . , x d,n ) x 1,n • • • x d,n = inf n≥1 f (x 1,n , . . . , x d,n ) x 1,n • • • x d,n = L . (9)
In particular,

lim n→∞ f (n, . . . , n)/n d = inf n≥1 f (n, . . . , n)/n d = L.
Proof: Straightforward from Theorem 1, the observations above, and

inf x1,...,x d ∈Z+ f (x 1 , . . . , x d ) x 1 • • • x d ≤ inf n≥1 f (x 1,n , . . . , x d,n ) x 1,n • • • x d,n , which follows from A ⊇ B implying inf A ≤ inf B. ✷ 3

An application to cellular automata

A cellular automaton (briefly, CA) is a quadruple A = d, Q, N , f where the dimension d > 0 is an integer, the set of states Q is finite and has at least two distinct elements, the neighbourhood index N = {ν 1 , . . . , ν n } is a finite subset of Z d , and the local evolution function

f maps Q n into Q. A global evolution function F is induced by f of the space Q Z d of d-dimensional configurations by F (c)(x) = f (c(x + ν 1 ), . . . , c(x + ν n )) . (10)
A is said to be surjective if For every finite

F is. For example, if d = 1, Q = {0, 1}, N = {1}, f (x) = x, then d, Q, N , f
E ⊆ Z d , calling E + N = {x + ν | x ∈ E, ν ∈ N }, a function F E : Q E+N → Q E is induced
by f , again by applying [START_REF] Toffoli | When-and how-can a cellular automaton be rewritten as a lattice gas?[END_REF]. Observe that the number |F E (Q E+N )| of patterns over E obtainable by applying [START_REF] Toffoli | When-and how-can a cellular automaton be rewritten as a lattice gas?[END_REF] does not depend on the displacement of E along Z d , i.e., if

x + E = {x + y | y ∈ E}, then |F x+E (Q x+E+N )| = |F E (Q E+N )|. Put E(x 1 , . . . , x d ) = {z ∈ Z d | 0 ≤ z i < x i ∀i}.
Call right d-polytope any set of the form H = y + E(x 1 , . . . , x d ) for some y ∈ Z d . (Here, "right" has the same meaning as in "right triangle".) If N is contained in a right d-polytope of sides r 1 , . . . , r d , then E(x 1 , . . . , x d ) + N is contained in a right d-polytope of sides x 1 + r 1 , . . . , x d + r d , which is the disjoint union of E(x 1 , . . . , x d ) and a boundary. It is well-known [START_REF] Moore | Machine models of self-reproduction[END_REF][START_REF] Myhill | The converse of Moore's Garden-of-Eden theorem[END_REF] that A is surjective iff F E is surjective for every right d-polytope E. From this characterization many more follow, two of which at least deserve some words.

Moore-Myhill's theorem [START_REF] Moore | Machine models of self-reproduction[END_REF][START_REF] Myhill | The converse of Moore's Garden-of-Eden theorem[END_REF] states that a CA is surjective if and only if for no two different patterns p i on the same d-hypercube E may happen that

c i | E = p i , c 1 | C\E = c 2 | C\E , and F (c 1 ) = F (c 2 )
. This has the important consequence that injective CA are surjective. Note that a key part of the proof relies on the fact that any boundary of fixed "range" has a lower growth rate than the right d-polytope it surrounds.

Maruoka-Kimura's balancement theorem [START_REF] Maruoka | Condition for Injectivity of Global Maps for Tessellation Automata[END_REF] states that in a surjective CA each pattern on a given rectangular support has the same number of predecessors. Note that, in the proof of this theorem, the previous one is used. If N is contained in a right d-polytope of sides r 1 , . . . , r d (which we may call N ′ ) we may identify the original CA with one having neighbourhood index N ′ ; then the CA is surjective iff for all x 1 , . . . ,

x d ∈ Z + , p ∈ Q E(x1,...,x d ) F -1 E(x1,...,x d ) (p) = |Q| (x1+r1)•••(x d +r d )-x1•••x d .
Let A = d, Q, N , f be a CA. If A is nonsurjective, then there must exist a support of suitable size where not every possible pattern is reachable, i.e., a part of the state is lost. In the 1D case [START_REF] Toffoli | When-and how-can a cellular automaton be rewritten as a lattice gas?[END_REF], such lost state is proved to be ultimately as much as the boundary can transport; which allowed devising a CA-to-LG conversion algorithm. If the technique employed there is to be extended to higher dimension, then we must determine whether such large a loss can still be achieved.

Call output size of f on a right d-polytope of sides x 1 , . . . , x d the quantity

Out f (x 1 , . . . , x d ) = F E(x1,...,x d ) Q E(x1,...,x d )+N . Then A is surjective iff Out f (x 1 , . . . , x d ) = |Q| x1•••x d for every x 1 , . . . , x d ∈ Z + .
By switching to a logarithmic measure unit, we can associate to A a loss of variety on a right d-polytope of sides x 1 , . . . , x d defined as

Λ A (x 1 , . . . , x d ) = x 1 • • • x d -log |Q| Out f (x 1 , . . . , x d ) . (11)
Observe how such loss is measured in qits (with q = |Q|), a qit being the amount of information carried by a q-states device; n qits correspond to n log 2 q bits. Theorem 3 Let A = d, Q, N , f be a CA. Define Λ A as by [START_REF] Van Lint | A Course in Combinatorics[END_REF]. Then 1. either A is surjective and Λ A is identically zero, 2. or A is nonsurjective and for every K ≥ 0, r 1 , . . . , r d ∈ N, there exist t 1 , . . . , t d ∈ Z + such that, if x j ≥ t j for every j ∈ {1, . . . , d}, then

Λ A (x 1 , . . . , x d ) ≥ (x 1 + r 1 ) • • • (x d + r d ) -x 1 • • • x d + K . ( 12
)
Proof: Put q = |Q|. Since a pattern over E(x 1 , . . . , x j + y j , . . . , x d ) can always be seen as the joining of a pattern over E(x 1 , . . . , x j , . . . , x d ) and another one over E(x 1 , . . . , y j , . . . , x d ), there cannot be more patterns obtainable over the former than pairs of patterns obtainable over the latter, i.e.,

Out f (x 1 , . . . , x j + y j , . . . , x d ) ≤ Out f (x 1 , . . . , x j , . . . , x d ) • Out f (x 1 , . . . , y j , . . . , x d )
whatever x 1 , . . . , x n , y j ∈ Z + , j ∈ {1, . . . , d} are; consequently, log q Out f is subadditive in each of its arguments (and nonnegative). Let

λ f = lim (x1,...,x d )∈Z d log q Out f (x 1 , . . . , x d ) x 1 • • • x d , (13)
whose existence and value are given by Theorem 1; observe that λ f ≤ 1, and A is surjective iff λ f = 1. Suppose A is nonsurjective. Let δ ∈ (λ f , 1). Choose t 1 , . . . , t d ∈ Z + so that, for every

x 1 ≥ t 1 , . . . , x d ≥ t d , both log q Out f (x 1 , . . . , x d ) x 1 • • • x d ≤ δ (14)
and

(x 1 + r 1 ) • • • (x d + r d ) -x 1 • • • x d + K x 1 • • • x d ≤ 1 -δ (15)
are satisfied, the latter following from (2). Then, for such x 1 , . . . , x d ,

x 1 • • • x d -log q Out f (x 1 , . . . , x d ) ≥ (x 1 • • • x d )(1 -δ) ≥ (x 1 + r 1 ) • • • (x d + r d ) -x 1 • • • x d + K . ✷ Corollary 4 Let A be as in Theorem 3. 1. If Λ A is bounded, then A is surjective. 2. If A is nonsurjective, then there exist k 1 , . . . , k d such that, if x i ≥ k i for all i, then Λ A (x 1 , . . . , x d ) ≥ |E(x 1 , . . . , x d ) + N | -|E(x 1 , . . . , x d )|.
Proof: Point 1 follows from point 2 of Theorem 3. For point 2, put K = 0 and choose r 1 , . . . , r d so that N ⊆ z + E(r 1 , . . . , r d ) for some z ∈ Z d . ✷

The unbounded growth of Λ A for nonsurjective A could also be proved via the following argument, akin to the one used in the proof of Moore-Myhill's theorem. Let π be a GoE pattern with support E(k 1 , . . . , k d ):

then Out f (k 1 , . . . , k d ) ≤ q k -1, where k = k 1 • • • k d .
For every n ≥ 1, none of the n d portions of the image via (10) of a pattern over E(nk 1 , . . . , nk d ) + N can equal π, so in fact

Out f (nk 1 , . . . , nk d ) ≤ (q k -1) n d ∀n ≥ 1 ; (16) this implies Λ A (nk 1 , . . . , nk d ) ≥ n d (k -log q (q k -1)) ∀n ≥ 1 ,
and the factor in parentheses is a positive constant. However, the proof based on Fekete's lemma gives us more comprehensive information about the behaviour of A. In fact, if we only rely on the existence of a GoE pattern, we only get a family of values on which Λ A grows arbitrarily large; instead, Fekete's lemma immediately tells us that Λ A grows ultimately larger than any given value. To get such thing from ( 16), we must first rewrite each x i as nk i + r i , then employ

Out f (x 1 , . . . , x d ) ≤ (q k -1) n d • q x1•••x d -n d •k .
Point 2 of Corollary 4 says that, for (x 1 , . . . , x d ) satisfying both ( 14) and ( 15), the loss of variety is at least the size of the boundary: this is precisely the fact used in [START_REF] Toffoli | When-and how-can a cellular automaton be rewritten as a lattice gas?[END_REF], and supports the conjecture that a similar construction can be carried out in dimension d > 1. On the other hand, since surjectivity of ddimensional CA is only decidable when d = 1 [START_REF] Amoroso | Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures[END_REF][START_REF] Kari | Reversibility of 2D cellular automata is undecidable[END_REF], no algorithm exists to determine, given an arbitrary multidimensional CA, whether its loss of variety ( 11) is bounded.

A consideration on the Weyl pseudodistance

The Weyl pseudodistance on d-dimensional configurations is defined as

d W (c 1 , c 2 ) = lim sup (x1,...,x d )∈Z d max y∈Z d |{z ∈ y + E(x 1 , . . . , x d ) | c 1 (z) = c 2 (z)}| x 1 • • • x d . (17)
This is an extension of the definition given in [START_REF] Blanchard | Cellular automata in Cantor, Besicovitch, and Weyl topological spaces[END_REF] for one-dimensional configurations. Essentially, d W (c 1 , c 2 ) is the upper limit of the maximum probability of getting different values for the c i 's when choosing at random a point in a given (x 1 , . . . , x d )-hypercube. Note that d W is translation invariant, i.e., d

W (c x 1 , c x 2 ) = d W (c 1 , c 2 ) for every x ∈ Z d , c 1 , c 2 ∈ Q Z d ,
where c x (z) = c(x + z) for all z ∈ Z d : this is impossible for any distance inducing the product topology (cf. [START_REF] Blanchard | Cellular automata in Cantor, Besicovitch, and Weyl topological spaces[END_REF]). Moreover, CA induce continuous transformations of the quotient space obtained by identifying configurations having Weyl distance zero, and information about the behaviour of the CA can be inferred from that of the induced function.

The Weyl pseudodistance has been neglected in favor of the Besicovitch pseudodistance defined, for d = 1 (cf. [START_REF] Blanchard | Cellular automata in Cantor, Besicovitch, and Weyl topological spaces[END_REF]), as

d B (c 1 , c 2 ) = lim sup n≥1 |{x ∈ [-n, . . . , n] | c 1 (x) = c 2 (x)}| 2n + 1 ,
which is also translation invariant and induces a quotient space with better topological properties, on which CA also induce continuous transformations whose properties may reflect those of the original. However, there is a feature distinctive of d W which is not shared by d B .

Theorem 5 For any

c 1 , c 2 ∈ Q Z d , d W (c 1 , c 2 ) = lim (x1,...,x d )∈Z d max y∈Z d |{z ∈ y + E(x 1 , . . . , x d ) | c 1 (z) = c 2 (z)}| x 1 • • • x d . ( 18
)
Moreover,

d W (c 1 , c 2 ) = inf x1,...,x d ∈Z+ max y∈Z d |{z ∈ y + E(x 1 , . . . , x d ) | c 1 (z) = c 2 (z)}| x 1 • • • x d . ( 19
) Proof: For y ∈ Z d , x 1 , . . . , x d ∈ Z + , put Φ y (x 1 , . . . , x d ) = |{z ∈ y + E(x 1 , . . . , x d ) | c 1 (z) = c 2 (z)}| and f (x 1 , . . . , x d ) = max y∈Z Φ y (x 1 , . . . , x d ) . Then d W (c 1 , c 2 ) = lim sup (x1,...,x ) d∈Z d f (x 1 , . . . , x d ) x 1 • • • x d .
Moreover, if (z (j) ) i = x j • δ j i (δ j i being the Kronecker symbol) then Φ y (x 1 , . . . , x j + x ′ j , . . . , x d ) = Φ y (x 1 , . . . , x j , . . . , x d ) + Φ y+z (j) (x 1 , . . . , x ′ j , . . . , x d ) , so that f (x 1 , . . . , x j + x ′ j , . . . , x d ) ≤ f (x 1 , . . . , x j , . . . , x d ) + f (x 1 , . . . , x ′ j , . . . , x d ) , because the maximum over y is a subadditive function and is invariant by translations of y by a fixed value. By Theorem We are now going to check that d B is not, in general, a limit. Let x n = n k=1 2 k ; let c 1 (x) = 0 for every x ∈ Z and let

c 2 (x) =        0 if x 2k < x ≤ x 2k+1 , 1 if x 2k-1 < x ≤ x 2k , 1 if x = 0 , c 2 (-x) if x < 0 .
For n odd, the interval [0, x n ] contains twice as many points where c 2 (x) = 0 than points where c 2 (x) = 1; for n even, the interval [1, x n ] contains twice as many points where c 2 (x) = 1 than points where c 2 (x) = 0. From this follows that d B (c 1 , c 2 ) ≥ 2/3 but lim inf n∈N |{|x| ≤ n, c 1 (x) = c 2 (x)}|/(2n + 1) ≤ 1/3. (With a bit more patience one can see that equalities actually hold.)

As a consequence of Theorem 5 and Corollary 2, the Weyl pseudodistance can be obtained as a limit on any sequence of right d-polytopes which "grow infinitely large in all directions".

  is the shift cellular automaton and F (c)(x) = c(x + 1) is the shift map, which is surjective; on the other hand, for same d and Q, N = {0, 1}, and f (a, b) = a • b, we get a nonsurjective CA, because if c(x) is 0 for x = 0 and 1 otherwise, then F (c) = c for any c.

Corollary 6

 6 Let lim n→∞ x i,n = +∞ for each i ∈ {1, . . . , d}. Thenlim n→∞ max y∈Z d |{z ∈ y + E(x 1,n , . . . , x d,n ) | c 1 (z) = c 2 (z)}| x 1,n • • • x d,n = d W (c 1 , c 2 ) .In particular,lim n→∞ max y∈Z d |{z ∈ y + E(n, . . . , n) | c 1 (z) = c 2 (z)}| n d = d W (c 1 , c 2 ) .

  1, inf x1,...,x d ∈Z+ f (x 1 , . . . , x d ) x 1 • • • x d = lim

(x1,...,x d )∈Z d f (x 1 , . . . , x d ) x 1 • • • x d = lim sup (x1,...,x d )∈Z d f (x 1 , . . . , x d ) x 1 • • • x d ,

which yields (18) and (19). ✷

Acknowledgements

The author was partly supported by the project "The Equational Logic of Parallel Processes" (nr. 060013021) of The Icelandic Research Fund. We also thank Tullio Ceccherini-Silberstein, Tommaso Toffoli, Patrizia Mentrasti, Luca Aceto, Anna Ingólfsdóttir, Anders Claesson, Magnús Már Halldórsson, MohammadReza Mousavi, and the two anonymous referees for the many helpful suggestions and encouragements.


Helmut Prodinger
email: hproding@sun.ac.za

The location of the first maximum in the first sojourn of a Dyck path

Keywords: Dyck path, maximum, location, generating function, Mellin transform

For Dyck paths (nonnegative symmetric) random walks, the location of the first maximum within the first sojourn is studied. Generating functions and explicit resp. asymptotic expressions for the average are derived. Related parameters are also discussed.

Introduction

In the recent paper [START_REF] Randon-Furling | Distribution of the time at which a Brownian motion is maximal before its first-passage time[END_REF], the distribution of the time at which a Brownian motion is maximal before its first-passage time was studied.

We undertake a related study, by investigating the discrete cousins, namely Dyck paths (nonnegative lattice paths, returning to the x-axis). These celebrated combinatorial objects, enumerated by Catalan numbers 1 N +1 2N N , when their length is 2N , are known by many names, including also Dyck words, nonnegative symmetric random walks, etc. They are also important in Computer Science, since they code planar trees (and binary trees), see e.g. [START_REF] De Bruijn | The average height of planted plane trees[END_REF].

We find an explicit form of the generating function F (z, u), where the coefficient of z n u k is the number of Dyck paths of length n such that the first maximum within the first sojourn occurs at time (=step) k. From it, we compute the expectation explicitly and asymptotically. It is roughly 1/4 of the length of the walk.

We also compute the average height of the first sojourn, explicitly and asymptotically. (The average height of the whole path has been known for a long time.)

For reason of comparison, we also investigate the location of the first maximum of the whole path, which is roughly at 1/2 of the length of the walk.

In a final section, we show how to extend these results from the first sojourn to the r-th sojourn. The parameters here are based on assuming all Dyck paths with at least r sojourns to be equally likely. Most of the old computations can be used and only have to be adapted slightly.

Generating functions

We study the parameter position of the first maximum during the first sojourn of a Dyck path of length n, which we denote by R. Since this parameter makes no sense for the empty path, we assume that n ≥ 1.

Lemma 1

The generating function F (z, u) where z marks the length of the Dyck path and u the parameter R, is given by

F (z, u) = C(z) 1 -4z 2 1 -4z 2 u 2 h≥1 z 2h u h λ h 1 (zu) -λ h 2 (zu) λ h+1 1 (z) -λ h+1 2 (z) ,
where

C(z) = 1 - √ 1 -4z 2 2z 2 , λ 1,2 (z) = 1 ± √ 1 -4z 2 2 .
Proof. Let ϕ h,i (z) be the generating function of paths of height ≤ h, ending at level i. We are in particular interested in C h (z) = ϕ h,h (z); such a path clearly has height = h. The following system of equations is easy to obtain (see, e.g., [START_REF] Panny | The expected height of paths for several notions of height[END_REF] for similar calculations):

       1 -z -z 1 -z -z 1 -z . . . -z 1               ϕ h,0 (z) ϕ h,1 (z) ϕ h,2 (z) . . . ϕ h,h (z)        =        1 0 0 . . . 0        (2.1)
Solving the system with Cramer's rule produces the form

C h (z) = z h √ 1 -4z 2 λ h+2 1 (z) -λ h+2 2 (z)
.

For the rest of the proof, we consider the decomposition according the the first occurrence of the height h of the first sojourn (for this part, z is replaced by zu, to count the position where this happens)

F (z, u) = h≥2 zuC h-2 (zu)zuC h-1 (z)z • C(z) + z 2 uC(z),
which is equivalent to the announced statement. ✷ Theorem 1 The average value R N of the parameter R, assuming that all b N = 1 N +1

2N

N Dyck paths of length 2N are equally likely, is given by

R N = 1 b N -4 N + 2 2N N - k≥1 d(k) 2N + 1 N -k + 2 k≥1 k d(k) 2N N -k - 2N N -1 -k ,
where d(k) denotes the number of (positive) divisors of the integer k.

Proof. We differentiate the function F (z, u) w.r.t. u, followed by u := 1, which is (apart from normalization) the generating function of the averages R N :

G(z) := ∂ ∂u F (z, u) u=1 = -4z 2 C(z) h≥1 z 2h (λ h 1 (z) -λ h 2 (z))(λ h+1 1 (z) -λ h+1 2 (z)) + C(z)(1 -4z 2 ) h≥1 hz 2h (λ h 1 (z) -λ h 2 (z))(λ h+1 1 (z) -λ h+1 2 (z)) + C(z) 1 -4z 2 h≥1 2hz 2h+2 (λ h-1 1 (z) + λ h-1 2 (z)) (λ h 1 (z) -λ h 2 (z)) 2 (λ h+1 1 (z) -λ h+1 2 (z)) .
With the substitution z = v/(1 + v 2 ), this expression becomes nicer:

G(z) = -4v h≥1 v 2h+1 (1 -v 2h )(1 -v 2h+2 ) + (1 -v 2 ) 2 h≥1 hv 2h (1 -v 2h )(1 -v 2h+2 ) + (1 -v 2 ) h≥1 2hv 2h+2 (1 + v 2h-2 ) (1 -v 2h ) 2 (1 -v 2h+2 ) = - 4v 4 (1 -v 2 ) 2 - (1 + v 2 ) 2 1 -v 2 h≥1 v 2h 1 -v 2h + 2(1 + v 2 ) h≥1 hv 2h (1 -v 2h ) 2 .
The last step was done by partial decomposition and a few rearrangements. Now note that

h≥1 v 2h 1 -v 2h = k≥1 d(k)v 2k and h≥1 hv 2h (1 -v 2h ) 2 = k≥1 k d(k)v 2k .
To read off coefficients, we observe that

[z n ]G(z) = [v n ](1 -v 2 )(1 + v 2 ) n-1 G(z(v));
this can be justified either by the Lagrange inversion formula or formal residue calculus. Now, since we have contributions only for even n = 2N , we can continue:

[z n ]G(z) = [v n ](1 -v 2 )(1 + v 2 ) n-1 G(z(v)) = [v N ](1 + v) 2N -1 - 4v 2 1 -v -(1 + v) 2 h≥1 v h 1 -v h + 2(1 -v 2 ) h≥1 hv h (1 -v h ) 2 = -4 N -2 k=0 2N -1 k - k≥1 d(k) 2N + 1 N -k + 2 k≥1 k d(k) 2N N -k - 2N N -1 -k .
The final formula follows from simplifying the first sum. ✷

Asymptotics

In the paper [START_REF] De Bruijn | The average height of planted plane trees[END_REF] we find the procedure how to compute asymptotics of such sums. (See also [START_REF] Flajolet | Analytic Combinatorics[END_REF].)

We use the following approximation

-2N +1 N -k + 2k 2N N -k -2k 2N N -1-k 2N N ∼ exp(-x 2 ) -2 + 4x 2 + 1 √ N (4x -4x 3 ) + 1 N (1 -9x 2 + 19 3 x 4 - 2 3 x 6 ) , (3.1)
where x = k/ √ N , and it holds for |k| ≤ N 1 2 +ε , and for other values of k, the expression is negligible (exponentially small). Maple could produce this expansion, and more terms would be available. In [START_REF] Prodinger | Some analytic techniques for the investigation of the asymptotic behaviour of tree parameters[END_REF], a procedure is described how to obtain such an approximation efficiently.

A key ingredient to the asymptotics is now the sum

S := k≥1 d(k)e -k 2 /N -2 + 4 k 2 N + 1 √ N 4 k √ N -4 k 3 N 3/2 + 1 N 1 - 9k 2 N + 19k 4 3N 2 - 2k 6 3N 3 .
This can be attacked with the Mellin transform. Writing again x = 1/ √ N , it becomes a harmonic sum in the notation of [START_REF] Flajolet | Mellin transforms and asymptotics: Harmonic sums[END_REF];

S * = ζ 2 (s) (s -1)Γ s 2 + further terms . (Note that k≥1 d(k)k -s = ζ 2 (s).)
The asymptotics of S can be recovered by computing residues of S * x -s (at s = 1 and s = 0):

S ∼ √ π x - 3 2 + further terms.
The final asymptotic formula for the average R N of the parameter R follows from this by multiplying by (N + 1), and taking care of the first two explicit terms, for which Stirling's formula applies. Most of this can be done by Maple. The final result is Theorem 2 The average value R N of the parameter R when considering all Dyck paths of lengths 2N to be equally likely, is given by

R N ∼ N 2 - √ πN 6 - 1 12 log N + 10 9 - γ 4 , (3.2)
with more terms being available if necessary. (Smaller terms in (3.1) translate into smaller terms in (3.2); we computed actually more terms and stopped at an arbitrary moment to display them, as they become more and more involved.)

So, roughly, we expect the parameter to be about 1/4 of the length of the Dyck path.

Higher moments could also be computed, by higher derivatives of F (z, u), but we did not do it, because the expressions become complicated.

The height of the first sojourn

The height of Dyck paths has been studied for some 35 years: De Bruijn, Knuth and Rice [START_REF] De Bruijn | The average height of planted plane trees[END_REF] showed that the average height is asymptotic to √ πN -3 2 (it is one less than the height of the corresponding planar tree).

However, it does not seem that the height of the first sojourn has been studied. Thus, we briefly address this here. Let A h (z) be the generating function of Dyck words of height ≤ h, and B h (z) be the generating function of Dyck words where the first sojourn has height ≤ h. Then, by the fundamental decomposition of Dyck words w.r.t. the first return to the origin,

B h (z) = z 2 A h-1 C(z).
Now, it is known (and easy to derive via the system (2.1)) that

A h (z) = λ h+1 1 (z) -λ h+1 2 (z) λ h+2 1 (z) -λ h+2 2 (z)
.

Consequently,

B h (z) = v 2 1 -v 2h 1 -v 2h+2 ,
again with the substitution z = v/(1 + v 2 ). The generating function of Dyck words where the height of the first sojourn is > h, is then

C(z) -1 -B h (z) = v 2 (1 -v 2 ) v 2h 1 -v 2h+2 .
The generating function of the averages (apart from normalization by b N ) is obtained by summing this up over h ≥ 0, viz.

(1 -v 2 ) h≥1 v 2h 1 -v 2h = (1 -v 2 ) k≥1 d(k)v 2k .

Now we must look at the coefficient of z

2N : [z 2N ](1 -v 2 ) h≥1 v 2h 1 -v 2h = [v 2N ](1 -v 2 )(1 + v 2 ) 2N -1 (1 -v 2 ) k≥1 d(k)v 2k = [v N ](1 -v) 2 (1 + v) 2N -1 k≥1 d(k)v k = k≥1 d(k) 2N -1 N -k -2 2N -1 N -1 -k + 2N -1 N -2 -k . Theorem 3
The average height of the first sojourn of a Dyck path of length 2N is given by

1 b N k≥1 d(k) 2N -1 N -k -2 2N -1 N -1 -k + 2N -1 N -2 -k .
A similar computation as before evaluates this asymptotically:

Theorem 4 The average height of the first sojourn of a Dyck path of length 2N is asymptotic to

1 2 √ πN + 1 4 log N + 3 4 (γ -1).
It is interesting to note that in the average height of the Dyck path, no such logarithmic term occurs.

The location of the first maximum

For reasons of comparison, it is also interesting to study the location of the first maximum of the whole path (not only the first sojourn). The computations are somewhat similar.

F (z, u) = h≥1 C h-1 (zu)zuC h (z) = 1 -4z 2 1 -4z 2 u 2 h≥1 z 2h u h (λ h+1 1 (zu) -λ h+1 2 (zu))(λ h+2 1 (zu) -λ h+2 2 (zu))
.

We compute again the average, by differentiating this function:

G(z) = -4z 2 h≥1 z 2h (λ h+1 1 (z) -λ h+1 2 (z))(λ h+2 1 (z) -λ h+2 2 (z)) + (1 -4z 2 ) h≥1 hz 2h (λ h+1 1 (z) -λ h+1 2 (z))(λ h+2 1 (z) -λ h+2 2 (z)) + 2z 2 1 -4z 2 h≥1 (h + 1)z 2h (λ h 1 (z) + λ h 2 (z)) (λ h+1 1 (z) -λ h+1 2 (z)) 2 (λ h+2 1 (z) -λ h+2 2 (z)) = -4(1 + v 2 ) h≥2 v 2h (1 -v 2h )(1 -v 2h+2 ) + (1 -v 2 ) 2 (1 + v 2 ) h≥1 hv 2h (1 -v 2h+2 )(1 -v 2h+4 ) + 2(1 -v 4 ) h≥2 hv 2h (1 + v 2h-2 ) (1 -v 2h ) 2 (1 -v 2h+2 ) = - (1 + v 2 ) 3 (1 -v 2 ) 2 - (1 + v 2 ) 3 v 2 (1 -v 2 ) h≥1 v 2h 1 -v 2h + 2(1 + v 2 ) 2 v 2 h≥1 hv 2h (1 -v 2h ) 2 .
And we read off coefficients again:

[z n ]G(z) = [v n ](1 -v 2 )(1 + v 2 ) n-1 G(z(v)) = -[v N ] (1 + v) 2N +2 1 -v -[v N +1 ](1 + v) 2N +2 h≥1 v h 1 -v h + 2[v N +1 ](1 -v)(1 + v) 2N +1 h≥1 hv h (1 -v h ) 2 = - N k=0 2N + 2 k -[v N +1 ](1 + v) 2N +2 k≥1 d(k)v k + 2[v N +1 ](1 -v)(1 + v) 2N +1 k≥1 kd(k)v k = -2 2N +1 + 2N + 1 N - k≥1 d(k) 2N + 2 N + 1 -k + 2 k≥1 kd(k) 2N + 1 N + 1 -k - 2N + 1 N -k . Theorem 5
The average location of the first maximum, assuming that all b N = 1 N +1

2N

N Dyck paths of length 2N are equally likely, is given by

1 b N -2 2N +1 + 2N + 1 N - k≥1 d(k) 2N + 2 N + 1 -k + 2 k≥1 kd(k) 2N + 1 N + 1 -k - 2N + 1 N -k .
The asymptotic evaluation is exactly as before, with the result:

Theorem 6
The average location of the first maximum, assuming that all b N = 1 N +1

2N

N Dyck paths of length 2N are equally likely, is asymptotic to

N - 1 3 √ πN + 1 2 .

The general case

We don't have to stop here. Indeed, we can consider the height (location and value) within the r-th sojourn. The expected number of sojourns (=degree of the root of the associated planar tree) is just 2. Kemp has analyzed the height of trees with root degree exactly r, see [START_REF] Kemp | The average height of r-tuply rooted planted plane trees[END_REF][START_REF] Prodinger | A note on a result of R. Kemp on r-tuply rooted planted plane trees[END_REF]. We consider Dyck paths of length n which have ≥ r sojourns, where r is a parameter. The generating function of them is (zC(z)z) r C(z) = z 2r C r+1 (z). A standard application of the Lagrange inversion formula enumerates the paths:

r + 1 N + 1 2N -r N .
Asymptotically, a proportion of r+1 2 r of all paths has ≥ r sojourns. Now, for the position of the first maximum within the r-th sojourn, we have to consider F r (z, u) = z 2(r-1) u 2(r-1) C r-1 (zu)F (z, u).

For the average, we compute

G r (z) = 2(r -1)z 2(r-1) C r-1 (z)F (z, 1) + z 2(r-1) (r -1)C r-2 (z)zC ′ (z)F (z, 1) + z 2(r-1) C r-1 (z)G(z) = (r -1) 2 + zC ′ (z) C(z) z 2r C r+1 (z) + z 2(r-1) C r-1 (z)G(z) = 2(r -1)v 2r (1 -v 2 )(1 + v 2 ) r+1 + v 2(r-1) (1 + v 2 ) r-1 - 4v 4 (1 -v 2 ) 2 - (1 + v 2 ) 2 1 -v 2 h≥1 v 2h 1 -v 2h + 2(1 + v 2 ) h≥1 hv 2h (1 -v 2h ) 2 = 2(r -1)v 2r (1 -v 2 )(1 + v 2 ) r+1 - 4v 2(r+1) (1 -v 2 ) 2 (1 + v 2 ) r-1 - v 2(r-1) (1 -v 2 )(1 + v 2 ) r-3 h≥1 v 2h 1 -v 2h + 2v 2(r-1) (1 + v 2 ) r-2 h≥1 hv 2h (1 -v 2h ) 2 .
And thus

[z 2N ]G(z) = 2(r -1) 2N -r -2 N -r -4 N -r-1 k=1 2N -r k - k≥1 d(k) 2N -r + 2 N -r + 1 -k + 2 k≥1 k d(k) 2N -r + 1 N -r + 1 -k - 2N -r + 1 N -r -k . Note that N -r-1 k=1 2N -r k = 1 2 2 2N -r - N k=N -r 2N -r k .
And we have

-2N -r+2 N -r+1-k + 2k 2N -r+1 N -r+1-k -2k 2N -r+1 N -r-k 2N -r N ∼ e -x 2 4(-1 + 2x 2 ) + 8r(x -x 3 ) √ N + 2 -6(r 2 -r + 3)x 2 + (4r 2 -4r + 38 3 )x 4 -4 3 x 6 N .
Eventually, the same procedure as before produces the asymptotic formula for the position of the first maximum within the r-th sojourn: .

And finally we will consider the height of the r-th sojourn. We must multiply the old B h (z) function by (z 2 C(z)) r-1 , or by v 2(r-1) (1+v 2 ) 2(r-1) . The generating function of paths where the maximum in the r-th sojourn is > h, is given by

v 2r (1 -v 2 ) (1 + v 2 ) r-1 v 2h 1 -v 2h+2 .
And for the expectation, we must consider

v 2(r-1) (1 -v 2 ) (1 + v 2 ) r-1 h≥1 v 2h 1 -v 2h .
Apart from normalization, we look at

k≥1 d(k) 2N -r N + 1 -r -k -2 2N -1 N -r -k + 2N -1 N -1 -r -k .
We approximate again:

2N -r N +1-r-k -2 2N -1 N -r-k + 2N -1 N -1-r-k 2N -r N ∼ 1 N e -k 2 /N -2 + 4 k 2 N + further terms .
Eventually, the average evaluates asymptotically to √ πN r + 1 + r 2(r + 1) log N -2r + 1 2(r + 1) + 3rγ 2(r + 1) .

Conclusion

We leave limiting distributions, higher moments and asymmetric random walks to further research.

† This material is based upon work supported by the National Research Foundation under grant number 2053748 1365-8050 c 2008


J A Grytczuk

H A Kierstead

P Prałat

On-line Ramsey Numbers for Paths and Stars

Keywords:

We study on-line version of size-Ramsey numbers of graphs defined via a game played between Builder and Painter: in one round Builder joins two vertices by an edge and Painter paints it red or blue. The goal of Builder is to force Painter to create a monochromatic copy of a fixed graph H in as few rounds as possible. The minimum number of rounds (assuming both players play perfectly) is the on-line Ramsey number e r(H) of the graph H. We determine exact values of e r(H) for a few short paths and obtain a general upper bound e r(Pn) ≤ 4n -7. We also study asymmetric version of this parameter when one of the target graphs is a star Sn with n edges. We prove that e r(Sn,H) ≤ n • e(H) when H is any tree, cycle or clique.

Introduction

In this paper we are concerned with on-line variant of size-Ramsey numbers of graphs. For given graphs G and H we write G → H if there is a monochromatic copy of H in any red-blue coloring of the edges of G. The size-Ramsey number of a graph H, denoted by r(H), is the smallest possible number of edges in a graph G satisfying G → H. This notion was first studied by Erdős, Faudree, Rousseau, and Schelp [START_REF] Erdős | The size Ramsey number[END_REF], as a variation on the usual Ramsey number r(H) (which is the least n such that K n → H, where K n is a clique on n vertices). Clearly, r(H) is at most r(H) 2 for every graph H. Somewhat surprisingly this bound is attained if H = K n [START_REF] Erdős | The size Ramsey number[END_REF]. However, r(P n ) ≤ cn for some absolute constant c, where P n is a path on n vertices. This was proved by Beck (2) in response to a one-hundred-dollar question of Erdős. The proof uses random graphs and is nonconstructive (cf. [START_REF] Bollobás | Random graphs[END_REF]). Explicit construction based on expanders was provided by Alon and Chung [START_REF] Alon | Explicit construction of linear sized tolerant networks[END_REF]. Since then many deep results for other natural classes of graphs were obtained (cf. (3; 7; 15; 22)).

On-line version of size-Ramsey numbers was introduced independently by Beck (4) and Kurek and Ruciński [START_REF] Kurek | Two variants of the size Ramsey number[END_REF]. It is best explained by the following game between Builder and Painter, played on a large set of vertices. In one round Builder joins two nonadjacent vertices by an edge and Painter colors this edge red or blue. The goal of Builder is to create a monochromatic copy of a fixed graph H in as few rounds as possible. Painter will try to resist doing it for as long as possible. The on-line Ramsey number 1365-8050 c 2008 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France r(H) of a graph H is the minimum number of rounds in which Builder achieves his goal, assuming both players play perfectly. Clearly, r(H) ≤ r(H) and it is natural to ask how much these two parameters may differ. We study this question in several typical situations. For instance we show that r(P n ) ≤ 4n -7, while currently best bound in the off-line case is r(P n ) ≤ 594n (cf. ( 5)). In general the problem may be hard as it is not even known if the ratio r(K n )/ r(K n ) tends to zero as n →∞(cf. [START_REF] Kurek | Two variants of the size Ramsey number[END_REF]). Other open problems and related versions of the game can be found in (10; 12; 13).

One can also consider an asymmetric version of the on-line Ramsey number. We write F → (G, H) if in any red-blue coloring of the edges of F there is a red copy of G or a blue copy of H. Similarly, r(G, H) stands for the minimum number of edges in a graph F such that F → (G, H), and r(G, H) is defined accordingly.

Similar to the classical Ramsey numbers (see a dynamic survey of Radziszowski (21) which includes all known nontrivial values and bounds for Ramsey numbers), it is hard to compute the exact value of r(G) unless G are trivial. In this relatively new area of small on-line Ramsey numbers, very little is known.

Paths

As a warm-up we start with exact determination of the on-line Ramsey numbers for a few short paths. Let e(H) denote the number of edges of a graph H. Note first that in general we have r(H) ≥ 2e(H) -1, since Painter may color safely the first e(H) -1 edges red, and the next e(H) -1 edges blue. Since e(P n )=n -1 we have r(P n ) ≥ 2n -3. This lower bound is attained for n =2, 3, 4, 5.

Proposition 2.1 r(P

n )=2n -3, for n =2, 3, 4, 5.
The cases n =2, 3 are trivial. The case n =4is also very easy; after presenting three edges of a path P 4 , there are only two possible patterns (up to symmetry): bbr and brb. Then Builder creates a monochromatic path P 4 in the next two moves, as depicted in Figure 1. (The final edge is drawn in two colors.) To prove that r(P 5 )=7we have to analyze more subcases. In the first four moves Builder constructs a path P 5 so that essentially one of the three possible color patterns appears, as displayed in Figure 2. Then he obtains a monochromatic P 5 in next three moves, as shown in Figure 3. (A circled number means that Painter had a choice in that move, which led to a branching into subcases.) The pattern breaks already for n =6.

❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ✈✈✈✈ ✈ 123 4 5 (a) Case 1 ✧ ✦ ★ ✥ ✤ ✜ ✈✈✈✈ 123
❍ ❍ ❍ ❍ ❍ ❍ ❍ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ❅ ❅ ❅ ❅ ✈✈✈ ✈✈ ✈ 5 ❤ 6 7 (b) Case 2 -rbbr ✟ ✟ ✟ ✟ ✟ ✟ ✟ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ✈✈✈ ✈✈ ✈ 5 ❤ 6 7 (c) Case 2' -rbbr ¡ ¡ ¡ ¡ ¡ ¡ ¡ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ❍ ❍ ❍ ❍ ❍ ❍ ❍ ❅ ❅ ❅ ❅ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✈✈ ✈✈ ✈ 5 ❤ 6 7 (d) Case 3 -brbr ❍ ❍ ❍ ❍ ❍ ❍ ❍ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ❅ ❅ ❅ ❅ ✈✈ ✈✈✈ ✈ 5 ❤ 6 7
(e) Case 3' -brbr Fig. 3: Forcing a path P5 (last three moves)

Proof: For the lower bound consider a natural strategy for Painter: color an edge blue if it does not create a blue copy of P 6 , otherwise use red. Suppose first that the graph constructed by Builder in the first four moves is not a path P 5 . Then clearly Painter will be able to use the color blue in the very next move and we are done. So, suppose that after first four rounds there is a blue path P 5 . The only way for Builder to finish the game in the total of nine rounds is to create in next four rounds a red P 5 . This is possible only by using both ends of the blue path P 5 , making the last winning move impossible. The upper bound is achieved by case-by-case analysis shown in Figure 4 (first five moves) and

(

(1)

Fig. 4: Forcing a monochromatic P6 (first five moves)

Further computer assisted results for small paths can be found in (18; 19). (It has been shown that r(P 7 )=1 2 , r(P 8 )=1 5 , and r(P 9 )=1 7 . The values for an asymmetric version of the on-line Ramsey number for paths of lengths at most 8 are also determined.) In general we have the following upper bound.

Theorem 2.3 Let k ≥ 1.I n 2k -1 rounds Builder can force Painter to create two vertex disjoint monochromatic paths (the red one and the blue one) the sum of whose lengths is equal to k.

In particular, r(P n ) ≤ 4n -7 for all n ≥ 2. Proof: The proof goes by induction on k. The basis step k =1is trivial. For the inductive step assume that the statement holds for some k ≥ 1, that is after 2k -1 rounds there is a red path R and a blue path B such that In order to finish the proof notice that after 4n-7=2(2n-3)-1 rounds there must be a monochromatic path with at least n -1 edges, that is, a monochromatic P n . ✷

❅ ❅ ❅ ✟ ✟ ✟ ✟ ✟ ✟ ❅ ❅ ❅ ❆ ❆ ❆ ❆ ❆ ❆ ✉✉ ✉✉ ✉✉ ✉✉ ✉ 6 7 8 9 10 (a) Case 1 -bbbbr ❅ ❅ ❅ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ❆ ❆ ❆ ❆ ❆ ❆ ❅ ❅ ❅ ❅ ❅ ❅ ✉✉ ✉✉ ✉✉ ✉✉ 6 7 8 9 10 ❢ (b) Case 2a -bbbrb ❅ ❅ ❅ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ❆ ❆ ❆ ❆ ❆ ❆ ❍ ❍ ❍ ❍ ❍ ❍ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ✉✉ ✉✉ ✉✉ ✉ 6 7 8 9 10 ❢ (c) Case 2b -bbbrb ❅ ❅ ❅ ❍ ❍ ❍ ❍ ❍ ❍ ❅ ❅ ❅ ❅ ❅ ❅ ✉✉ ✉✉ ✉✉ ✉✉ 6 7 8 9 ❢ (d) Case 3a -bbbrr ❅ ❅ ❅ ❅ ❅ ❅ ✉✉ ✉✉ ✉✉ ✉✉ ✉ 6 7 8 9 ❢ ❢ (e) Case 3b -bbbrr ❅ ❅ ❅ ❍ ❍ ❍ ❍ ❍ ❍ ✉✉ ✉✉ ✉✉ ✉✉ 6 7 8 9 ❢ ❢ (f) Case 3c -bbbrr ❅ ❅ ❅ ✉✉ ✉✉ ✉✉ ✉✉ 6 78 9 10 ❣ (g) Case 4a -bbrbr ❅ ❅ ❅ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ✟ ✟ ✟ ✟ ✟ ✟ ✉✉ ✉✉ ✉✉ ✉ 6 7 8 9 10 ❣ ❣ (h) Case 4b -bbrbr ✏ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ❅ ❅ ❅ ✟ ✟ ✟ ✟ ✟ ✟ ✉✉ ✉✉ ✉✉ ✉✉ 6 7 8 9 10 ❣ ❣ (i) Case 4c -bbrbr ❅ ❅ ❅ ❅ ❅ ❅ ❍ ❍ ❍ ❍ ❍ ❍ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ¡ ¡ ¡ ¡ ¡ ¡ ❅ ❅ ❅ ❅ ❅ ❅ ✉✉ ✉✉ ✉✉ ✉ 6 7 8 9 10 ❣ (j) Case 5a -brbbr ¡ ¡ ¡ ¡ ¡ ¡ ❆ ❆ ❆ ❆ ❆ ❆✟ ✟ ✟ ✟ ✟ ✟ ❅ ❅ ❅ ❇ ❇ ❇ ❇ ❇ ❇ ❇ ❇ ❇ ✟ ✟ ✟ ✟ ✟ ✟ ✉✉ ✉✉ ✉✉ ✉✉ 6 7 8 9 10 ❣ ❣ ❣ (k) Case 5b -brbbr ¡ ¡ ¡ ¡ ¡ ¡ ❅ ❅ ❅ ❇ ❇ ❇ ❇ ❇ ❇ ❇ ❇ ❇ ❆ ❆ ❆ ❆ ❆ ❆ ✉✉ ✉✉ ✉✉ ✉✉ 6 7 8 9 10 ❣ ❣ ❣ (l) Case 5c -brbbr ¡ ¡ ¡ ¡ ¡ ¡ ❇ ❇ ❇ ❇ ❇ ❇ ❇ ❇ ❇ ✟ ✟ ✟ ✟ ✟ ✟ ❅ ❅ ❅ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✉✉ ✉✉ ✉✉ ✉✉ 6 7 8 9 10 ❣ ❣ (m) Case 5d -brbbr ❆ ❆ ❆ ❆ ❆ ❆ ✟ ✟ ✟ ✟ ✟ ✟ ❅ ❅ ❅ ✟ ✟ ✟ ✟ ✟ ✟ ✉✉ ✉✉ ✉✉ ✉✉ 6 7 8 9 ❢ (n) Case 6a -brrbb ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ✉✉ ✉✉ ✉✉ ✉✉ 6 7 8 9 10 ❣ ❣ (o) Case 6b -brrbb ❍ ❍ ❍ ❍ ❍ ❍ ❅ ❅ ❅ ❍ ❍ ❍ ❍ ❍ ❍ ✉✉ ✉✉ ✉✉ ✉ 6 7 8 9 ❣ ❣ (p) Case 6c -brrbb
V (R) ∩ V (B)=∅ and |E(R) ∪ E(B)| = k. Let v R

Trees

Let f (n) be the maximum value of r(T ) taken over all trees with n edges. In (9) Erdős and Graham proved that r(T ) ≤ 4e(T )+1for every tree T . From this it follows that f (n)=O(n 2 ). We show that this bound cannot be improved asymptotically, that is, f (n)=Θ ( n 2 ). First we derive a general lower bound for r(H) for arbitrary graphs and then present an example that proves the statement. Let τ (H) denote the smallest number of vertices covering all edges of H. The size-Ramsey number of H can be bounded from below in terms of τ (H) and the maximum degree ∆(H) of a graph H. A similar bound holds in the on-line case.

Proposition 3.1 r(H) ≥ 1 2 τ (H)(∆(H) -1
) + e(H) for every graph H.

Proof: Painter's strategy is to color an edge red as long as the red subgraph has maximum degree strictly less than ∆(H); otherwise she colors an edge blue. So, a red copy of H will never appear. Suppose a blue copy of H has appeared in a graph constructed by Builder. Then at least one end vertex of each blue edge must be incident with exactly ∆(H) -1 red edges. Hence the red subgraph must have at least τ (H) vertices of degree ∆(H) -1 and thus the number of red edges is at least 1 2 τ (H)(∆(H) -1). ✷

Now, we are ready to show that f (n)=Ω ( n 2 ). Let B n be a graph with n edges, obtained from a star S ⌊n/2⌋ = K 1,⌊n/2⌋ by subdividing each edge, and with an additional edge attached to the center of the star if n is odd. ✷

Corollary 3.2 f (n) ≥ r(B n ) ≥ n 2 8 + 3n 4 , for every n ≥ 1. Proof: We have ∆(B n )=τ (B n )=⌈n/2⌉
If we restrict to trees of bounded degree then even the size-Ramsey numbers are linearly bounded (cf. ( 11)).

Stars versus trees, cycles, and cliques

In this section we focus on asymmetric version of the on-line Ramsey number where one of the graphs is a star S n .

It is clear that the Proposition 3.1 can be easily generalized to the asymmetric version we consider. Since the proof is almost identical, we omit it here. In particular, r(S n ,H) ≥ 1 2 τ (H)(n -1) + e(H). Before we state a general upper bound we need a few more definitions. Let π be a permutation of the vertices of G. For a vertex v ∈ V (G), let N + π (v) be the number of neighbors of v that follow it in the permutation. Similarly, we define N - π (v). Let d π (G) be the maximum "back degree", that is,

d π (G)=max{N - π (v):v ∈ V (G)},
and l π (G) be the number of vertices with no "forward neighbors", that is,

l π (G)= v∈V (G) δ(N + π (v)=0)
where δ(A) is the Kronecker delta function

δ(A)= 1, if A is true 0, otherwise.
Finally, let n(G) denote the number of vertices in a graph G. The proof follows immediately from Proposition 4.2 since there is a permutation π with d π (G)=1 and l π (G)=l. We present an alternative proof below.

Proof: Let r ∈ V (T ) be any vertex of degree at least 2, and select this vertex as a root of the tree T making this tree a rooted one. Let d(v) denote the degree of a vertex v in the tree T . In the first d(r)+n-1 moves Builder draws a star S d(r)+n-1 forcing Painter to create a blue star S d(r) . This is the first level of T . Then for every leaf v of the blue star S d(r) , which is not a leaf of T , Builder draws a star S (d(v)-1)+(n-1) with center in v. This creates the second level of T (see Figure 6). And so on, until a complete blue copy of T (or a red copy of S n ) appears. The total number of edges drawn by Builder is In next proposition we show that the on-line Ramsey number for a star S n versus a fixed cycle grows linearly in n. This is different than in the off-line case, where for odd cycles we have a quadratic growth (cf. (16; 17)).

(n -1)(|V (T )|-l)+e(T )=e(T )n -(l -1)(n -1) as asserted. ✷ ✟ ✟ ✟ ✟ ✟ ✟ ❅ ❅ ❅ ❍ ❍ ❍ ❍ ❍ ❍ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ❅ ❅ ❅ ❅ ❅ ❅ ✟ ✟ ✟ ✟ ✟ ✟ ❅ ❅ ❅ ✉ ✉✉✉✉ ✉✉✉✉✉✉✉✉ ✉✉✉✉✉✉✉ ✉✉✉

Proposition 4.4 For every

n, k ∈ N, k ≥ 3 k 4 (n +3)≤ r(S n ,C k ) ≤ nk.
Proof: The lower bound follows immediately from Proposition 4.

1 since τ (C k ) ≥ k/2.
For the upper bound, Builder first forces a blue path with k -2 edges. By Proposition 4.3 this takes at most n(k -3) + 1 rounds. Let v 1 and v k-1 be the two end vertices of this path. Builder draws a star S 2n-1 with center in v k-1 and new vertices u 1 ,...,u 2n-1 as its leaves. Clearly at least n edges of this star must be blue. Then he joins these vertices to the vertex v 1 . If there is no red star yet, then there must be a vertex u i such that both edges u i v 1 and u i v k-1 are blue. Hence a blue cycle is created (see Figure 7). Total number of edges is equal to It is clear that better bounds can be achieved with more effort. For example let us mention the following small improvement. If Painter creates red S n-1 in the first phase, then Builder can start growing a path from the other direction so that vertex v 1 is attached to the red star. Now in the second phase we can generate one blue edge only (instead of n as before). This saves at least min{n -1,k-3} edges. Since there is no hope for a general exact formula, we are happy with the bound which is optimal up to a multiplicative constant.

((k -3)n +1)+(2n -1) + n = kn. ✷ ❅ ❅ ❅ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ❇ ❇ ✂ ✂ ❇ ❇ ✂ ✂ v 1 v 2 v 3 v 4 v 5 v k-3 v k-2 v k-1 t t t t tt t t (a) First phase ❅ ❅ ❅ ❅ ❅ ❅ ❍ ❍ ❍ ❍ ❍ ❍ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ❇ ❇ ✂ ✂ ❇ ❇ ✂ ✂ ✟ ✟ ✟ ✟ ✟ ✟ v 1 v 2 v 3 v 4 v 5 v k-3 v k-2 v k-1 t t t t tt t t ttttt (b) Second phase ❅ ❅ ❅ ❅ ❅ ❅ ❍ ❍ ❍ ❍ ❍ ❍ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ❇ ❇ ✂ ✂ ❇ ❇ ✂ ✂ ✟ ✟ ✟ ✟ ✟ ✟ ❅ ❅ ❅ ❍ ❍ ❍ ❍ ❍ ❍ v 1 v 2 v 3 v 4 v 5 v k-3 v k-2 v k-1 t t
A similar bounds hold for cliques K k . The bound is optimal up to a factor of ck for some constant c>0.

Proposition 4.5 For every

n, k ∈ N, k ≥ 2 1 2 (k -1)(n -1) + k 2 ≤ r(S n ,K k ) ≤ k 2 n.
Proof: Again, the lower bound is a simple consequence of Proposition 4.1 since τ (K k )=k -1.

For the upper bound, let V 0 be a set of |V 0 | =( k -1)n +1vertices. First Builder proposes (k -1)n edges of a star S (k-1)n on the set V 0 . Since Painter is trying to avoid a red star with n edges, at least

(k -2)n +1edges must be colored blue. Let V 1 ⊂ V 0 , |V 1 | =(k -2)
n +1be a set of vertices of degree 1 connected with a blue edge. In the second phase Builder is drawing a star S (k-2)n on V 1 forcing Painter to use blue color at least (k -3)n +1times. Thus, there is a set

V 2 ⊂ V 1 , |V 2 | =(k -3
)n +1of vertices of degree 2 incident with a blue edges only. Repeating this strategy in each phase, Builder eventually forces Painter to draw either a red star S n or a blue clique K k . An example of the game in case of K 1,2 and K 4 is shown on Figure 8. Note that the game consists of k -1 phases and during the ith round, the Builder is drawing a star with (ki)n edges. Thus

r(S n ,K k ) ≤ k-1 i=1 (k -i)n = k(k -1) 2 n
and the assertion follows. ✷ The above results suggest that perhaps r(S n ,H) ≤ n • e(H) for every graph H.

✘ ✘ ✘ ✘ ✘ ✘ ❳ ❳ ❳ ❳ ❳ ❳ ❅ ❅ ❅ ❅ ❅ ❈ ❈ ❈ ❈ ❈ ❈ ✄ ✄ ✄ ✄ ✄ ✄ r r r rr r r (a) First phase ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✏ ✏ ✏ ✏ ✏ ❳ ❳ ❳ ❳ ❳ ❳ ❅ ❅ ❅ ❅ ❅ ❈ ❈ ❈ ❈ ❈ ❈ ✄ ✄ ✄ ✄ ✄ ✄ ¡ ¡ ¡ ✧ ✧ ✧ ✧ ✧ ✧ ✧ ✧ r r r rr r r (b) Second phase ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✏ ✏ ✏ ✏ ✏ ✘ ✘ ✘ ✘ ✘ ✘ ✟ ✟ ✟ ❳ ❳ ❳ ❳ ❳ ❳ ❅ ❅ ❅ ❅ ❅ ❈ ❈ ❈ ❈ ❈ ❈ ✄ ✄ ✄ ✄ ✄ ✄ ¡ ¡ ¡ ✧ ✧ ✧ ✧ ✧ ✧ ✧ ✧ ✟ ✟ ✟

Discussion

We conclude the paper with some questions for future consideration. Let F be a fixed family of graphs and let r(n)=m a x { r(H):H ∈F, |V (H)| = n}. Also let r(n) and r(n) be defined analogously for size-Ramsey and Ramsey numbers of graphs from F , respectively. Clearly for any class F we have

r(n) ≤ r(n) ≤ r(n) 2 .
A general problem is to determine the asymptotic growth of the function r(n) for some basic graph classes. In particular, to decide whether

lim n→∞ r(n) r(n) = ∞. (1)
It is natural to expect that (1) should hold for most reasonable families of graphs. Clearly (1) cannot hold if r(n) is linear, but, as we demonstrated, it also does not hold for trees, where r(n) grows quadratically. We do not know what happens for graphs of bounded degree. A well known theorem of Chvátal, Rödl, Szemerédi, and Trotter (6) asserts that r(n) grows linearly for every fixed ∆ (hence r(n) is at most quadratic). On the other hand, as proved by Rödl and Szemerédi [START_REF] Rödl | On size Ramsey numbers of graphs with bounded maximum degree[END_REF], there are cubic graphs with quadratic size-Ramsey number.

It is obvious that the real challenge is in computing the on-line Ramsey numbers for cliques. Therefore, the following intriguing question was posed by Kurek and Ruciński (14): does (1) hold for the family of all cliques? A natural strategy for Builder is to mimic a recursive construction giving the upper bound for classical Ramsey number r(K n ). This gives for instance r(K 3 ) ≤ 8 (in fact, r(K 3 )=8 ; the proof of the lower bound is elementary but nontrivial). Moreover, it has been shown that r(K k ) ≤ 2k 2k-2 k-1 ∼

1 2 √ π √ k4 k .
The third author of this note, with computer support, showed that an asymmetric version of the on-line Ramsey number r(K 3 ,K 4 ) is equal to 17, provided a general upper bound for r(K k ,K l ), which gives a slightly better asymptotic upper bound of 3 8 √ π 4 k √ k for a symmetric version of the on-line Ramsey numbers (see [START_REF] Prałat | R(3, 4) = 17[END_REF] for more details).

4 5(b) Case 2 Fig. 1 :

 421 Fig. 1: Forcing a path P4

Fig. 2 :

 2 Fig. 2: Forcing a monochromatic P5 (first four moves)

Fig. 5 :

 5 Fig. 5: Forcing a path P6 (last five moves)

  and v B denote any end vertices of R and B, respectively (take any isolated vertex as v R or v B if the corresponding path has no edge). If there is no edge v R v B , then Builder draws the edge v R v B and Painter does her job (note that it is only to Builder's advantage if it already exists).Suppose Painter colors this edge red. Then Builder draws an edge from vertex v B to a new vertex v. If Painter uses red color, then there are two vertex disjoint monochromatic pathsR ′ = R + v B + v and B ′ = Bv B ,with k +1edges in total. If Painter colors v B v blue, the paths R ′ = R and B ′ = B + v satisfy the assertion. If initially Painter colors the edge v B v R blue, then Builder draws an edge from v R to a new vertex v instead, and the situation is symmetric.

Proposition 4 .

 4 1 r(G, H) ≥ 1 2 max{τ (H)(∆(G) -1) + e(H),τ(G)(∆(H) -1) + e(G)} for arbitrary graphs G and H.

Proposition 4 . 3

 43 Let T be any tree with e(T ) ≥ 2 edges and l vertices of degree 1 (leaves). Then for every n ∈ N r(S n ,T) ≤ e(T )n -(l -1)(n -1) .

Fig. 6 :

 6 Fig. 6: Forcing a red K1,n or blue T

Fig. 7 :

 7 Fig. 7: Forcing a red K1,n or blue C k

Fig. 8 :

 8 Fig. 8: Forcing a red K1,n or blue K k

  as each cover must contain a non-center vertex from each subdivided edge and one extra vertex for an additional edge if n is odd. ✷ If Builder knows that Painter will follow the strategy from Proposition 3.1, then he can force B n in From now on, Painter will color any vertex incident to a clique vertex blue. So Builder can force a blue B n in n moves by using the clique vertices as subdivision vertices of B n . Painter can delay her agony a little by coloring edges that are incident to the clique and do not create forbidden graph with red, but her real problem was allowing the red clique. On the other hand, at most n 2 4 + O(n) moves are enough to force Painter to create monochromatic B n . Builder starts by playing 6k -5 independent edges. Painter is forced to create a monochromatic matching M = {x i y i : i ∈ [3k -2]}; suppose the edges of M are blue. Add a new vertex v and edges vx i for i ∈ [3k -2]. To avoid creating B n , Painter must color 2k -1 of these edges with red. Say she colors x i y i red for i ∈ [2k -1]. In the next k 2 steps, Builder introduces k new vertices z l (l ∈ [k]) and edges z l x m (for some values of m), forcing Painter to either create a blue star with center at some z l (thus finishing a blue B n ), or a red matching M ′ = {z l x m l : l ∈ [k]} (thus finishing a red B n ). To do this, he simply plays k edges between z l and k vertices of the form x m , where x m is not incident with an edge in M

	Proposition 3.3 r(B n ) ≤ n 2 4 + 9 2 n -7 for every even n =2k ≥ 4.
	⌈n/2⌉ 2	+ n = n 2

[START_REF] Erdős | The size Ramsey number[END_REF]

+ O(n) moves. He starts by building a ⌈n/2⌉-clique, which Painter colors entirely red.

Proof: ′ .

This takes (6k -5) + (3k -2) + k 2 edges. Builder can save some edges by being more careful at the beginning.

  Fix a permutation π of vertices of H. We present Builder's strategy to construct H in an order yielded by permutation π. When we consider a new vertex v of H, we choose a new vertex w in the graph we are constructing and add all edges from w to previously assigned vertices that correspond to the neighbors of v in H. If Painter uses blue color only, we assign w to v and move to the next vertex in H. Otherwise we try again starting from a new vertex w. In total we can have at most (n(H)l π (H))(n -1) retries since that is exactly an upper bound for the number of red edges when Painter is trying to avoid red S n and each retry can be associated with a unique red edge generated in the previous try. In each retry we use at most d π (H) edges.✷Now, we are ready to prove bounds for r(S n ,H) in a few special cases where graph H is any tree, cycle or clique.

Proposition 4.2 r(S n ,H) ≤ min π d π (H)(n(H)l π (H))(n -1) + e(H) for any graph H. Proof:


C Balbuena

P García-Vázquez

X Marcote

J C Valenzuela
email: jcarlos.valenzuela@uca.es

Extremal K (s,t) -free bipartite graphs

Keywords: Zarankiewicz problem, extremal graph theory, forbidden subgraphs

In this paper new exact values of the Zarankiewicz function z(m, n; s, t) are obtained assuming certain requirements on the parameters. Moreover, all the corresponding extremal graphs are characterized. Finally, an extension of this problem to 3-partite graphs is studied.

Introduction

Throughout this paper only undirected simple graphs (without loops or multiple edges) are considered. Unless stated otherwise, we follow the book by Bollobás [START_REF] Bollobás | Extremal Graph Theory[END_REF] for undefined terminology and definitions.

Let G = G(m, n) = G(X, Y ) denote a bipartite graph with vertex classes X and Y such that |X| = m and |Y | = n. A complete bipartite subgraph with s vertices in the class X and t vertices in the class Y is denoted by K (s,t) . A bipartite graph G = G(X, Y ) contains K (s,t) as a subgraph if there exists an s-set S in X and a t-set T in Y such that the induced subgraph by S ∪ T in G, denoted G [S ∪ T ], is a complete bipartite K (s,t) . Notice that a bipartite graph G may contain K (s,t) as a subgraph but it may be actually free of K (t,s) .

A question that arises naturally is: what is the maximum number of edges, denoted by z(m, n; s, t), that a K (s,t) -free bipartite graph G = G(m, n) can have? Zarankiewicz [START_REF] Zarankiewicz | Problem P 101[END_REF] posed this problem for the particular case in which m = n and s = t = 3, shortly denoted by z(n; 3), when n = 4, 5, 6. This problem was solved by Sierpinski [START_REF] Sierpinski | Sur un problème concernant un reseau à 36 points[END_REF]. In the following years additional numerical values of the extremal function z(n; 3) for n ≥ 7 were provided by Brzezinski, see [START_REF] Sierpinski | Problems in the Theory of Numbers[END_REF], Culik [START_REF] Culik | Teilweise Lösung eines verallgemeinerten Problems von Zarankiewicz[END_REF], Guy [11,[START_REF] Guy | A problem of Zarankiewicz in: "Theory of Graphs[END_REF][START_REF] Guy | The many faceted problem of Zarankiewicz in: "The Many Facets of Graphs Theory[END_REF] and Guy and Znám [START_REF] Guy | A problem of Zarankiewicz in: "Recent progress in Combinatorics[END_REF]. Finally, the general problem of determining the exact value of the function z(m, n; s, t) as well as the family of extremal graphs has also been known as the Zarankiewicz problem. The extremal family for this problem, denoted by Z(m, n; s, t), is the set of bipartite graphs on m + n vertices with extremal size z(m, n; s, t), such that they do not contain K (s,t) as a subgraph.

The Zarankiewicz problem belongs to a wide class of extremal problems known as Turán type problems. The aim of this kind of problems is to compute the maximum number of edges, denoted by ex (n; F), that a graph G on n vertices can have in such a way that if F ∈ F then F ⊆ G. If the problem involves bipartite graphs on m + n vertices then the extremal function is denoted by ex (m, n; F). Clearly z(m, n; s, t) = ex m, n; {K (s,t) } . Another interesting extremal Turán type problem is the study of ex m, n; {K (s,t) , K (t,s) } , usually denoted by ex (m, n; K s,t ).

Taking into account that K s,t ⊆ G implies both K (s,t) ⊆ G and K (t,s) ⊆ G, it is clear that these extremal problems are related by ex (m, n; K s,t ) ≤ min{z(m, n; s, t), z(m, n; t, s)}.

For a survey of well-known results regarding bounds on the Zarankiewicz problem we refer the reader to Section VI.2 of [START_REF] Bollobás | Extremal Graph Theory[END_REF]. Most of the contributions are bounds for the function z(m, n; s, t) when s, t are fixed and m, n are much larger than s, t (see, for example, [START_REF] Furëdi | New asymptotics for Bipartite Turán Numbers[END_REF][START_REF] Godbole | Contributions to the problem of Zarankiewicz[END_REF][START_REF] Godbole | Threshold functions for the bipartite Turán property[END_REF]).

Our goal in this paper is to present exact values for the extremal function and to characterize the extremal graphs if possible. Concerning exact values for the Zarankiewicz function it is worth pointing out the work of Culik [START_REF] Culik | Teilweise Lösung eines verallgemeinerten Problems von Zarankiewicz[END_REF] who proved that if s, t and m are fixed then

z(m, n; s, t) = (s -1)n + (t -1) m s , for all n > (t -1) m s . (1)
Regarding the particular case in which m = n and s = t = 2 it is well known [START_REF] Bollobás | Extremal Graph Theory[END_REF] that z(n; 2) ≤ (n + n √ 4n -3)/2 and equality holds when n = q 2 + q + 1 for a prime power q. Goddard et al. [START_REF] Goddard | Bipartite Ramsey numbers and Zarankiewicz numbers[END_REF] found the exact values of z(n; 2) for n ≤ 20 and showed that in some cases the family Z(n; 2) is formed by only one extremal graph. Carnielli and Monte Carmelo [START_REF] Cornielli | K 2,2 -K 1,n and K 2,n -K 2,n bipartite Ramsey numbers[END_REF] use z(n; 2) to investigate the bipartite Ramsey number b(n) = b(K 2,2 ; K 1,n ); see also [START_REF] Guy | The many faceted problem of Zarankiewicz in: "The Many Facets of Graphs Theory[END_REF].

There is another equivalent formulation of the Zarankiewicz problem in terms of matrices. Namely, it is easy to check that evaluating the extremal function z(m, n; s, t) for fixed positive integers s ≤ m and t ≤ n, is exactly the same as answering the question of how many ones a {0, 1}-matrix of dimension m × n can have in such a way that it is free of submatrices of dimension s × t whose elements are all ones? Using this matrix terminology Griggs et al. [START_REF] Griggs | On the half-half case of the Zarankiewicz problem[END_REF][START_REF] Griggs | 0,1)-Matrices with no half-half submatrix of ones[END_REF] studied the so-called "half-half" case, that is to say, they evaluated the extremal function z(2s, 2t; s, t) when s ≤ t. In [START_REF] Griggs | 0,1)-Matrices with no half-half submatrix of ones[END_REF] the following inequalities are settled, 4st -(2t + 2sgcd(s, t) + 1) ≤ z(2s, 2t; s, t) ≤ 4st -(2t + s + 1), where gcd(s, t) denotes the greatest common divisor of s and t. Furthermore, it is proved that if t = ks + r, 0 ≤ r < s, such that either r = 0, or r > 0 and s ≤ k + r (which is always true for t > (s -1) 2 ) then

z(2s, 2t; s, t) = 4st -(2t + s + 1). (2)
In a more recent paper Griggs et al. [START_REF] Griggs | On the half-half case of the Zarankiewicz problem[END_REF] studied the still open case t = ks + 1, evaluating z(2s, 2t; s, t) for large enough s and t, and obtaining the exact values of this function whenever t ≤ 20 and s ≤ 7.

Recently, the authors [START_REF] Balbuena | New results on the Zarankiewicz problem[END_REF] solved completely the problem for all the values of the parameters such that max{m, n} ≤ s + t -1 proving the following result:

Let m, n, s, t be positive integers with 2 ≤ s < m, 2 ≤ t < n and such that max{m, n} ≤ s + t -1. Then z(m, n; s, t) = ex(m, n; K s,t ) = mn -(m + nst + 1) and Z(m, n; s, t) = EX (m, n; K s,t ) = {K (m,n) -M }, where M is any matching in K (m,n) with cardinality m + nst + 1.

(3)

In this paper we obtain the exact value of the extremal function z(m, n; s, t) when the parameters m, n, s, t satisfy certain requirements. Moreover, all the corresponding extremal graphs are described. Finally, we compute the exact value of the extremal function for an extension of the Zarankiewicz problem to r-partite graphs. More precisely, we study the function z 3 (n; t), namely, the maximum number of edges of a 3-partite graph with n vertices in each vertex class, free of a complete 3-partite subgraph with t vertices in each vertex class. In this regard we give the exact value for the extremal function z 3 (n; t) when t ≤ n ≤ 2t -1. In Section 2 we present our results and prove them in Section 3.

Main Results

In order to avoid trivial cases we only study the Zarankiewicz problem when s ≥ 2 and t ≥ 2. Notice that z(m, n; s, t) = z(n, m; t, s) for all m, n, s and t.

In the first theorem we compute the exact value of the Zarankiewicz function assuming certain requirements on the parameters.

Theorem 2.1 Let m, n, s, t be integers such that 2 ≤ s ≤ m and 2 ≤ t ≤ n -s. Suppose that (i) (m -s)(⌊(n -t)/s⌋ + 1) ≤ t -1; or (ii) s divides n -t and (m -s)n ≤ mt, being m ≥ 2s if (m -s)n = mt. Then z(m, n; s, t) = mn -(⌊(n -t)/s⌋(m -s) + m + n -s -t + 1) .
Let us point out that when m = 2s, n = 2t and s divides t, Theorem 2.1 gives the same exact value for the extremal function z(2s, 2t; s, t) provided in [START_REF] Bollobás | Extremal Graph Theory[END_REF], see Corollary 2.1. Moreover, Theorem 2.1 permit us to compute z(m, 2t; s, t), for every m ≤ 2s, and to characterize all the corresponding extremal graphs. Therefore, this result improves the "half-half" case [START_REF] Griggs | On the half-half case of the Zarankiewicz problem[END_REF][START_REF] Griggs | 0,1)-Matrices with no half-half submatrix of ones[END_REF] when s divides t. Furthermore, if max{m, n} ≤ s + t -1 then ⌊(nt)/s⌋ = ⌊(ms)/t⌋ = 0 and the value of the extremal function given by Theorem 2.1 matches the one obtained in [START_REF] Cornielli | K 2,2 -K 1,n and K 2,n -K 2,n bipartite Ramsey numbers[END_REF], which in turn means that this theorem extends the results obtained by the authors in [START_REF] Balbuena | New results on the Zarankiewicz problem[END_REF]. However, the results proved in this paper do not overlap those obtained in [START_REF] Balbuena | New results on the Zarankiewicz problem[END_REF] because Theorem 2.1 is written under the hypothesis n ≥ s + t, whereas n ≤ s + t -1 is assumed in (3).

Thus, assuming without loss of generality m ≤ n, we focus our attention in the case ⌊(nt)/s⌋ ≥ 1, hence s + t ≤ n whose solution is not given by (3). Broadly speaking, (3) gives us the exact value of the extremal number z(m, n; s, t) when m and n are very close to s and t respectively. However, with Theorem 2.1 we contribute the solution for this extremal problem when n ≥ s + t.

In order to describe the corresponding extremal graphs we introduce next three families of graphs. Let m, n, s, t be integers such that

m ≤ n, 2 ≤ s ≤ m and 2 ≤ t ≤ n -s. Let H = H 1 ∪ H 2 ⊆ K (m,n) be any subgraph of K (m,n) , with H 1 and H 2 disjoint. (1) F 1 (m, n; s, t) is the family of subgraphs H ⊆ K (m,n) such that: • s divides n -t; • the subgraph H 1 consists of s -1 disjoint copies of K (1,(n-t)/s) ;
• the subgraph H 2 has girth at least 2(s + 1) (may be infinite) and every vertex of the m-class has degree (nt)/s + 1.

(2) F 2 (m, n; s, t) stands for the family of subgraphs H ⊆ K (m,n) such that:

• 3 ≤ s ≤ m and n -t = s⌊(n -t)/s⌋ + r with 0 ≤ r ≤ s -3;
• there exists an integer

k with 2 ≤ ⌈(n -t + s 2 -r(s + 1))/(n -t + s -r)⌉ ≤ k ≤ s -r -1 such that: -the subgraph H 1 consists of the disjoint union of K (1,di) , with 0 ≤ d 1 ≤ • • • ≤ d k-1 ≤ ⌊(n -t)/s⌋ and d 1 + . . . + d k-1 = (k -1) (⌊(n -t)/s⌋ + 1) -s + r + 1;
the subgraph H 2 consists of the disjoint union of m-k+1 copies of the graph K (1,⌊(n-t)/s⌋+1) .

(3) F 3 (m, n; s, t) is the family of subgraphs H ⊆ K (m,n) such that:

• nt = s⌊(nt)/s⌋ + r with 0 < r < s;

• the subgraph H 1 consists of s -r -1 disjoint copies of K (1,⌊(n-t)/s⌋) ; • the subgraph H 2 consists of m -s + r + 1 disjoint copies of K (1,⌊(n-t)/s⌋+1) .
Observe that F 1 (m, n; s, t), F 2 (m, n; s, t) and F 3 (m, n; s, t) are pairwise disjoint families of graphs, and let us point out for every i ∈ {1, 2, 3} that if H ∈ F i (m, n; s, t) then the number of edges of H is

⌊(n -t)/s⌋(m -s) + m + n -s -t + 1. (4)
As an example, Figure 1 depicts three subgraphs of K (m,n) that belong, respectively, to the aforementioned families. In all examples H 1 is the subgraph induced by the white vertices.

The next result describes all the corresponding extremal bipartite graphs to the exact values of Zarankiewicz numbers obtained in the above Theorem 2.1.

Theorem 2.2 Let m, n, s, t be integers such that 2 ≤ s ≤ m and 2 ≤ t ≤ n -s. Suppose that (i) (m -s)(⌊(n -t)/s⌋ + 1) ≤ t -1; or (ii) s divides n -t and (m -s)n ≤ mt, being m ≥ 2s if (m -s)n = mt. Then if r ≡ n -t(mods) with 0 ≤ r < s the following assertions hold: 1. If r = 0 and s = 2 then Z(m, n; s, t) = {K (m,n) -E(H) : H ∈ F 1 (m, n; s, t)}. 2. If r = 0 and s ≥ 3 then Z(m, n; s, t) = {K (m,n) -E(H) : H ∈ F 1 (m, n; s, t) ∪ F 2 (m, n; s, t)}.

H H'' H'

If r > 0 and s

-2 ≤ r ≤ s -1 then Z(m, n; s, t) = {K (m,n) -E(H) : H ∈ F 3 (m, n; s, t)}. 4. If 0 < r ≤ s -3 then Z(m, n; s, t) = {K (m,n) -E(H) : H ∈ F 2 (m, n; s, t) ∪ F 3 (m, n; s, t)}.
Corollary 2.1 Let λ, s, t ≥ 2 be integers and suppose that λt/(λ -1) is an integer. Then if s divides t/(λ -1) we have

z λs, λt λ -1 ; s, t = λ 2 st λ -1 - λt λ -1 + (λ -1)s + 1 .
Moreover the following assertions hold:

1. If s = 2 then Z 2λ, λt λ -1 ; 2, t = K (2λ, λt λ-1 ) -E(H) : H ∈ F 1 2λ, λt λ -1 ; 2, t .
2. If s ≥ 3 then Z (sλ, λt/(λ -1); s, t) is the following set:

K (2λ, λt λ-1 ) -E(H) : H ∈ F 1 sλ, λt λ -1 ; s, t ∪ F 2 sλ, λt λ -1 ; s, t .
Finally, let us denote by K 3 (t) the complete 3-partite graph with t vertices in each vertex class. We study the following problem: what is the maximum number of edges, denoted by z 3 (n; t), of a K 3 (t)-free 3-partite graph G = G(X, Y, Z) with n vertices in each class? In the next result we answer the question for

2 ≤ t ≤ n ≤ 2t -1. Theorem 2.3 Let n, t be integers such that 2 ≤ t ≤ n ≤ 2t -1. Then z 3 (n; t) = 3n 2 -(2(n -t) + 1) .

Proofs

The degree of a vertex w in a graph G is denoted by d G (w) = d(w), N G (w) is the set of adjacent vertices to w in G, and N G (T ) =

w∈T N G (w) \ T denotes the neighborhood of a subset of vertices T . The bipartite complement of a bipartite graph

G = G(X, Y ) with |X| = m and |Y | = n is G c = K (m,n) -E(G)
, where E(G) denotes the edge set of G. We also use e(G) to denote the number of edges of G and G[V ′ ] for the induced subgraph in G by the set of vertices

V ′ ⊆ V (G). Remark 3.1 Let m, n, s, t be integers such that 2 ≤ s ≤ m and 2 ≤ t ≤ n. Let G = G(X, Y ) be a bipartite graph with |X| = m and |Y | = n. Then G is K (s,t) -free if and only if |N G c (S)| ≥ n -(t -1)
for every s-subset S of the X class.

Proof: If S is an s-subset of X such that |N G c (S)| ≤ n -t, then there exists a t-subset T of Y such that N G c (x) ∩ T = ∅ for any x ∈ S. Then G[S ∪ T ] = K (s,t) , hence K (s,t) ⊆ G. Reciprocally, if K (s,t) ⊆ G
then there exist both an s-subset S of X and a t-subset T of Y such that there is no edge joining a vertex in S with a vertex in T in the bipartite complement G c of G. Hence |N G c (S)| ≤ nt, finishing the proof.

✷

The following lemmas are the basis for proving Theorem 2.1 and Theorem 2.2. First, since K (s,t) ⊆ G we have

K (s,t) ⊆ G[S ∪ Y ] and therefore e(G[S ∪ Y ]) ≤ z(s, n; s, t) = (s -1)n + t -1 because of (1). Suppose d G (x s ) ≥ n -⌊(n -t)/s⌋. Then e(G[S ∪ Y ]) ≥ s n - ⌊(n -t)/s⌋ ≥ sn -n + t which is an absurdity. So d G (x s ) ≤ n -⌊(n -t)/s⌋ -1 which implies d G (x i ) ≤ n -⌊(n -t)/s⌋ - 1
for all i ∈ {s + 1, . . . , m}, and hence,

z(m, n; s, t) = e(G) = e(G[S ∪ Y ]) + e(G[(X \ S) ∪ Y ]) ≤ sn -n + t -1 + (m -s)(n -⌊(n -t)/s⌋ -1) = mn -(⌊(n -t)/s⌋(m -s) + m + n -s -t + 1) . (5)
The same reasoning can be repeated for the t-subset T of the Y -class, so we obtain

z(m, n; s, t) ≤ mn -(⌊(m -s)/t⌋(n -t) + m + n -s -t +
G = K (m,n) -E(H 1 ∪ H 2 ) be a bipartite graph with H 1 ∪ H 2 ∈ F i (m, n; s, t). Then G is K (s,t) -free. Proof: Let G = G(X, Y ) = K (m,n) -E (H 1 ∪ H 2 ), with H 1 ∪ H 2 ∈ F i (m, n; s, t), i ∈ {1, 2, 3}.
Let S be any s-subset of X. For each i ∈ {1, 2, 3}, notice that each vertex of X belongs to either V (H 1 ) or V (H 2 ), so S is formed by j vertices of V (H 1 ) and sj vertices of V (H 2 ), where 0 ≤ j ≤ s -1.

First, suppose that the subgraph H 1 ∪ H 2 belongs to the family F 1 (m, n; s, t), then

|V (H 1 ) ∩ X| = s -1 and |V (H 2 ) ∩ X| = m -s + 1.
Let us denote by W ⊆ H 2 the subgraph of the bipartite complement G c induced by the sj vertices in S ∩ V (H 2 ) and their neighbors. As the girth of H 2 is at least 2(s + 1) ≥ 6 we deduce that W is acyclic and

|N G c (u) ∩ N G c (u ′ )| ≤ 1 for every distinct u, u ′ ∈ V (W ). Since the degree in G c of every vertex in V (H 2 ) ∩ X is (n -t)/s + 1 it follows that |V (W ) ∩ Y | ≥ (s -j)(n -t)/s + 1. Then |N G c (S)| ≥ j(n -t)/s + (s -j)(n -t)/s + 1 = n -(t -1) which implies that K (s,t) ⊆ G according to Remark 3.1. Second, suppose that H 1 ∪H 2 ∈ F 2 (m, n; s, t), then |V (H 1 )∩X| = k-1 and |V (H 2 )∩X| = m-k+1 for some 2 ≤ k ≤ s -r -1, hence 0 ≤ j ≤ k -1.
Let us denote by U the subgraph of G c induced by the j vertices in S ∩ V (H 1 ) and their neighbors. Taking into account that

|V (H 1 ) ∩ Y | = d 1 + . . . + d k-1 = (k -1) (⌊(n -t)/s⌋ + 1) -s + r + 1 and d G c (x) ≤ ⌊(n -t)/s⌋ for every vertex x ∈ V (H 1 ), we have |V (U ) ∩ Y | = |V (H 1 ) ∩ Y | -| (V (H 1 ) \ V (U )) ∩ Y | ≥ (k -1) (⌊(n -t)/s⌋ + 1) -s + r + 1 -(k -1 -j)⌊(n -t)/s⌋ = k -s + r + j⌊(n -t)/s⌋,
and hence

|N G c (S)| ≥ k -s + r + j⌊(n -t)/s⌋ + (s -j) (⌊(n -t)/s⌋ + 1) = n -t + k -j ≥ n -t + 1,
which implies that K (s,t) ⊆ G due to Remark 3.1. Finally, suppose that

H 1 ∪ H 2 ∈ F 3 (m, n; s, t), then 0 ≤ j ≤ s -r -1 as |V (H 1 ) ∩ X| = s -r -1 and |V (H 2 ) ∩ X| = m -s + r + 1.
In this case |N G c (S)| ≥ j⌊(nt)/s⌋ + (sj)(⌊(nt)/s⌋ + 1) = ntr + sj ≥ nt + 1. Once more, Remark 3.1 implies that K (s,t) ⊆ G and the proof is complete.

✷ Lemma 3.3 Let m, n, s, t be integers such that 2 ≤ s ≤ m and 2 ≤ t ≤ n -s. Suppose that (i) (m - s)(⌊(n -t)/s⌋ + 1) ≤ t -1; or (ii) s divides n -t and (m -s)n ≤ mt, with m ≥ 2s if (m -s)n = mt. Then z(m, n; s, t) ≥ mn -(⌊(n -t)/s⌋(m -s) + m + n -s -t + 1) . Proof: Observe that m ≤ n follows from the hypothesis. First suppose that (m -s)(⌊(n -t)/s⌋ + 1) ≤ t -1. If s divides n -t then we can consider a graph G = K (m,n) -E(H) with H = H 1 ∪ H 2 ∈ F 1 (
m, n; s, t), the girth of H 2 being infinite. Indeed the subgraphs H 1 and H 2 are well defined since the number of different vertices of

H 1 ∪ H 2 in the n-class is at most (s -1) n -t s + (m -s + 1) n -t s + 1 = (m -s) n -t s + 1 + n -t + 1 ≤ n.
By Lemma 3.2 we know that G is free of K (s,t) . Moreover, from (4) we get e(G) = mn -(⌊(nt)/s⌋(ms) + m + nst + 1) , so z(m, n; s, t) ≥ e(G) and the lemma holds. If s does not divide nt then we consider a graph G = K (m,n) -E(H) with H = H 1 ∪ H 2 ∈ F 3 (m, n; s, t), and reasoning in the same way as before we are done.

From now on we can assume that t ≤ (ms)((nt)/s + 1). Second suppose that s divides nt and (ms)n ≤ mt. As t ≤ (ms)((nt)/s + 1), we are restricting to (m-s)n ≤ mt ≤ (m-s)(n+s). In this case we can consider a graph

G = K (m,n) -E(H) with H = H 1 ∪ H 2 ∈ F 1 (m, n; s, t)
, the subgraph H 2 being taken as follows.

If (ms)n < mt, which is equivalent to m(nt)/s < n, then H 2 consists of a path of length 2(ms + 1) with end vertices in the n-class and such that it has (nt)/s -1 pendant edges attached to each vertex of the m-class. The graph G is well defined since the number of different vertices of

H 1 ∪ H 2 in the n-class is at most (s -1) n -t s + (m -s + 1) n -t s + 1 = m n -t s + 1 ≤ n.
If (ms)n = mt, which is equivalent to m(nt)/s = n, and m ≥ 2s then H 2 consists of a cycle of length 2(ms + 1) which has (nt)/s -1 pendant edges attached to each vertex of the m-class (notice that ms + 1 ≥ s + 1 is necessary because the girth of H 2 is at least 2(s + 1), hence m ≥ 2s must hold). The graph G is well defined because the number of different vertices of

H 1 ∪ H 2 in the n-class is at most (s -1) n -t s + (m -s + 1) n -t s = m n -t s = n.
Observe that e(G) = mn -(⌊(nt)/s⌋(ms) + m + nst + 1) from ( 4), the graph G being free of K (s,t) by Lemma 3.2. Then, we can state that z(m, n; s, t) ≥ e(G), ending the proof. ✷

Reasoning as in the proof of Lemma 3.3, it is not difficult to see that Nevertheless, (ms)n ≤ mt is far from being a necessary condition for F 1 (m, n; s, t) = ∅, as Figure 2 shows. Now we are able to prove our main result regarding the exact values of Zarankiewicz function.

(m -s)(⌊(n -t)/s⌋ + 1) ≤ t -
Proof: of Theorem 2.1. First of all, let us show that

n -t s (m -s) ≥ m -s t (n -t) (6)
Fig. 2: A bipartite graph of F1(8, 9; 2, 5).

follows from the hypothesis.

If (m -s) (⌊(n -t)/s⌋ + 1) ≤ t -1 then it is easy to check that 0 ≤ (m -s)⌊(n -t)/s⌋ ≤ s + t -1 -m which implies m ≤ s + t -1 and hence ⌊(m -s)/t⌋(n -t) = 0. If s divides n -t and (m -s)n < mt, which is equivalent to m(n -t)/s < n, then m < n. Hence m ≤ s + t -1 for if not 0 ≤ (m -s -t)n = (m -s)n -tn ≤ (m -n)t implying that m ≥ n. Therefore we have again that ⌊(m -s)/t⌋(n -t) = 0. Finally, if s divides n -t, m ≥ 2s and (m -s)n = mt,
which is equivalent to m(nt)/s = n, then m ≤ n. If m ≤ s + t -1 then, reasoning as above we are done. If m ≥ s + t then tn ≤ (ms)n = mt and hence s + t = n = m ≥ 2s which implies t ≥ s. In this case we have

n -t s (m -s) = t ≥ s = m -s t (n -t),
and the claimed inequality (6) holds. Now, taking into account (6) we have

z(m, n; s, t) = mn -(⌊(n -t)/s⌋(m -s) + m + n -s -t + 1)
as a direct consequence of Lemmas 3.1 and 3.3. ✷ Proof: of Theorem 2.2. For the characterization of the family of extremal graphs with size z(m, n; s, t), let us consider a graph G = G(X, Y ) ∈ Z(m, n; s, t). Let us assume that the vertices of X are ordered as in the proof of Lemma 3.1, so that

d G c (x 1 ) ≤ • • • ≤ d G c (x m ) in the bipartite complement of G. Let S = {x 1 , . . . , x s }. Due to e(G) = mn-(⌊(n -t)/s⌋(m -s) + m + n -s -t + 1), all inequalities (5) become equalities, hence d G (x s ) = • • • = d G (x m ) = n-⌊(n-t)/s⌋-1 and e(G[S∪Y ]) = sn-n+t-1, which implies e(G c [S ∪Y ]) = n-t+1. Let r be the integer 0 ≤ r < s such that n-t = s⌊(n-t)/s⌋+r. Observe that d G c (x s-r ) = ⌊(n -t)/s⌋ + 1, for if not e(G c [S ∪ Y ]) ≤ (s -r)⌊(n -t)/s⌋ + r(⌊(n - t)/s⌋ + 1) = n -t, which is not possible. So we have d G c (x s-r ) = • • • = d G c (x m ) = ⌊(n -t)/s⌋ + 1; and d G c (x i ) ≤ ⌊(n -t)/s⌋ + 1 for every i ∈ {1, . . . , s -r -1} if r ≤ s -2. (7)
Moreover, notice that d G c (x 1 ) = ⌊(n-t)/s⌋+1 can only occur when

r = s-1, because e(G c [S ∪Y ]) = n -t + 1 equals s(⌊(n -t)/s⌋ + 1) = n -t -r + s. It is also clear that d G c (x s-1 ) ≥ 1 because otherwise we have d G c (x i ) =
From ( 8) it follows that

N G c (x) ∩ N G c (x ′ ) = ∅ for all distinct vertices x, x ′ ∈ S. Claim 1: If d G c (x s-1 ) = ⌊(n -t)/s⌋ + 1 then N G c (x) ∩ N G c (x ′ ) = ∅ for any two distinct vertices x, x ′ ∈ X. To prove this claim suppose N G c (x) ∩ N G c (x ′ ) = ∅,
hence we can assume x ′ ∈ X \ S. If x, x ′ share some neighbor, using [START_REF] Goddard | Bipartite Ramsey numbers and Zarankiewicz numbers[END_REF] we obtain a contradiction with Remark 3.1 as follows:

⋆ if x ∈ S, taking x ′′ ∈ {x s-1 , x s }, x ′′ = x, it follows |N G c ((S \ {x ′′ }) ∪ {x ′ }) | ≤ n -t; ⋆ if x ∈ X \ S then |N G c ((S \ {x s-1 , x s }) ∪ {x, x ′ }) | ≤ n -t. ✷ As a consequence of Claim 1, if r ≥ 1 then N G c (x) ∩ N G c (x ′ ) = ∅
for any two distinct vertices x, x ′ ∈ X, which follows from [START_REF] Godbole | Threshold functions for the bipartite Turán property[END_REF] because in this case d G c (x s-1 ) = ⌊(nt)/s⌋ + 1.

Now assume that r = s -1. Then from [START_REF] Godbole | Threshold functions for the bipartite Turán property[END_REF] it follows that d G c (x i ) = ⌊(nt)/s⌋ + 1 for all i ∈ {1, 2, . . . , m}, and by Claim 1 it turns out that G = K (m,n) -E(H) where H consists of the union of m disjoint copies of K (1,⌊(n-t)/s⌋+1) . Therefore H ∈ F 3 (m, n; s, t) in this case. The proof continues for 0 ≤ r ≤ s -2.

Assume now that d G c (x s-r-1 ) = ⌊(n-t)/s⌋+1, which implies 0 ≤ r ≤ s-3 (because x s-r-1 = x 1 for the case r = s -2, and d G c (x 1 ) = ⌊(nt)/s⌋ + 1 if and only if r = s -1). Hence from [START_REF] Godbole | Threshold functions for the bipartite Turán property[END_REF] there exists some integer k with 2 ≤ k ≤ sr -1 such that d G c (x i ) = ⌊(nt)/s⌋ + 1 for all i ∈ {k, . . . , m} and d G c (x i ) ≤ ⌊(nt)/s⌋ for all If r = 0, from [START_REF] Godbole | Threshold functions for the bipartite Turán property[END_REF] we have that all the vertices x s , . . . , x m have the same degree equal to (nt)/s + 1 in G c , hence (8) applied to the s-set S \ {x s } ∪ {x j } yields N G c (x j ) ∩ N G c (S \ {x s }) = ∅ for every j ∈ {s, . . . , m}. This means that the subgraphs

1 ≤ i ≤ k -1. Hence 0 ≤ k-1 i=1 d G c (x i ) = e(G c [S ∪ Y ]) -(s -k + 1)(⌊(n-t)/s⌋+1) = (k-1)(⌊(n-t)/s⌋+1)-(s-r)+1, yielding k ≥ (n-t+s 2 -r(s+1))/(n-t+s-r). That is to say, s -r -1 ≥ k ≥ ⌈(n -t + s 2 -r(s + 1))/(n -t + s -r)⌉ ≥ 2. Therefore by Claim 1 we conclude that G = K (m,n) -E (H 1 ∪ H 2 ), the subgraphs H 1 and H 2 being disjoint, where H 1 is the union of k -1 disjoint subgraphs K (1,d1) , . . . , K (1,d k-1 ) , with 0 ≤ d 1 ≤ . . . ≤ d k-1 ≤ ⌊(n -t)/s⌋ and d 1 + . . . + d k-1 = (k -1)(⌊(n -t)/s⌋ + 1) -(s -r) + 1; and H 2 is the union of m -k + 1 disjoint copies of the graph K (1,⌊(n-t)/s⌋+1) . Therefore H 1 ∪ H 2 ∈ F 2 (m, n; s, t). Finally, assume that d G c (x s-r-1 ) ≤ ⌊(n-t)/s⌋. Then d G c (x i ) = ⌊(n-t)/s⌋ for each i ∈ {1, . . . , s- r -1}, because otherwise e(G c [S ∪ Y ]) < (s -r -1)⌊(n -t)/s⌋ + (r + 1) (⌊(n -t)/s⌋ + 1) = s⌊(n -t)/s⌋ + r + 1 = n -t + 1, an absurdity. If r ≥ 1 then d G c (x s-1 ) = ⌊(n -t)/
H 1 = G c [(S \ {x s }) ∪ N G c (S \ {x s })] and H 2 = G c [{x s , . . . , x m } ∪ N G c ({x s , . . . , x m })] are disjoint, H 1 consisting of the union of s -1 disjoint subgraphs K (1,(n-t)/s) . Notice that |N G c (x)∩N G c (x ′ )| ≤ 1 for every two distinct x, x ′ ∈ {x s , . . . , x m }. Otherwise the set S ′ = (S \ {x s-1 , x s }) ∪ {x, x ′ } satisfies |N G c (S ′ )| ≤ |N G c (S \ {x s-1 , x s })| + |N G c ({x, x ′ })| ≤ (s -2)(n -t)/s + 2((n -t)/s + 1) -2 = n -t, contradicting again Remark 3.1.
Observe also that every cycle of H 2 , if any, has length at least 2(s + 1), because if C is such a cycle of length 2l with 2 ≤ l ≤ s, then the s-subset S ′ of X consisting of l vertices of C and any sl

vertices in V (H 1 ) ∩ X ⊆ {x 1 , . . . , x s-1 } satisfies |N G c (S ′ )| = (s -l)(n -t)/s + l(n -t)/s = n -t, against Remark 3.1.
As a consequence, H 2 is either acyclic, or each of its cycles has length at least 2(s + 1). In any case all vertices of H 2 belonging to X have degree (nt)/s + 1 in G c . Therefore H 1 ∪ H 2 ∈ F 1 (m, n; s, t). To finish, notice that for each of the cases 1 to 4 of the theorem there exists at least one suitable family of subgraphs F i (m, n; s, t) = ∅ such that Z(m, n; s, t) is guaranteed to be nonempty (see our comment after Lemma 3.3 and the hypotheses of the theorem). This finishes the proof.

✷ Lemma 3.4 Let n, t be integers such that 2 ≤ t ≤ n ≤ 2t -1. Then the 3-partite graph G = G(X, Y, Z) = K 3 (n) -M does not contain K 3 (t)

Fig. 1 :

 1 Fig. 1: H ∈ F1(8, 8; 3, 5); H ′ ∈ F2(5, 10; 4, 6) (with k = 3); H ′′ ∈ F3(5, 10; 4, 5).

Lemma 3 . 1

 31 Let m, n, s, t be integers such that 2 ≤ s ≤ m and 2 ≤ t ≤ n. Thenz(m, n; s, t) ≤ mn -(α + m + nst + 1) , where α = max ⌊(nt)/s⌋(ms), ⌊(ms)/t⌋(nt) .Proof: Let G = G(X, Y ) be a graph belonging to Z(m, n; s, t). Let us order the vertices of V (G) in such a way that d G (x i ) ≥ d G (x i+1 ), for i ∈ {1, . . . , m -1} and d G (y j ) ≥ d G (y j+1 ), for j ∈ {1, . . . , n -1}. Let us consider the subsets S = {x 1 , . . . , x s } and T = {y 1 , . . . , y t }.

  0 for all i ∈ {1, . . . , s -1} and then n -t + 1 = e(G c [S ∪ Y ]) = d G c (x s ), which is impossible since d G c (x s ) = ⌊(nt)/s⌋ + 1 and s ≥ 2.Taking into account that nt+ 1 = e(G c [S ∪ Y ]) ≥ |N G c (S)| and by applying Remark 3.1 we have e(G c [S ∪ Y ]) = |N G c (S)| = nt + 1.

Lemma 3 . 5

 35 as a subgraph, where M is a matching of cardinality 2n -2t + 1 in the subgraph G[X ∪ Y ].Proof: Let us consider the bipartite subgraph Γ induced by X ∪Y in K 3 (n)-M . Since Γ = K (n,n) -M , then Γ ∈ Z(n; t) because M is a matching of cardinality 2n -2t + 1 (see Th. 1.2 of[START_REF] Balbuena | New results on the Zarankiewicz problem[END_REF]), and therefore Γ is free of K (t,t) as a subgraph. So K 3 (n) -M is free of K 3 (t) and the result holds.✷ Let n, t be integers such that 2 ≤ t ≤ n and let G = G(T, Y, Z) be a 3-partite graph with|T | = t, |Y | = |Z| = n free of the complete 3-partite graph K 3 (t). Then e(G) ≤ n 2 + 2nt -(nt + 1) . Proof: Assume that e(G) ≥ n 2 + 2nt -(nt), hence e(G c ) ≤ nt. If we denote by r T Y , r T Z and r Y Z the number of edges of the subgraphs G c [T ∪ Y ], G c [T ∪ Z] and G c [Y ∪ Z], respectively, then we have r T Y + r T Z + r Y Z ≤ nt.Let us denote by Y ′ and Z ′ , respectively, the subsets of Y and Z whose vertices have degree t + n in G. It is clear that|Y | = |Y ′ | + |Y \ Y ′ | ≤ |Y ′ | + (r T Y + r Y Z ), |Z| = |Z ′ | + |Z \ Z ′ | ≤ |Z ′ | + (r T Z + r Y Z ). Hence |Y ′ | ≥ n -(r T Y + r Y Z ) ≥ t + r T Z ≥ t and |Z ′ | ≥ n -(r T Z + r Y Z ) ≥ t + r T Y ≥ t. But then G[T ∪ Y ′ ∪ Z ′ ] contains K 3 (t)and the result follows. ✷ Proof: of Theorem 2.3. We know that z 3 (n) ≥ 3n 2 -(2(nt) + 1) because of Lemma 3.4. To show the other inequality, let G = G(X, Y, Z) be a 3-partite graph free of K 3 (t) as a subgraph. Let us order the vertices X = {x 1 , . . . , x n }, Y = {y 1 , . . . , y n } and Z = {z 1 , . . . , z n} so that d G c (x i ) ≤ d G c (x i+1 ), d G c (y i ) ≤ d G c (y i+1 ) and d G c (z i ) ≤ d G c (z i+1 ) for all i ∈ {1, . . . , n -1}. At least one vertex v of the set {x t , y t , z t } has degree d G c (v) ≥ 1, because if d G c (x t ) = d G c (y t ) = d G c (z t ) = 0 then d G (x i ) = d G (y i ) = d G (z i ) =2n for all i ∈ {1, . . . , t} and hence K 3 (t) ⊆ G against our assumptions. Assume that d G c (x t ) ≥ 1 and so d G c (x i ) ≥ 1 for i ∈ {t, . . . , n}. Then G[T ∪ Y ∪ Z] must be free of K 3 (t) where T = {x 1 , . . . , x t }. Hence, by applying Lemma 3.5, we have e(G[T∪ Y ∪ Z]) ≤ n 2 + 2nt -(nt + 1). This implies that e(G c ) = e(G c [T ∪ Y ∪ Z]) + e(G c [(X \ T ) ∪ Y ∪ Z]) ≥ nt + 1 + n i=t+1 d G c (x i ) = nt + 1 + nt = 2(nt) + 1,thus e(G) ≤ 3n 2 -(2(nt) + 1). This proves the theorem. ✷

  Let m, n, s, t be integers such that 2 ≤ s ≤ m and 2 ≤ t ≤ ns. Assume that F i (m, n; s, t) = ∅, i ∈ {1, 2, 3}, and let

	Lemma 3.2
	1) ,
	and the result holds.	✷

  s⌋ + 1 by[START_REF] Godbole | Threshold functions for the bipartite Turán property[END_REF], so Claim 1 allows us to deduce that G = K (m,n) -E (H 1 ∪ H 2 ), the subgraphs H 1 and H 2 being disjoint, where H 1 consists of the union of sr -1 disjoint copies of K (1,⌊(n-t)/s⌋) and H 2 is the union of ms + r + 1 disjoint copies of the graph K (1,⌊(n-t)/s⌋+1) . Then, H 1 ∪ H 2 ∈ F 3 (m, n; s, t).

Acknowledgment

Research supported by the Ministry of Education and Science, Spain, and the European Regional Development Fund (ERDF) under project MTM2005-08990-C02-02; and under the Andalusian Government project P06-FQM-01649.