Svjetlan Feretić

A perimeter enumeration of column-convex polyominoes

Keywords: Column-convex polyomino, Rectangular lattice, Hexagonal lattice, Perimeter generating function, Sequence of tailed polyominoes, Wall polyomino

This work is concerned with the perimeter enumeration of column-convex polyominoes. We consider both the rectangular lattice and the hexagonal lattice. For the rectangular lattice, two formulae for the generating function already exist, and neither of them seems to admit further simplification. We first rederive those two formulae (so as to make the paper self-contained), and then we enrich the rectangular lattice generating function with some additional variables. Subsequently, we make a change of variables, which (nearly) produces the hexagonal lattice generating function. This latter generating function was first found by Lin and Wu in 1990. However, our present formula, in addition to having a simpler form, also allows a substantially easier Taylor series expansion. As to the methods, our approach is inspired by algebraic languages, whereas Lin and Wu used the Temperley methodology.

Introduction

The enumeration of polyominoes (by perimeter and/or area) is a topic of great interest to physicists, chemists and combinatorialists alike. So far nobody has succeeded to count the set of all polyominoes. That set could easily remain beyond reach for a very long time. In view of this, it is easy to understand that those subsets of polyominoes which are reasonably numerous, but amenable to counting, enjoy considerable popularity. At present, not a wide variety of such subsets is known. In fact, each of today's numerous-yet-tractable sets of polyominoes is in some way derived either from column-convex polyominoes or from directed animals (or from both) (i) . Column-convex polyominoes were first presented in Temperley's 1956 paper [START_REF] Temperley | Combinatorial problems suggested by the statistical mechanics of domains and of rubber-like molecules[END_REF], and directed animals were first presented in Dhar, Phani and Barma's 1982 paper [START_REF] Dhar | Enumeration of directed site animals on two-dimensional lattices[END_REF]. (It is plausible that directed animals appeared comparatively late because they do not submit to column-by-column approaches.)

On some lattices (such as e.g. the square lattice), directed animals have an algebraic area generating function, which satisfies a quadratic equation [START_REF] Bousquet-Mélou | New enumerative results on two-dimensional directed animals[END_REF][START_REF] Penaud | Arbres et animaux[END_REF][START_REF] Shapiro | Directed animals and Motzkin paths[END_REF]. Moreover, stacked directed animals and multidirected animals (two recent models due to Bousquet-Mélou and Rechnitzer [START_REF] Bousquet-Mélou | Lattice animals and heaps of dimers[END_REF]) substantially generalize square-lattice directed animals and still have nice-looking area generating functions. On the other hand, the perimeter generating function for directed animals is not known, and is probably very complicated.

Column-convex polyominoes have a rational area generating function and an algebraic perimeter generating function; the latter generating function satisfies a quartic equation. In detail, the cells of a columnconvex polyomino can be either squares or hexagons (other shapes are not so popular), but in both cases the generating functions have the nature just described.

Temperley [START_REF] Temperley | Combinatorial problems suggested by the statistical mechanics of domains and of rubber-like molecules[END_REF] dealt with column-convex polyominoes with square cells. He computed the area generating function and started computing the perimeter generating function (which we denote G sq ), but he had to stop because the formulae became too bulky. Later on, Temperley's computations were completed by use of computer algebra systems. That was done in Brak, Guttmann and Enting [START_REF] Brak | Exact solution of the row-convex polygon perimeter generating function[END_REF], and in Lin [START_REF] Lin | Perimeter generating function for row-convex polygons on the rectangular lattice[END_REF]. Nevertheless, it was in Delest [START_REF] Delest | Generating functions for column-convex polyominoes[END_REF] that a formula for G sq was given for the first time; the papers [START_REF] Brak | Exact solution of the row-convex polygon perimeter generating function[END_REF][START_REF] Lin | Perimeter generating function for row-convex polygons on the rectangular lattice[END_REF] appeared after [START_REF] Delest | Generating functions for column-convex polyominoes[END_REF]. Delest did not follow Temperley's approach. Instead, she used the Dyck-Schützenberger-Viennot method, a method in which polyominoes are encoded by words of algebraic languages. However, Delest's formula for G sq was very complicated. This is similar for the formulae of [START_REF] Brak | Exact solution of the row-convex polygon perimeter generating function[END_REF][START_REF] Lin | Perimeter generating function for row-convex polygons on the rectangular lattice[END_REF]. (Our understanding is granted. Erdős has stated that no one blames a mathematician if his or her first solution of a problem is messy [13, p. 289].) Later on, Feretić and Svrtan [START_REF] Feretić | On the number of column-convex polyominoes with given perimeter and number of columns[END_REF] recomputed G sq by the algebraic-language method, then upgraded the Temperley method, and then applied the upgraded method to derive G sq once again. As a result, in [START_REF] Feretić | On the number of column-convex polyominoes with given perimeter and number of columns[END_REF] there are two formulae for G sq (equivalent to one another), each of which is considerably simpler than the formulae of [START_REF] Brak | Exact solution of the row-convex polygon perimeter generating function[END_REF][START_REF] Delest | Generating functions for column-convex polyominoes[END_REF][START_REF] Lin | Perimeter generating function for row-convex polygons on the rectangular lattice[END_REF]. In the end, Feretić [START_REF] Feretić | The column-convex polyominoes perimeter generating function for everybody[END_REF][START_REF] Feretić | A new way of counting the column-convex polyominoes by perimeter[END_REF] remarked that column-convex polyominoes are closely related to wall polyominoes of odd width. This remark allowed an easy rederivation of G sq , and also accounted for the form which G sq has.

As to column-convex polyominoes with hexagonal cells, their area generating function was first found by Klarner [START_REF] Klarner | Cell growth problems[END_REF], and their perimeter generating function (which we denote G hex ) was first found by Lin and Wu [START_REF] Lin | Unidirectional-convex polygons on the honeycomb lattice[END_REF]. Subsequently, Feretić and Svrtan [START_REF] Feretić | On the number of column-convex polyominoes with given perimeter and number of columns[END_REF] recomputed G hex by two methods, just as they did with G sq . So, in [START_REF] Feretić | On the number of column-convex polyominoes with given perimeter and number of columns[END_REF] there are two formulae for G hex , too. Each of these two formulae is shorter than Lin and Wu's formula for G hex . But, unfortunately, each of Feretić and Svrtan's [START_REF] Feretić | On the number of column-convex polyominoes with given perimeter and number of columns[END_REF] two formulae for G hex is seriously wrong. (The moral is that every new formula needs a careful check.) Since [START_REF] Feretić | On the number of column-convex polyominoes with given perimeter and number of columns[END_REF] was published, no attempt has been made to derive G hex once again. For a fairly long time, Lin and Wu's formula has remained the only-and hence the nicest-correct formula for G hex . In this paper, however, we shall express G hex more simply and "Taylor-expandably" than Lin and Wu did. As to a check, we engaged Maple to expand our new expression for G hex , and then also Lin and Wu's expression for G hex , in a Taylor series through thirtieth-order terms. The two expansions agreed, and therefore we are convinced that our new formula is correct. This paper continues as follows. In Section 2, we state the necessary definitions. In Sections 3 to 5, we repeat Feretić's [START_REF] Feretić | The column-convex polyominoes perimeter generating function for everybody[END_REF] derivation of G sq . (The repeated derivation appears in the present one as an essential part.) In particular, in Section 4 we find K, the perimeter generating function for wall polyominoes. In Section 6, we enrich K with an extra variable, which keeps track of repeats. In Section 7, we digress to state the other formula for G sq . In Section 8, we prove that the two formulae for G sq are equivalent. In Sections 9 to 12, we study the properties of wall polyominoes of odd width. Each section is entitled after one or two properties therein considered. In Section 13, wall polyominoes of odd width are already under our control, and we recast their generating function as a generating function for general column-convex polyominoes. In Section 14, a change of variables, together with a bit of gluing, gives us the series G hex . Finally, in Section 15, we outline a proof that the formula for G hex found in Section 14 is equivalent to Lin and Wu's formula for G hex .

Annotated definitions

A plane has three regular tilings: one with squares, one with hexagons, and one with triangles. The square, hexagonal and triangular tiles give rise to the square, hexagonal and triangular lattices, respectively. The hexagonal lattice is also known as the honeycomb lattice. In this paper, we confine our attention to the square and hexagonal lattices. We draw these two lattices so that every tile has two horizontal edges. See Fig. 1.

In a regularly tiled plane, a tile is often referred to as a cell. A polyomino is a finite union of cells which possesses a connected interior. A polyomino P is column-convex if on the boundary of P there are not more than two horizontal edges having the same horizontal projection. See Fig. 2.

The cells of a column-convex polyomino P fall into classes according to their horizontal projection. Each of those classes is called a column of P .

We denote the perimeter generating functions for column-convex polyominoes by G sq = G sq (x, y) and G hex = G hex (x, y, z). The series G sq refers to the square lattice. It is defined as follows:

G sq (x, y) = P a column-convex polyomino
x No. of horizontal edges of P • y No. of vertical edges of P .

(

) 1
The series G hex refers to the hexagonal lattice, and is defined by

G hex (x, y, z) = P a column-convex polyomino
x No. of horizontal edges of P • y No. of edges of P with a +60 • slope • z No. of edges of P with a -60 • slope . In the rest of this section, as well as in the next ten sections, we concentrate on the square lattice.

For certain prominent points of a column-convex polyomino, we use the name poles and we write SW, N W, N E and SE. For example, the SW pole is the lower end of the left border of the leftmost column. Similarly for the other poles. See Fig. 2 again.

Imagine a column-convex polyomino P with a "tail" t of nonnegative integer length, going straight down from the SW pole of P . We call the union P ∪ t a tailed polyomino or, briefly, a tapo. See Fig. 3. The figure also shows the poles of a tapo: the SW pole is the lower end of the tapo's tail, while the other three poles are inherited from the underlying column-convex polyomino.

For n ∈ N, let T 1 be a column-convex polyomino, and let T 2 , T 3 , . . . , T n be tapoes. Suppose that, for every i ∈ {2, 3, . . . , n}, the SW pole of T i coincides with the N E pole of T i-1 . Then we call the union n i=1 T i a stapo. (The name "stapo" is an abbreviation for a sequence of tailed polyominoes (ii) .) Note that the stapoes with n = 1 are simply column-convex polyominoes. See Fig. 4.

We denote the perimeter generating functions for tapoes and stapoes by H and I, respectively. Both H and I have two variables, x and y. In the series H, the exponent of x means the number of horizontal edges, and the exponent of y in principle means the number of vertical edges. For computational convenience, however, we adopt the following agreement: if a tapo T has a tail of length k, and the rest of T is a column-convex polyomino with 2i horizontal edges and 2j vertical edges, then the contribution of T to the series H is x 2i y 2j+2k (and not x 2i y 2j+k ). The series I is defined likewise. That is, if a stapo S has 2i horizontal edges, 2j vertical edges not belonging to tails, and k vertical edges belonging to tails, then the contribution of S to the series I is again x 2i y 2j+2k . By virtue of the above definitions, we have

H = G sq (1 + y 2 + y 4 + y 6 + . . .) = G sq 1 -y 2 (2)
and

I = G sq (1 + H + H 2 + H 3 + . . .) = G sq 1 -H . (3)
Let J = I 1-y 2 . We can think of J as the perimeter generating function for objects which are very similar to stapoes, the only difference being that the leftmost column-convex polyomino, too, is allowed to have a tail. From (2) and (3) it follows that

J = H 1 -H . (4)
Hence

H = 1 - 1 1 + J . (5)
A column-convex polyomino P is a wall polyomino if the bottom sides of the columns of P all lie on the same horizontal line. Wall polyominoes are also known as bargraph polygons.

We denote the perimeter generating function for wall polyominoes by

K = K(x, y). The definition of K is K(x, y) = P a wall polyomino
x No. of columns of P • y No. of vertical edges of P .

Thus, the roles of x in G sq and in K are somewhat different.

A bijection between stapoes and wall polyominoes of odd width

Stapoes are interesting because of a simple bijection which maps them onto the wall polyominoes of odd width. Let S be a stapo with n columns. Let Y i (S) and y i (S) be the maximal ordinate and the minimal ordinate of the ith column of S. With S we associate ϕ(S), a wall polyomino having 2n -1 columns. From left to right, the heights of those columns are

Y 1 (S) -y 1 (S), Y 2 (S) -y 1 (S), Y 2 (S) -y 2 (S), Y 3 (S) -y 2 (S), . . . , Y n-1 (S) -y n-1 (S), Y n (S) -y n-1 (S), and Y n (S) -y n (S).
Thus, the 1st, 3rd, 5th, . . . columns of the wall polyomino ϕ(S) are copies of the 1st, 2nd, 3rd, . . . columns of the stapo S. The 2nd, 4th, 6th, . . . columns of ϕ(S) tell us how the 2nd, 3rd, 4th, . . . columns of S are placed with respect to their left neighbour columns. For example, if the 6th column of ϕ(S) is of height 5, then the top of the 4th column of S lies 5 lattice units higher than the bottom of the 3rd column of S. See Fig. 5.

With the above-stated agreement that a tail of length k has 2k vertical edges, the vertical perimeters of S and ϕ(S) relate in the simplest way. Namely, they are equal. On the other hand, the horizontal perimeter of S is by one greater than the number of columns of ϕ(S). So, the perimeter generating function for stapoes is x times the perimeter generating function for wall polyominoes of odd width. That is,

I = x 2 • [K(x, y) -K(-x, y)]. (6)
Now we shall compute K, and then it will be no problem to obtain I, J, H and G sq one after another.

The perimeter generating function for wall polyominoes

Let W denote the set of all wall polyominoes. Let W α denote the set of wall polyominoes that have no one-celled columns. For P ∈ W \ W α , we define leone(P ) to be the leftmost one-celled column of P . We partition the set W \ W α into four subsets: W β , W γ , W δ and W ǫ . The definitions are:

• W β := {P ∈ W \ W α : leone(P ) is both the leftmost and the rightmost column of P },

• W γ := {P ∈ W \ W α : leone(P ) is the leftmost, but not the rightmost column of P },

• W δ := {P ∈ W \ W α : leone(P ) is the rightmost, but not the leftmost column of P },

• W ǫ := {P ∈ W \ W α : leone(P ) is neither the leftmost nor the rightmost column of P }.

We write K α , K β , K γ , K δ and K ǫ to denote the parts of the series K that come from the sets W α , W β , W γ , W δ and W ǫ , respectively. With one eye on Fig. 6, we observe the following.

Between the sets W and W α there is an obvious bijection: Below a polyomino P ∈ W , we put a "pad" of height one. (The pad is as wide as P is.) In this way, the vertical perimeter increases by two. Therefore, we have

K α = y 2 K.
The set W β has only one element, namely the one-celled polyomino. So,

K β = xy 2 .
There also exists an obvious bijection between the sets W and W γ : Just to the left of a polyomino P ∈ W , we place an extra column of height one. Under this bijection, the number of columns increases by one and the vertical perimeter remains the same. So, K γ = xK. There is yet another obvious bijection: Given P ∈ W α , we map it into W δ by placing an extra column of height one just to the right of P . Under this bijection, too, the number of columns increases by one, while the vertical perimeter remains the same. So,

K δ = xK α = xy 2 K.
Finally, let P ∈ W ǫ . We decompose P into two wall polyominoes, say Q 1 and Q 2 . The polyomino Q 1 is a left factor; it begins with the first column of P and ends with the column which is the left neighbour of leone(P ). Thus, Q 2 begins with leone(P ) and ends with the last column of P .

We see that Q 1 lies in W α and that Q 2 lies in W γ . The number of columns of P is just the sum of the numbers of columns of Q 1 and Q 2 . The vertical perimeter of P is equal to vertical perimeter of Q 1 plus vertical perimeter of Q 2 minus two. Moreover, the decomposition

P → (Q 1 , Q 2 ) is a bijection from W ǫ to the Cartesian product W α × W γ . Altogether, we have K ǫ = y -2 K α K γ = xK 2 . Since K = K α + K β + K γ + K δ + K ǫ ,
it follows that the generating function K satisfies a quadratic equation:

K = y 2 K + xy 2 + xK + xy 2 K + xK 2 ,
which can be written as

xK 2 + [-(1 -y 2 ) + x(1 + y 2 )]K + xy 2 = 0. (7)
Solving equation ( 7), we obtain the following proposition.

Proposition 1 The perimeter generating function for wall polyominoes is given by

K = 1 -y 2 -x(1 + y 2 ) -(1 -x) 2 (1 -y 2 ) 2 -4xy 2 (1 -y 2 ) 2x . (8)
5 A formula for G sq By substituting (8) into (6), we get

I = 1 4 2(1 -y 2 ) -(1 -x) 2 (1 -y 2 ) 2 -4xy 2 (1 -y 2 ) -(1 + x) 2 (1 -y 2 ) 2 + 4xy 2 (1 -y 2 ) .
We defined J to be I 1-y 2 . Hence, we find

J = 2 -(1 -x) 2 -4xy 2 1-y 2 -(1 + x) 2 + 4xy 2 1-y 2 4 . (9)
By ( 2) and ( 5),

G sq = (1 -y 2 )H = (1 -y 2 ) 1 -4 4+4J .
Here we insert [START_REF] Klarner | Cell growth problems[END_REF], and the result reads as follows.

Theorem 1 The perimeter generating function for column-convex polyominoes on the rectangular lattice is given by

G sq = (1 -y 2 )   1 - 4 6 -(1 -x) 2 -4xy 2 1-y 2 -(1 + x) 2 + 4xy 2 1-y 2   . (10)
Formula (10) first appeared in Feretić and Svrtan [START_REF] Feretić | On the number of column-convex polyominoes with given perimeter and number of columns[END_REF].

Repeats

Now that we know G sq , we want to find G hex as well. To achieve this goal, we are going to carry out a more detailed exploration of wall polyominoes. We shall take into account several new properties, the first of which will be repeats; by a repeat we mean the event that two neighbouring columns have the same height.

Let L = L(x, y) be the part of K that comes from wall polyominoes having no repeats. Let M = M (x, e, y) be defined by the formula M (x, e, y) = P a wall polyomino

x No. of columns of P • e No. of repeats of P • y No. of vertical edges of P .

To see how the generating functions K, L and M relate to one another, it is useful to write down a procedure.

Procedure 1 Choose a wall polyomino P without repeats. For every column c of P , make either 0, or 1, or 2, or 3, . . . duplicates of c; then insert those duplicates just to the right of c.

The output of Procedure 1 is just W , the set of all wall polyominoes. Moreover, every wall polyomino is produced in a unique way. Thus, we have M (x, e, y) = L( x 1-xe , y) and L( x 1-x , y) = K(x, y). So,

M (x, e, y) = L x 1 -xe + x -x , y = L x 1-xe+x 1 - x 1-xe+x , y = K x 1 -xe + x
, y .

Therefore we substitute

x 1-xe+x for x in [START_REF] Feretić | On the number of column-convex polyominoes with given perimeter and number of columns[END_REF], and the result is

M = (1 -xe)(1 -y 2 ) -2xy 2 -(1 -xe) 2 (1 -y 2 ) 2 -4xy 2 [1 -x(e -1)](1 -y 2 ) /(2x).
(11) To summarize, we changed a variable in a known generating function, and we obtained a generating function enriched with an extra variable. Later in this paper, this change-of-variable method will give us some results that seem hard to obtain in another way. In the case of formula [START_REF] Lin | Unidirectional-convex polygons on the honeycomb lattice[END_REF], however, a simple alternative exists. It is quite possible to refine the proof of Proposition 1 so that repeats are taken into account, too. The reader may do this alternative proof by herself/himself.

Let

M 1 = M (x, e, y) -M (-x, e, y) 2 .
That is to say, M 1 is the portion of M coming from wall polyominoes which have an odd number of columns. Using formula [START_REF] Lin | Unidirectional-convex polygons on the honeycomb lattice[END_REF] and the notations

∆ -= (1 -xe) 2 (1 -y 2 ) 2 -4xy 2 [1 -x(e -1)](1 -y 2 )
and

∆ + = (1 + xe) 2 (1 -y 2 ) 2 + 4xy 2 [1 + x(e -1)](1 -y 2 ),
we readily obtain

M 1 = 2(1 -y 2 ) -∆ --∆ + 4x . ( 12
)
Next we would like to have an algebraic equation for M 1 . For this purpose, we first rewrite [START_REF] Penaud | Arbres et animaux[END_REF] as

∆ + = 2(1 -y 2 -2xM 1 ) -∆ -.
By squaring and then rearranging, we get

4 ∆ -(1 -y 2 -2xM 1 ) = 4(1 -y 2 -2xM 1 ) 2 + ∆ --∆ + .
Then we square again, rearrange again, recall the definitions of ∆ -and ∆ + , and eventually divide the equation by 16(1 -y 2 ) 4 . The result is

1 - 2xM 1 1 -y 2 4 -1 + x 2 e 2 + 4x 2 y 2 e -1 1 -y 2 1 - 2xM 1 1 -y 2 2 + x 2 e + 2y 2 1 -y 2 2 = 0. (13)
7 One more formula for G sq

The case e = 1 of ( 13) is also interesting. Let us turn to that case for a moment. For e = 1, xM 1 is x[K(x, y) -K(-x, y)]/2, which is, by [START_REF] Feretić | The column-convex polyominoes perimeter generating function for everybody[END_REF], equal to I. We defined J to be I 1-y 2 .

Hence xM1

1-y 2 is equal to J, and J is, by ( 4), equal to H 1-H . So, from ( 13) we obtain

1 - 2H 1 -H 4 -(1 + x 2 ) 1 - 2H 1 -H 2 + x 2 1 + y 2 1 -y 2 2 = 0. (14)
The solution of ( 14) is

1 - 2H 1 -H = 1 + x 2 + (1 -x 2 ) 2 -16x 2 y 2 (1-y 2 ) 2 √ 2 . Since H = 1 - 2 3 -1 -2H 1-H , it follows that H = 1 - 2 √ 2 3 √ 2 -1 + x 2 + (1 -x 2 ) 2 -16x 2 y 2 (1-y 2 ) 2 .
Multiplying by 1 -y 2 , we obtain the following theorem.

Theorem 2 The perimeter generating function for column-convex polyominoes on the rectangular lattice is given by

G sq = (1 -y 2 )     1 - 2 √ 2 3 √ 2 -1 + x 2 + (1 -x 2 ) 2 -16x 2 y 2 (1-y 2 ) 2     . (15)
Now we have two formulae for G sq , viz. [START_REF] Lin | Perimeter generating function for row-convex polygons on the rectangular lattice[END_REF] and [START_REF] Temperley | Combinatorial problems suggested by the statistical mechanics of domains and of rubber-like molecules[END_REF]. These formulae look rather different from one another, but they are of course equivalent. Both [START_REF] Lin | Perimeter generating function for row-convex polygons on the rectangular lattice[END_REF] and [START_REF] Temperley | Combinatorial problems suggested by the statistical mechanics of domains and of rubber-like molecules[END_REF] were first obtained in [START_REF] Feretić | On the number of column-convex polyominoes with given perimeter and number of columns[END_REF].

8 Proof that formulae [START_REF] Lin | Perimeter generating function for row-convex polygons on the rectangular lattice[END_REF] and ( 15) are equivalent Under the inner square root in [START_REF] Temperley | Combinatorial problems suggested by the statistical mechanics of domains and of rubber-like molecules[END_REF], we do a series of rewritings:

(1 -x 2 ) 2 - 16x 2 y 2 (1 -y 2 ) 2 = (1 + x 2 ) 2 - 4x 2 (1 + y 2 ) 2 (1 -y 2 ) 2 = 1 + x 2 - 2x(1 + y 2 ) 1 -y 2 1 + x 2 + 2x(1 + y 2 ) 1 -y 2 = (1 -x) 2 - 4xy 2 1 -y 2 (1 + x) 2 + 4xy 2 1 -y 2 .
Using this, we rewrite the contents of the outer square root as follows:

1 + x 2 + (1 -x 2 ) 2 - 16x 2 y 2 (1 -y 2 ) 2 = 1 2 (1 -x) 2 - 4xy 2 1 -y 2 + 2 (1 -x) 2 - 4xy 2 1 -y 2 (1 + x) 2 + 4xy 2 1 -y 2 + (1 + x) 2 + 4xy 2 1 -y 2 = 1 2 (1 -x) 2 - 4xy 2 1 -y 2 + (1 + x) 2 + 4xy 2 1 -y 2 2 .
Thus, the big fraction in ( 15) is equal to

2 √ 2 3 √ 2 -1 √ 2 (1 -x) 2 -4xy 2 1-y 2 + (1 + x) 2 + 4xy 2 1-y 2 = 4 6 -(1 -x) 2 -4xy 2 1-y 2 -(1 + x) 2 + 4xy 2 1-y 2
, which is identical to the big fraction in [START_REF] Lin | Perimeter generating function for row-convex polygons on the rectangular lattice[END_REF]. Therefore, (15) can be rearranged into [START_REF] Lin | Perimeter generating function for row-convex polygons on the rectangular lattice[END_REF] and vice versa.

OEO repeats and single repeats

The digression finished, the variable e is around again. By substituting √ x for x in the series xM 1 , we obtain a new series, say N . We have N (x, e, y) = P a wall polyomino of odd width

x No. of odd columns of P • e No. of repeats of P • y vertical perimeter of P .

Here, it is understood that the odd columns of a wall polyomino are its first, third, fifth, . . . columns, while the even columns are those columns which are not odd. From (13) it follows that N satisfies the equation

1 - 2N 1 -y 2 4 -1 + xe 2 + 4xy 2 e -1 1 -y 2 1 - 2N 1 -y 2 2 + x e + 2y 2 1 -y 2 2 = 0. ( 16
)
The next property of interest are the OEO repeats (iii) . By definition, an OEO repeat is the event that three successive columns have the same height, and the first of those three columns is an odd column. We also define single repeats: A single repeat is a repeat not forming part of any OEO repeat.

Let O(x, d, e, y) = P a wall polyomino of odd width

x No. of odd columns of P • d No. of OEO repeats of P

•e

No. of single repeats of P • y vertical perimeter of P .

Then O(x, 0, e, y) is the part of N that comes from wall polyominoes of odd width having no OEO repeats. To see how the generating functions N , O(x, 0, e, y) and O(x, d, e, y) relate to one another, it is useful to write down a procedure.

Procedure 2 Choose a wall polyomino of odd width having no OEO repeats. In the chosen polyomino, focus on the odd columns. For every such column c, make either 0, or 2, or 4, or 6, . . . duplicates of c; then insert those duplicates just to the right of c.

The output of Procedure 2 is just the set of all wall polyominoes of odd width. Moreover, every wall polyomino of odd width is produced in a unique way. Thus, we have O(x, d, e, y) = O( 10 Low and high single repeats

Now that we drew a distinction between OEO repeats and single repeats, we wish to draw a further distinction between two kinds of single repeats. The definitions follow.

Every single repeat involves one even column, which is equally high as one (but not both) of its neighbour columns. If the even column is lower than its unlike neighbour column, we speak of a low single repeat. Otherwise we speak of a high single repeat.

Given a low single repeat, we can of course heighten the even column involved so as to produce a high single repeat. The point is that this low-to-high conversion does not affect the vertical perimeter. See Fig. 7. Naturally, under the similar conversion from a high single repeat into a low single repeat, the vertical perimeter is again unaffected.

For P a wall polyomino of odd width, we define a companion of P to be a wall polyomino which can be obtained from P by means of low-to-high and high-to-low conversions. We also define LSR polyominoes: An LSR polyomino is a wall polyomino of odd width which has no high single repeats. Every wall polyomino of odd width is a companion to one and only one LSR polyomino. (iii) OEO is an abbreviation for odd-even-odd. Then P (x, 0, b 0 , d, y) is a generating function for LSR polyominoes. An LSR polyomino has the same vertical perimeter as any of its companions. Hence P (x, 0, a 0 + b 0 , d, y) is a generating function for LSR polyominoes and all of their companions or, in other words, a generating function for all wall polyominoes of odd width. Thus, P (x, a 0 , b 0 , d, y) = P (x, 0, a 0 + b 0 , d, y). Since P (x, e, e, d, y) = O(x, d, e, y), it follows that P (x, a 0 , b 0 , d, y) = P (x, 0, a 0 + b 0 , d, y) = P (x, 0, a0+b0

2 + a0+b0 2 , d, y) = P (x, a0+b0 2 , a0+b0 2 , d, y) = O(x, d, a0+b0 2
, y). Now we use relation ( 17) to obtain

P (x, a 0 , b 0 , d, y) = N   x 1 + x (a0+b0) 2 4 -d , a 0 + b 0 2 , y   . ( 18
)
11 Chimneys

Having beaten the even columns which play a role in repeats, we now turn to the even columns which play no role in repeats.

We define a chimney to be an even column which is higher than both of its neighbour columns.

Mutatis mutandi, we handle chimneys as we handled repeats and OEO repeats. That is, first we define a generating function and then we write down a procedure. Let Then Q(x, a 0 , 0, b 0 , d, y) is the part of the generating function P that comes from wall polyominoes of odd width having no chimneys.

Q(x,

Procedure 3

• Choose a wall polyomino of odd width having no chimneys.

• In the chosen wall polyomino, choose some (or none) of the even columns living in high single repeats. Also choose some (or none) of the even columns living in OEO repeats.

• Visit the chosen columns one by one, each time placing either 1, or 2, or 3, . . . additional cells on the top of the column being visited.

This procedure is illustrated in Fig. 8. The output of Procedure 3 is just the set of all wall polyominoes of odd width. Moreover, every wall polyomino of odd width is produced in a unique way. Thus, we have

Q(x, a 0 , a, b 0 , d, y) = Q(x, a 0 + ay 2 1-y 2 , 0, b 0 , d + ay 2 1-y 2 , y) and Q(x, a 0 + y 2 1-y 2 , 0, b 0 , d + y 2 1-y 2 , y) = P (x, a 0 , b 0 , d, y). Therefore Q(x, a 0 , a, b 0 , d, y) = Q x, a 0 + (a -1)y 2 1 -y 2 + y 2 1 -y 2 , 0, b 0 , d + (a -1)y 2 1 -y 2 + y 2 1 -y 2 , y = P x, a 0 + (a -1)y 2 1 -y 2 , b 0 , d + (a -1)y 2 1 -y 2 , y .
With this relation in hand, we use (18) to obtain

Q(x, a 0 , a, b 0 , d, y) = N          x 1 + x    a0+ (a-1)y 2 1-y 2 +b0 2 4 -d -(a-1)y 2 1-y 2    , a 0 + (a-1)y 2 1-y 2 + b 0 2 , y          . ( 19
)
12 Wells

We are now ready for the next (and last) property.

A well is an even column which is lower than both of its neighbour columns. Wells are somewhat trickier than chimneys. To conquer wells, it is not enough to make a change of variables. So to speak, it is also necessary to make a change of the generating function. Anyway, the job begins in the usual way: first we define a generating function and then we write down a procedure. Let Then R(x, a 0 , a, b 0 , 0, d, y) is the part of Q that comes from wall polyominoes of odd width having no wells.

Procedure 4

• Choose a wall polyomino of odd width having no wells.

• In the chosen wall polyomino, choose some (or none) of the even columns living in low single repeats. Also choose some (or none) of the even columns living in OEO repeats.

• Visit the chosen columns one by one, each time lowering the column being visited either by 1, or by 2, or by 3, . . . . This procedure is illustrated in Fig. 9.

Notice that Procedure 4 generates polyominoes and non-polyominoes alike. That happens because when we lower a column, we are free to overdraw. For example, from a column of height 3, we get an (ex-)column whose height may be any of the numbers 2, 1, 0, -1, -2, -3, . . . . Thus, the output of Procedure 4 is a relatively large set: it contains every object whose form is either ⊓ or ⊓ ⊔ ⊓ or ⊓ ⊔ ⊓ ⊔ ⊓ or . . . . Here, every ⊓ is a wall polyomino of odd width, and every ⊔ is an ex-column of nonpositive height.

These facts observed, what can we say about generating functions? After a little thought, we realize that R(x, a 0 , a, b 0 , b, d, y)

1 -bR(x,a0,a,b0,b,d,y)

1-y 2 = R x, a 0 , a, b 0 + by 2 1 -y 2 , 0, d + by 2 1 -y 2 , y
R x, a 0 , a, b 0 + y 2 1 -y 2 , 0, d + y 2 1 -y 2 , y = Q(x, a 0 , a, b 0 , d, y) 1 -Q(x,a0,a,b0,d,y) 1-y 2 . Hence, R(x, a 0 , a, b 0 , b, d, y) 1 -bR(x,a0,a,b0,b,d,y) 1-y 2 = R x, a 0 , a, b 0 + (b -1)y 2 1 -y 2 + y 2 1 -y 2 , 0, d + (b -1)y 2 1 -y 2 + y 2 1 -y 2 , y = Q x, a 0 , a, b 0 + (b-1)y 2 1-y 2 , d + (b-1)y 2 1-y 2 , y 1 - Q x,
(1 -y 2 )R 1 -y 2 -(b -1)R = Q x, a 0 , a, b 0 + (b -1)y 2 1 -y 2 , d + (b -1)y 2 1 -y 2 , y . (20)
Combining ( 20) with (19), we get the following result:

(1 -y 2 )R 1 -y 2 -(b -1)R = N          x 1 + x    a0+b0+ (a+b-2)y 2 1-y 2 2 4 -d -(a+b-2)y 2 1-y 2    , a 0 + b 0 + (a+b-2)y 2 1-y 2 2 , y          . ( 21
)
13 The twilight of wall polyominoes

Our additional variables a 0 , a, b 0 , b and d have done us very good service. At this stage, however, it is possible to reduce the set of variables without incurring a serious loss of information.

From R(x, a 0 , a, b 0 , b, d, y), a generating function with seven variables, we pass to a generating function with four variables. Let S(x, a, b 0 , y) = P a wall polyomino of odd width

x No. of columns plus one of P • a No. of chimneys of P • b total No. of low single repeats, wells and OEO repeats of P 0 • y vertical perimeter of P .

Noticing that S = R(x 2 , 1, a, b 0 , b 0 , b 0 , y), from (21) we get

(1 -y 2 )S 1 -y 2 -(b 0 -1)S = N x 2 1 + x 2 λ 2 - , 1 + λ -, y , (22)
where

λ -= (a -1)y 2 + b 0 -1 2(1 -y 2 ) . (23)
Recall that in Section 3 we defined a bijection ϕ, which took us from stapoes to wall polyominoes of odd width. Now is the time to go back to stapoes. As a means of transportation, we shall use the bijection ϕ -1 . So, which kind of generating function for stapoes is the series S? Before answering this question, it is useful to give names to some properties of a stapo.

When we speak about a column of a stapo, and no ambiguity need be feared, we denote the maximum ordinate and the minimum ordinate of that column by Y and y, respectively.

Let a rise be the event that, in a pair of adjacent columns of a stapo, Y of the right column is greater than Y of the left column, and y of the right column is greater than y of the left column. Let a weak fall be the event that, in a pair of adjacent columns of a stapo, Y of the right column is less than or equal to Y of the left column, and y of the right column is less than or equal to y of the left column. Now, the alter ego of the series S is S = P a stapo

x horizontal perimeter of P • a No. of rises of P

•b

No. of weak falls of P 0 • y vertical perimeter of P .

Next we define a generating function for tapoes and a generating function for column-convex polyominoes. The names of these generating functions are T = T (x, a, b 0 , y) and G sq+ = G sq+ (x, a, b 0 , y), respectively. In each of the generating functions T and G sq+ , each of the variables has the same meaning as in S.

We have S = G sq+ (1 + aT + aT aT + aT aT aT + . . .) = G sq+ 1 -aT . Note that the twin which lives on the honeycomb lattice is subject to one (and only one) restriction on its freedom. Namely, it can have no ceiling overlaps. The definition follows.

Let P be a column-convex polyomino on the honeycomb lattice. A ceiling overlap is the event that, in a pair of adjacent columns of P , the bottom cell of the right column is the upper right neighbour of the top cell of the left column.

So, U (x, y, z) is also the perimeter generating function for column-convex polyominoes which live on the honeycomb lattice, but have no ceiling overlaps.

From now on, when we say "a column-convex polyomino", we mean a column-convex polyomino on the honeycomb lattice.

Let P be a column-convex polyomino, and let P have one ceiling overlap. Then we can think of P as two column-convex polyominoes, say P 1 and P 2 , staying stuck together. Here, neither of P 1 and P 2 has any ceiling overlaps. See Fig. 13. Notice that P has two z-edges less than P 1 and P 2 taken cumulatively.

We now see how to express the perimeter generating functions. For column-convex polyominoes with one ceiling overlap, the expression is z -2 U 2 . More generally, G hex -that is, the perimeter generating function for all column-convex polyominoes-can be written as and

G hex = U + U z -2 U + U z -2 U z -2 U + . . . = U (1 + z -2 U + z -2 U z -2 U + . . .) = U 1 -z -2 U . Therefore U = G hex 1+z -2 G hex . Let µ -= - (1 -y 2 )(1 -z 2 ) 2(1 -y 2 z 2 ) , µ + = (1 + y 2 )(1 + z 2 ) 2(1 -y 2 z 2 ) , (25)
V = N x 2 1 + x 2 µ 2 - , 1 + µ -, yz . (26)
Recalling that U (x, y, z) = G sq+ (x, z -2 , z 2 , yz), we now go back to relation ( 24) and we substitute z -2 for a, z 2 for b 0 , and yz for y. We quickly find that

(1 -y 2 z 2 )U 1 -y 2 z 2 -(z -2 + z 2 -1)U = V,
which, together with the relation between U and G hex , gives

G hex = 1 -y 2 z 2 1 -y 2 -z 2   2 1 + y 2 + z 2 + (1 -y 2 -z 2 ) 1 -2V 1-y 2 z 2 -1   . (27)
Next we combine (26) with (16), obtaining

(1 + x 2 µ 2 -) 1 - 2V 1 -y 2 z 2 4 -(1 + x 2 + 2x 2 µ -µ + ) 1 - 2V 1 -y 2 z 2 2 + x 2 µ 2 + = 0, (28)
where µ -and µ + are given by (25). Now follows the long and tiring, but unavoidable task of solving equation ( 28). Once we are finished, we embed the formula for 1 -1-y 2 z 2 into (27). This yields the following theorem. Theorem 3 The perimeter generating function for column-convex polyominoes on the honeycomb lattice is given by

G hex (x, y, z) = 1 -y 2 z 2 1 -y 2 -z 2 •                2 1 + y 2 + z 2 + (1 -y 2 -z 2 ) 2+x 2 1+ (y 2 -z 2 ) 2 (1-y 2 z 2 ) 2 +2 √ ∆ 4+x 2 (1-y 2 ) 2 (1-z 2 ) 2 (1-y 2 z 2 ) 2 -1                , (29)
where

∆ = 1 -2x 2 y 2 (1 + z 2 ) 2 + (1 + y 2 ) 2 z 2 (1 -y 2 z 2 ) 2 + x 4 (y 2 -z 2 ) 2 (1 -y 2 z 2 ) 2 .
If we set y = z, the formula for G hex becomes much simpler.

Corollary 1 We have

G hex (x, y, y) = 1 -y 4 1 -2y 2       2 1 + 2y 2 + (1 -2y 2 ) 2+x 2 +2 √ δ 4+x 2 1-y 2 1+y 2 2 -1       , where δ = 1 - 4x 2 y 2 (1 -y 2 ) 2 .
In the case of the generating function G sq (x, y), the two square roots can be written in two ways: separately, as in [START_REF] Lin | Perimeter generating function for row-convex polygons on the rectangular lattice[END_REF], and one inside the other, as in [START_REF] Temperley | Combinatorial problems suggested by the statistical mechanics of domains and of rubber-like molecules[END_REF]. However, I think that the formulae for G hex (x, y, z) and G hex (x, y, y) cannot be written in a form such that two square roots of rational functions stand separately.

In Maple, there is a command (called mtaylor) for computing multivariate series. Now, with our formula for G hex (x, y, z), mtaylor works all right. By contrast, with Lin and Wu's [START_REF] Lin | Unidirectional-convex polygons on the honeycomb lattice[END_REF] formula for G hex (x, y, z), mtaylor arrives at an impasse. This happens because the denominator of their formula involves a factor D = y 2 + z 2 + . . ., which is a polynomial with no constant term.

Appendix

A referee has rightly remarked that we should prove (and not just believe in) the equivalence between the formulae for G hex given in this paper and in Lin and Wu's paper [START_REF] Lin | Unidirectional-convex polygons on the honeycomb lattice[END_REF]. Hence, we started from Lin and Wu's formula, which reads

G hex (x, y, z) = 1 -y 2 z 2 4D a + b √ S + (c + d √ S) √ T 2(1 + y 2 z 2 ) + x 2 (1 -y 2 )(1 -z 2 ) , (30)
where a = 1 + 4(y 2 + z 2 ) + 3y 4 + 4y 2 z 2 + 3z 4 -8y 2 z 2 (y 2 + z 2 ) -6y 2 z 2 (y 4 + z 4 ) -11y 4 z 4 + 4y 4 z 4 (y 2 + z 2 ) + 3y By appropriately squaring two times, from (30) we got a degree-four algebraic equation. We factored that equation (at the price of employing pretty much RAM), and we removed the redundant factors. The result was a sensibly shorter degree-four algebraic equation, still satisfied by Lin and Wu's expression (30). Let this latter degree-four algebraic equation be numbered (A). Next, we wanted to know whether equation (A) is satisfied by our expression (29), too. Much to our relief, the answer was yes. However, equation (A) has four solutions. To show that (29) and (30) are one and the same solution of (A), we computed all four solutions of (A). In the case x = y = z, those four solutions have power series expansions 29) and (30) both begin with a sixth-order term. (This must be so. On the hexagonal lattice, the one-celled polyomino has perimeter 6.) Hence, (29) and (30) are both equal to that solution of (A) which gave us the series x 6 + 3x 10 + 2x 12 + . . . . That is to say, our expression (29) and Lin and Wu's expression (30) are equal to one another.

Fig. 1 :

 1 Fig. 1: (a) Square lattice and (b) hexagonal lattice.

Fig. 2 :

 2 Fig. 2: Column-convex polyominoes on (a) the square lattice and (b) the hexagonal lattice.

Fig. 3 :

 3 Fig. 3: A tapo.

Fig. 4 :

 4 Fig. 4: A stapo.

Fig. 5 :

 5 Fig. 5: Under the bijection ϕ, the stapo of Fig. 4 is mapped into this wall polyomino.

Fig. 6 :

 6 Fig.6: The bijections used in establishing equation[START_REF] Feretić | A new way of counting the column-convex polyominoes by perimeter[END_REF].

x 1 -

 1 xd , 0, e, y) and O( x 1-xe 2 , 0, e, y) = N (x, e, y). Hence, O(x, d, e, y) = O x 1 + x(e 2 -d) -xe 2 , 0, e, y

Fig. 7 :

 7 Fig. 7: The low-to-high conversion.

  a 0 , a, b 0 , d, y) = P a wall polyomino of odd width x No. of odd columns of P • a No. of high single repeats of P 0 •a No. of chimneys of P • b No. of low single repeats of P 0 •d No. of OEO repeats of P y vertical perimeter of P .

Fig. 8 :

 8 Fig. 8: Making of chimneys.

R

  (x, a 0 , a, b 0 , b, d, y) = P a wall polyomino of odd width x No. of odd columns of P •a No. of high single repeats of P 0 • a No. of chimneys of P •b No. of low single repeats of P 0 • b No. of wells of P •d No. of OEO repeats of P • y vertical perimeter of P .

Fig. 9 :

 9 Fig. 9: Making of wells, with the freedom to overdraw.

Fig. 10 :

 10 Fig. 10: A column-convex polyomino becomes similar to a piece of a brick wall.

Fig. 11 :

 11 Fig. 11: Effects of the shifts on the vertical perimeter. At every column-column interface there is an arrow, labelled with the local balance of vertical half-edges.

Fig. 12 :

 12 Fig. 12: Twin polyominoes.

Fig. 13 :

 13 Fig. 13: The ceiling overlap divides P into P1 and P2.

  4 z 4 (y 2 + z 2 ) 2 + x 2 [y 2 + z 2 -4y 2 z 2 (y 2 + z 2 ) -y 6 -z 6+ y 2 z 2 (y 6 + z 6 ) + 5y 4 z 4 (y 2 + z 2 )], b = (1 -y 2 z 2 )[1 -(y 2 + z 2 ) 2 ], c = -(1 -y 2 z 2 )[1 + 4(y 2 + z 2 ) + 3y 4 + 7y 2 z 2 + 3z 4 + 4y 2 z 2 (y 2 + z 2 ) + y 2 z 2 (y 2 + z 2 ) 2 + x 2 (y 2 + z 2 )(1 -y 4 -z 4 )], d = -1 + y 4 + y 2 z 2 + z 4 -y 2 z 2 (y 2 + z 2 ) 2 , D = (y 2 + z 2 )[1 + 2(y 2 + z 2 ) + y 4 + z 4 -4y 2 z 2 (y 2 + z 2 ) -y 2 z 2 (2y 4 + 3y 2 z 2 + 2z 4 ) + 2y 4 z 4 (y 2 + z 2 ) + y 4 z 4 (y 2 + z 2 ) 2 ] + x 2 y 2 z 2 [1 -(y 2 + z 2 ) 2 (1 -y 2 z 2 )], S = 1 -2(x 2 y 2 + y 2 z 2 + x 2 z 2 ) -8x 2 y 2 z 2 + x 4 y 4 + y 4 z 4 + x 4 z 4 -2x 2 y 2 z 2 (x 2 + y 2 + z 2 ), T = 2(1 -y 2 z 2 ) 2 + 2x 2 [2 -(y 2 + z 2 )(1 + y 2 z 2 ) + 2y 4 z 4 ] + x 4 (1 -y 2 ) 2 (1 -z 2 ) 2 + 2(1 -y 2 z 2 ) √ S.

(ii) In the area of polyominoes there also exist stack polyominoes, close relatives of Ferrers diagrams. Hence, it should be stressed that "stapo" could be, but is not an abbreviation for "stack polyomino".

Acknowledgements

I would like to thank the referees for several helpful comments, and Professor Dragutin Svrtan both for further comments and for kind help in computer matters.

Also, T = G sq+ (1 + y 2 + y 4 + y 6 + . . .) = Gsq+ 1-y 2 , so that (1 -y 2 )T = G sq+ . Therefore

Substitution of this into (22) yields

with λ -still given by (23).

Coping with the honeycomb lattice

Next, since our business is expanding again, we employ a new variable z. That is to say, we pass to the generating function G sq+ (x, a, b 0 , yz), where we think of y and z as the variables counting the first halves and second halves of vertical edges, respectively. Here, "the first half" actually means the half that would be first if the boundary of a column-convex polyomino had anticlockwise orientation.

Then we subject every column-convex polyomino P to a series of half-a-unit downward shifts. First we shift all of P except for the leftmost column of P . Second we shift all of the first-shifted object, except for the leftmost column of that object. Third we shift all of the second-shifted object, except for the leftmost column of that object. And so on. In the last shift, the shifted object has only one column.

Through this series of shifts, a column-convex polyomino becomes similar to a piece of a brick wall. See Fig. 10.

To count those (so to speak) pieces of brick walls, we introduce a generating function U = U (x, y, z). The definition is U (x, y, z) = P a piece of a brick wall

x horizontal perimeter of P •y No. of first halves of vertical edges of P • z No. of second halves of vertical edges of P .

(The meaning of "the first half" and "the second half" is illustrated in Fig. 11.) Of course, our aim is to express U by means of G sq+ . So, how do the shifts influence the vertical perimeter? By taking a closer look at Fig. 11, we find out the following.

A shift has influence in just two cases. Case 1: When the overlap between the moving columns and the still columns is a rise, we lose two z-edges. Case 2: When the overlap just mentioned is a weak fall, we gain two z-edges.

Therefore, we have U (x, y, z) = G sq+ (x, z -2 , z 2 , yz).

Next, every piece of a brick wall has something like a twin; the twin is a column-convex polyomino on the honeycomb lattice. See Fig. 12. As regards the three perimeter counts (x-edges, y-edges, z-edges), between the twins there is no difference.


Guy Kortsarz

A lower bound for approximating the grundy number

Keywords: Grundy, number, coloring, approximation, hardness

The grundy number of a graph is the maximum number of colors used by on-line first-fit coloring, under the worst order of arrival of vertices. The grundy number problem is to find this ordering. We prove that there is a constant c > 1 so that approximating the grundy number problem within c is not possible, unless N P ⊆ RP

Introduction

In first-fit coloring, we color the vertices with positive integers. The vertices arrive on-line, and we color the next vertex v by the minimum number not appearing in its neighborhood. The grundy number of a graph is the maximum possible number of colors used by on-line first-fit coloring, under the worst order of arrival of vertices. The grundy number problem is to find this worst ordering. The problem was extensively studied, see e.g., [START_REF] Christen | Some perfect coloring properties of graphs[END_REF]; [START_REF] Simmons | On the ochromatic number of a graph[END_REF]; [START_REF] Erdős | On the equality of the grundy and ochromatic numbers of a graph[END_REF]; [START_REF] Hoffman | Greedy coloring and the grundy chromatic number of the hypercube[END_REF]; [START_REF] Zaker | The grundy chromatic number of the complement of bipartite graphs[END_REF][START_REF] Zaker | Results on the grundy chromatic number of graphs[END_REF]. The first-fit coloring is important in practice and is extensively studied as well, see, e.g., [START_REF] Gyarfas | On-line and first-fit coloring of graphs[END_REF]; [START_REF] Kierstead | On-line coloring and recursive graph theory[END_REF]. In [START_REF] Kierstead | The linearity of first-fit coloring of interval graphs[END_REF] the author studies the grundy number problem on interval graphs and establishes that the grundy number differs from the obvious lower bound of maximum clique size by at most some multiplicative universal constant. An algorithm solving this problem on trees is given in [START_REF] Hedetniemi | A linear algorithm for the grundy (coloring) number of a tree[END_REF] and on partial k-trees in [START_REF] Telle | Algorithms for vertex partitioning problems on partial k-trees[END_REF]. The problem was shown to be N P -complete on directed graphs [START_REF] Christen | Some perfect coloring properties of graphs[END_REF]. The NP-hardness for the undirected case was harder to prove. Indeed, in the book [START_REF] Jensen | Graph Coloring Problems[END_REF] proving NP-hardness for the grundy number problem is posed as an open problem. A proof of the NP-hardness of the undirected version was established slightly after that [START_REF] Goyal | NP-completeness of undirected grundy numbering and related problems[END_REF]. Prior to this paper, there was no hardness of approximation result for the problem.

Definitions

An independent set in G(V, E) is a subset V ′ ⊆ V so that no two vertices in V ′ are neighbors. A dominating set is a subset V ′ ⊆ V so that V ′ ∪ N (V ′ ) = V with N (V ′ ) the vertices not in V ′ with at least one neighbor in V ′ . An independent set is (inclusion) maximal if it is also a dominating set of the 1365-8050 c 2007 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France graph. A set U dominates Z if every vertex z ∈ Z either belongs to U or has at least one neighbor in U . A grundy coloring is a disjoint partition V = C 1 ∪ C 2 . . . ∪ C k of V into independent sets so that every v ∈ C j has at least one neighbor in every C i , i < j. Thus, C i should be a maximal independent set in the graph induced by j≥i C j . The C i sets are also called the color-classes of the partition. The goal is to maximize k, the number of color-classes. The largest possible k is the grundy number of the graph.

Related problems

A natural idea for approximating the grundy number problem is trying to find a small size maximal independent set, removing the vertices of this independent set, and iterating. Unfortunately, in [START_REF] Halldórsson | Approximating the minimum maximal independence number[END_REF] it is shown that for every ǫ > 0 approximating the size of the minimum size maximal independent set within n 1-ǫ is N P -hard. In fact, the author is not aware of any non-trivial approximation published for the grundy number problem. Conversely, one may hope that [START_REF] Halldórsson | Approximating the minimum maximal independence number[END_REF] could be used to derive a strong lower bound. However, if a graph has a large grundy number, it does not necessarily imply that all maximal independent sets are small. For example, it might be the case that |C 1 | = n/2 and, |C j | = 2 for every j ≥ 2 and so the grundy number equals Ω(n) while there exists a a maximal independent set of size Ω(n). The grundy number problem is thus more related to the following problem: given a size bound x, find an independent set I of size at most x, and maximize |N (I)|. It is possible to show that this problem cannot be approximated within some constant c > 1, unless P = N P (detail omitted). Still, it seems hard to deduce from that any hardness result for the grundy number problem. This is as a large grundy number requires a large collection of small independent sets with many neighbors each.

Other two maximization partitioning problems that have some relation to the grundy number problem are the achromatic number problem and the complete coloring problem (cf. [START_REF] Edwards | The harmonious chromatic number and the achromatic number[END_REF] for a survey). The achromatic number problem is to partition the vertex set of a graph G(V, E) to maximum number k of independent sets V = k i=1 C i so that every two independent sets in the partition share an edge (for every two independent sets C i , C j in the partition there exist a vertex v ∈ C i and a vertex u ∈ C j so that (u, v) ∈ E). The complete partition problem is defined in the same way as the achromatic number problem except that the C i sets need not be independent sets and can be any arbitrary subsets of V .

Even though the grundy number problem seems more important in practice than the achromatic and complete partition problems (because of its tight relation to first-fit coloring), an Ω( √ log n) lower bound on the approximability of the two latter problems is known [START_REF] Kortsarz | Complete partitions of graphs[END_REF], but no lower bound for approximating the grundy number problem was known before this paper. It may be that grundy number problem is harder to analyze than the two other problems, because of its more restricted nature: Every vertex in C j j > i has to be dominated by C i (in the other two problems, C i , C j need to share only one edge). This poses a difficulty in the reduction, in particular for the part of the reduction of a yes-instance. The construction of [START_REF] Kortsarz | Complete partitions of graphs[END_REF] does not seem to work. The construction here is different. The technical nature of the proofs is also different.

Background

We now describe a construction from [START_REF] Feige | Approximating the domatic number[END_REF]. See also [START_REF] Lund | On the hardness of approximating minimization problems[END_REF]; [START_REF] Feige | A threshold of ln n for approximating set cover[END_REF]; [START_REF] Kortsarz | Approximating the achromatic number problem on bipartite graphs[END_REF] for constructions using similar tools.

Let I n be the set of 5-regular, simple graphs I = (V(I), E(I)) with V = {1, 2, . . . , n}. We say that a graph I ∈ I n is ǫ-non-3-colorable if in every 3-coloring of the vertices of I at most (1 -ǫ)|E(I)| edges of I are properly colored.

The maximum legal edge 3-coloring problem is given some graph G, to legally color the vertices of V and to maximize the number of edges that are legally colored. The following theorem states that given any N P -complete instance, then there exists a universal constant ǫ and a polynomial time reduction to an instance of the maximum legal edge 3-coloring problem so that in a yes instance, the graph is 3-colorable and in a no instance at most 1 -ǫ fraction of the edges are 3-colorable.

Theorem 1. 1 Feige et al. (2002) There is an ǫ > 0 such that the following holds. Let L ⊆ {0, 1} * be a language in NP. Then, there is a polynomial computable function f : {0, 1} * → I n such that for all

x ∈ {0, 1} * • if x ∈ L, then f (x) is 3-colorable; • if x ∈ L, then f (x) is ǫ-non-3-colorable.
The proof of the theorem in [START_REF] Feige | Approximating the domatic number[END_REF] is based on an earlier reduction of Petrank from an arbitrary N P language to an instance of 3-SAT (see [START_REF] Petrank | The hardness of approximation: Gap location[END_REF]). The advantage of reducing to maximum legal edge coloring is that by permuting the colors, if one legal coloring exists, many distinct colorings can be derived.

Notation 1.2 Throughout the paper, n = |V| denotes the number of vertices in I.

Consider the following two-prover protocol.

Input: I ∈ I n .
Verifier: Chooses a v ∈ V(I) at random. Chooses a random pair of edges (e, e ′ ), both incident on v.

Sends e to the Prover I and e ′ to Prover II.

Prover I: Sends a proper 3-coloring χ of the two vertices of e to the verifier.

Prover II: Sends a proper 3-coloring χ ′ (e ′ ) to the verifier.

Verifier: Accepts iff χ(v) = χ ′ (v).
Proposition 1.3 [START_REF] Kortsarz | Complete partitions of graphs[END_REF] Let the maximum number of edges properly colored in any 3coloring of I be (1 -ǫ)|E(I)|. Let Π be a strategy for the provers that makes the verifier accept with the highest probability. Then, under Π, Pr[Verifier accepts] = 1 -ǫ.

We briefly explain why does the proposition hold. In case of a yes instance, the two provers may use the same legal 3-coloring deriving a probability 1 of acceptance by the verifier. Now, given a no instance, every prover has some fixed strategy (namely choice of colors) over the edges. This is as the provers are deterministic. By Theorem 1.1, the colorings of the two provers differ on an ǫ fraction of the edges. Since the graph is regular, it follows from the method used that the selected edge is random as well. Hence with probability at least ǫ, the random edge e selected is one of those edges that have two different colorings under the strategy of the provers. For such an edge e, the verifier rejects. Hence, the verifier rejects with probability at least ǫ.

Let A e denote some question to the first prover (in our case a question is simply the edge e to be colored) and B e ′ a question to the second prover. If there is non-zero probability that (A e , B e ′ ) are asked together, namely, if e, e ′ share a vertex, then we call (A e , B e ′ ) a query.

Consider the following ℓ-fold parallel repetition of the protocol above.

Input: I ∈ I n .

Verifier: Sends v 1 , v 2 , . . . , v ℓ ∈ V(I) at random. For each i = 1, 2, . . . , ℓ, chooses a random pair (e i , e ′ i ) of edges both incident on v i . Sends e 1 , e 2 , . . . , e ℓ to the first prover and e ′ 1 , e ′ 2 , . . . , e ′ ℓ to the second prover.

Prover I: Chooses χ 1 , χ 2 , . . . , χ ℓ to the verifier, where χ i (e i ) is a proper coloring of e i .

Prover II:

Sends χ ′ 1 , χ ′ 2 , . . . , χ ′ ℓ to the verifier, where χ i (e ′ i ) is a proper coloring of e ′ i . Verifier: Accepts iff for all i = 1, 2, . . . , ℓ, χ i (v i ) = χ ′ i (v i ).
Theorem 1.4 (Raz's parallel repetition theorem Raz ( 1998)) If we perform ℓ parallel repetitions of a one-round two-prover protocol with probability of acceptance ǫ, and accept if and only if all ℓ runs lead to acceptance, then the probability of acceptance is at most 2 -cℓ where c > 0 is a constant that depends only on ǫ.

Corollary 1.5 Let the maximum number of properly colored edges in any 3-coloring of I be (1 -ǫ)|E(I)| (ǫ > 0). Then, there exists a constant c = c(ǫ) > 0 such that the following holds for all ℓ. Let Π be a strategy for the provers in the above protocol that makes the verifier accept with the highest probability. Then, under Π, Pr[Verifier accepts] ≤ 2 -cℓ .

From now on, we will use c for the constant associated in the above corollary with the constant ǫ.

Remark: In this paper ℓ will equal some large enough universal constant.

A query for the parallel repetition protocol is defined as above; namely, it is two tuples of ℓ questions each that have positive probability of being sent together. The task of determining the best strategy for the provers in the parallel protocol is now posed in graph theoretic terms as follows. We construct a bipartite graph MRG(I) = (U 1 , U 2 , E). The set U 1 = A e is decomposed to "question clusters" {A e }. Intuitively, every A e is a possible question (tuple of ℓ edges) for the first prover. The set U 2 = B e ′ is a union of sets B e ′ . Every B e ′ corresponds to a question for the second prover. The actual vertices in MRG(I) are all the proper answers (namely, legal colorings) for every A e and B e ′ . We call these vertices answer-vertices. If (A e , B e ′ ) is not a query no x ∈ A e and y ∈ B e ′ share an edge in M RG(I). If (A e , B e ′ ) is a query, then answer-vertices x ∈ A and y ∈ B are adjacent in MRG(I) (or (x, y) ∈ E) iff they are consistent, namely assign the same color to the shared vertex in every edge in the ℓ-tuple. Formally:

Definition 1.1 (min-rep-Graph Kortsarz (2001)) Given a graph I ∈ I n , the bipartite graph MRG(I) = (U 1 , U 2 , E), is defined as follows. U 1 and U 2 consist of tuples e 1 , e 2 , . . . , e ℓ , χ 1 , χ 2 , . . . , χ ℓ ,
where for i = 1, 2, . . . , ℓ, e i ∈ E(I) and χ i (e i ) is a proper coloring of e i . The edges of MRG(I) will be labeled by elements of V ℓ , and we will use

(u, u ′ , v) to denote the edge between u ∈ U 1 and u ′ ∈ U 2 with label v ∈ V(I) ℓ . Let E v be the edges labeled v. E v = {( e, χ , e ′ , χ ′ , v) : e, χ ∈ U 1 and e ′ , χ ′ ∈ U 2 and for i = 1, 2, . . . , ℓ, v i ∈ e i , e ′ i and χ i (v i ) = χ ′ i (v i )}.
Finally, the edge set of MRG(I) is v∈V(I) ℓ E v .

Note: In the graph above, and in those we shall encounter below, we allow parallel edges, but different edges connecting the same two vertices have different labels.

The vertices of U 1 can be partitioned into sets (A e : e ∈ E(I) ℓ ), where A e consists of vertices of the form e, χ . Similarly, U 2 can be partitioned into sets (B e ′ : e ′ ∈ E(I) ℓ ). Note that |A e | = |B e ′ | = 6 ℓ , and there are precisely q = |E(I) ℓ | = ( 52 ) ℓ |V(I)| ℓ parts in each partition (recall that the graph is 5-regular). Definition 1.2 (Super-graph) The supergraph SG(I) of the protocol has vertex set {A e } and {B e ′ }. A pair f = (A e , B e ′ ) is a superedge iff it is a query (namely, for i = 1, 2, . . . , ℓ, e i and e ′ i have a common vertex).

Remark: To avoid confusion, we use f for superedges and e for edge-tuples of size ℓ of E(I).

The number of superedges is denoted by h. The supergraph is d-regular with d = 2 ℓ • 5 ℓ = 10 ℓ ; indeed, consider a supervertex A e and count its neighbors in SG(I). A neighbor B e ′ of A e has the same v tuple. The tuple v can be chosen in 2 ℓ ways. Once this tuple is chosen, for defining B e , in every coordinate, there are 5 ways to choose edges touching the respective vertex in v vertex (this follows as the graph is 5-regular). This implies that d = 10 ℓ . Also,

h = q • d = (25 • n) ℓ . Definition 1.3 Let S ⊆ U 1 ∪ U 2 . We say that a superedge f = (A e , B e ′ ) is min-rep covered by S if there exist a ∈ A e ∩ S and b ∈ B e ′ ∩ S that are adjacent in MRG(I) (or (a, b) ∈ E).
A set S is a min-rep cover if it covers all the superedges.

We are now ready to derive the key properties of MRG(I) as established by [START_REF] Feige | Approximating the domatic number[END_REF].

Lemma 1.6 (Main Lemma) We have the following properties depending on whether I is 3-colorable or whether I is ǫ-non-3-colorable. This graph is a union of vertex-disjoint complete bipartite graphs.

• If I ∈ I n is 3-colorable, then V (MRG(I)) can

The construction

Like [START_REF] Kortsarz | Complete partitions of graphs[END_REF] we derive the reduction by modifying MRG(I). However, the modification is different.

The intermediate random graph G(I):

The intermediate graph G(I) is a random bipartite graph with vertex sets Ṽ1 and Ṽ2 similar to that of [START_REF] Lund | On the hardness of approximating minimization problems[END_REF]; Feige (1998); [START_REF] Feige | Approximating the domatic number[END_REF].

The first vertex set Ṽ1 = U 1 ∪ U 2 will, in fact, be the same as V (MRG(I)). We call the vertices of Ṽ1 answer-vertices, and as before, we partition it into 2q clusters (A e , B e ′ : e, e ′ ∈ E(I) ℓ ) each, with 6 ℓ answer-vertices. The other vertex set Ṽ2 has one ground set M f of m ≥ n 2ℓ vertices for each superedge f of SG(I). In addition, we assume that 6 ℓ divides m (we increase m to the first integer larger than n 2•ℓ so that 6 ℓ |m). The set Ṽ2 has h

• m = (25 • n) ℓ • m vertices.
We now describe how the edges are placed in G(I). The edges connecting the ground set M f to the answer-vertices in Ṽ1 are determined by using a random process. This process is run independently for each superedge f of SG(I). Consider a superedge f = (A e , B e ′ , v) of SG(I). The vertices in the ground set M f have neighbors only in A e and B e ′ .

The neighbors in M f of a class C ⊆ A e and its matching class H f (C) ⊆ B e ′ are defined together and complement each other (see [START_REF] Lund | On the hardness of approximating minimization problems[END_REF] for the first time this idea was used). Choose a random half M f (C) of M f . Join all the answer-vertices of C to all the vertices of M f (C). Join every answer-vertex of

H f (C) to the complementary half M f ( C) = M f \ M f (C).
Remark: The coins used to determine the neighbors in ground set

M f of C, H f (C) and C ′ , H f (C ′ ), C = C ′ are completely independent
Note that the answer-vertices in the same class will have the same neighbors in M f . A vertex v 2 ∈ M f is connected to either all the answer-vertices in a class or to none of them. See an example in Figure 1.4. 1. To get V1 duplicate every vertex in v ∈ Ṽ1 | Ṽ2 |/6 ℓ times (to duplicate a vertex v i times is to replace v by i copies of v all with the same neighbors as v). Here we use the fact that 6 ℓ divides m, and so | Ṽ2 |/6 ℓ is an integer. After the modification, the size of every A e B e ′ exactly equals | Ṽ2 |.

2. V2 ← Ṽ2 , namely, Ṽ2 is not changed 3. Clique A e , B e ′ : For every e and A e add an edge between all pairs u, v ∈ A e . Similarly, for for every e ′ and B e ′ and add an edge between all pairs z, w ∈ B e ′ .

4. In addition, clique the vertices of V2 , namely, add an edge between every two vertices of V2 .

Since the number of variables is large, the following table gives a summary of symbols, their sizes, and their meaning.

Intuition and technical claims

Trapdoor: a large grundy number of a yes-instance

The construction is best explained via a yes-instance. Intuitively, in a yes-instance we can select | V2 | = | Ṽ2 | subsets of V1 that are dominating sets of V2 . These dominating sets form the first half of the color-

Symbol Description Size I = (V(I), E(I))
The graph with the 3-coloring gap

|V (I)| = n. ℓ
The number of parallel repetitions ℓ is a large constant.

MRG(I) = (U 1 , U 2 , E) The min-rep graph |U i | = q • 6 ℓ = (15 • n) ℓ . q
The number of questions for each prover q = n ℓ • 5 ℓ /2 ℓ .

SG(I)

The supergraph with vertex set {A e }, {B e ′ } |{A e }| = |{B e ′ }| = q. d

The graph SG(I) is d-regular d = 10 ℓ . h

The number of superedges

h = d • q = (25 • n) ℓ . G = ( Ṽ1 , Ṽ2 ) Intermediate random graph. Ṽ1 = U 1 ∪ U 2 | Ṽ1 | = 2 • (15 • n) ℓ . M f A ground set |M f | = m ≥ n 2•ℓ , 6 ℓ \m Ṽ2 = V2 Ṽ2 = V2 = f is a superedge M f . | Ṽ2 | = | V2 | = h • m Ĝ = ( V1 , V2 )
Duplications of Ṽ1 and cliqueing Ṽ2 , etc. We now show that the above is a legal partition. We first show that every S i is a dominating set of V2 . Observe that every S i contain a min-rep cover of every superedge f = (A e , B e ′ ). Namely, there are a ∈ S i ∩ A e and b ∈ S i ∩ B e ′ so that (a, b) ∈ E.

|A e | = |B e ′ | = | V2 |.
It follows that a, b are adjacent to complementing halves of the ground set M f , and thus are a dominating set of M f . As this is true for every superedge, S i is a dominating set of V2 .

In addition, each S i is an independent set; Recall that for every e,e ′ A e , B e ′ are cliques, but other than that there are no edges inside V1 . As no S i color-class contains two or more vertices of the same A e or the same B e ′ , the claim follows.

Finally, we show that every vertex v in some S i has a neighbor in every S j , for j < i. Say without loss of generality that v ∈ A e . Observe that S j contains exactly one other vertex, say u, from A e . In addition, by construction A e is a clique. The required claim follows, and we have shown that the above is a legal size 2 • | V2 | partition. ✷

A technical claim for a no-instance: lucky pairs

For the rest of the paper we assume that I is a no-instance. Let Γ(G) be the optimal grundy number for I.

We later define a universal constant ρ (it will turn out later that ρ = 3 is enough for our purposes) and another universal constant µ = µ(ρ) that depends only on ρ.

In order to show that our reduction preserves the gap between a yes and a no-instance of I = (V(I), E(I)) we need to show that for a no-instance the grundy number cannot be arbitrarily close to 2 • | V2 |. More precisely, that there exists some universal constant µ so that opt ≤ (2 -µ)|| V2 |. For the sake of contradiction for the rest of the paper we assume that for every universal constant µ,

Γ(G) = {C 1 , C 2 , . . . , C opt } with opt ≥ (2 -µ)|| V2 | (opt is the number of color-classes in Γ(G)). Assumption 2.1 I is a no-instance and opt ≥ (2 -µ)|| V2 |
For the rest of the section, let f = (A e , B e ′ ) be a superedge.

Intuitively, our aim is to show that the color-classes for a no-instance must be "large." Hence, any grundy partition must have small size. The no-instance cannot "coordinate efforts" by using consistent answer-vertices, and so the connection between the answer-vertices and the M f ground sets are essentially random. Intuitively we show that for any superedge f = (A e , B e ′ ) a subset C ′ ⊆ V1 with only few vertices of A e ∪ B e ′ cannot dominate a "large" subset M ′ ⊆ M f unless C ′ min-rep covers f . We now define these terms precisely. Let M ′ ⊆ M f and C ′ ⊆ V1 . Let ρ be some universal constant. Let µ be a universal constant that depends only on ρ. Let DS(C ′ , M ′ ) be the events that C ′ is a dominating set of M ′ ; namely, each vertex in M ′ has a neighbor in C ′ .

Definition 2.1 Lucky Pairs

The pair (C ′ , M ′ ) is a (ρ, µ)-lucky pair (or just lucky pair for short) if the following properties hold:

1. |M ′ | ≥ (1 -4 • µ)m 2. C ′ does not min-rep covers f (namely, there are no a ∈ C ′ ∩ A e , b ∈ C ′ ∩ B e ′ so that (a, b) ∈ E). 3. DS(C ′ , M ′ ) holds 4. |(A e ∪ B e ′ )| ≤ 8 • ρ.
We later see that with high probability for any I (I can be a yes or a no-instance) there are no lucky pairs in the graph . Further, we shall show that if no lucky pairs exist, a no-instance must have a small size grundy number.

First, compute the probability that a given fixed triplet f , M ′ , C ′ as in Definition 2.1 is a lucky pair.

Claim 2.2 P r(DS(C ′ , M ′ )) ≤ exp(-Ω(m/exp(Θ(ρ)))).

Proof: Since C ′ does not min-rep covers f , it follows that every answer-vertex in C ′ ∩ (A e ∪ B e ′ ) is connected to a random half of ground set M f (recall that only A e ∪ B e ′ answer-vertices are connected to M f ). The neighbors in M f of every pair of x 1 , x 2 ∈ C ′ are completely independent over the probability space.

The probability that v 2 ∈ M ′ is not dominated by C ′ (does not have a neighbor in [START_REF] Motwani | Randomized Algorithms[END_REF]) we get that: P r(X = 0) = P r(X < 1) = P r(X < (1 -δ)ν) < exp(-νδ 2 /2) = 1/exp(Ω(m/exp(Θ(ρ)))).

C ′ ) is 1/2 8ρ . The expected number of elements in M ′ not dominated by C ′ (elements having no neighbor in C ′ ) is ν = |M ′ |/2 8ρ . Let X be the number of not dominated by C ′ elements in M ′ . Let δ = 1 -1/ν. Using the Chernoff bound (cf.,

✷

We now upper bound the probability that there exists some lucky pair. Namely, we have computed the required probability for a fix 3-tuple f and M ′ and C ′ . We now bound the probability that such an event occurs over all possible 3-tuples.

Claim 2.3 For every universal constant ρ, we can choose µ to be a small enough universal constant depending on ρ so that the probability that there exists a lucky pair is exp(-Ω(m)).

Proof: Recall that we started with the intermediate random graph G(I) and then duplicate every vertex in Ṽ1 | V2 |/6 ℓ times to get V1 . If we remove duplicates from C ′ , the event DS(C ′ , M ′ ) is not affected (the removed copies dominate the same vertex set as the copy that is not discarded). Thus, we may assume that C ′ ⊆ Ṽ1 , and the probability of DS(C ′ , M ′ ) can be computed over G, the graph before the duplications.

We use the union bound, namely, bound the probability over all 3-tuples by the sum of probabilities for every individual tuple. By symmetry, this equals the number of 3-tuples, times the probability derived in Claim 2.2.

Hence, we next bound from above the number of f , C ′ , M ′ triplets over G.

1. The number of

C ′ ⊂ Ṽ1 sets: Recall that q = |E(I) ℓ | = ( 5 2 ) ℓ |V(I)| ℓ . The number of vertices in G is 2 • q • 6 ℓ = 2 • (15 • n) ℓ = O(15 ℓ • n ℓ ).
The number of subsets C ′ of Ṽ1 is thus exp(Θ(15 ℓ • n ℓ )).

There are at most

h = d • q = (25 • n) ℓ superedges 3. The number of M ′ sets: The number of subsets of size (1 -4 • µ)m of M f is bounded as follows: We use, m αm ≤ 2 mH(α)
with H(α) is the binary entropy function that goes to 0 when α goes to 0 (see [START_REF] Cormen | Introduction to algorithms[END_REF]). Thus, the number of (1 -4 • µ)m size subsets of of M f is bounded by 4µ) .

m 4 • µm ≤ 2 mH(
Multiplying the four upper bounds, we get a bound of at most

exp(Θ(15 ℓ • n ℓ )) • 25 ℓ • n ℓ • 2 mH(4µ)
3-tuples. Thus, the probability that there exist any lucky pair is at most

exp(Θ((15n) ℓ )) • (25 • n) ℓ • 2 mH(4µ) exp(Ω(m/exp(Θ(ρ)))) .
Since m ≥ n 2ℓ , taking µ small enough, the above probability is exponentially small in m. The claim follows. ✷ Claim 2.3 shows that a subset C ′ has to be "large" in order to cover "many" vertices of M f . This is used in the next section to show that a grundy number for a no-instance cannot be too large.

Analysis of the reduction

We based the analysis on the following lemma: Lemma 3.1 Under Assumption 2.1, a lucky pair must exist.

First, note that once Lemma 3.1 is proved, we are done: The rest of the paper is devoted to proving Lemma 3.1.

The first thing we need to do is identify color-classes C i in Γ(G) that are fully contained in V1 , namely, do not contain V2 vertices (they will play the role of C ′ from the definition of a lucky pair) followed by many vertices of the same M f set. These vertices will become M ′ . Since C i is before M ′ in the ordering, C i has to be a dominating set of M ′ , and the situation mimics Claim 2.3.

We split its color-classes in Γ(G) into three types:

1. Type 1: Color-classes containing only V1 vertices.

2. Type 2: Color-classes containing only V2 vertices (because V2 is a clique, such a cluster contains a single V2 vertex).

3. Type 3: Color-classes containing at least one vertex of V1 and exactly one vertex of V2 .

Let I i , 1 ≤ i ≤ 3, be the number of color-classes of types 1, 2, 3, respectively. We now look for color-classes not containing V1 vertices. Let i max be the highest index so that C imax contains a V1 vertex (namely, C imax is a type 1 or 3 cluster). Then: The important type 1 color-classes C i will play the role of C ′ in the definition of a lucky pair. However, toward showing the existence of a lucky pair, we need to show that many M f ground sets contribute at least (1 -4µ) vertices to important type 2 color-classes. Let U ⊆ V2 be the set of all V2 vertices appearing in type 2 important color-classes. Exactly one V2 vertex appears in each color-class.

Claim 3.4 If n = |V(I)| is large enough, then i max ≤ (1 + µ)| V2 |. Proof: Let v ∈ V1 ∩ C imax . Note that each C j , j < i max must
Definition 3.2 Let M ′ = M f ∩ U. We say that M f is proper if |M ′ | = |M f ∩ U| ≥ (1 -4µ) • m
Claim 3.7 At least half of the ground sets (namely, h/2 of the ground sets) contribute at least (1 -4 • µ)m elements to U.

Proof: Say that i of the ground sets contribute less than (1 -4 • µ)m to U, and the rest of the h -i ground sets contribute to U more than that. We now bound from above the size of U. Observe that by Corollary 3.6, |U| ≥ | V2 | -2 • µ| V2 |. On the other hand, by the definition of i:

|U| ≤ i(1 -4 • µ)m + (h -i)m. Since (1 -2µ)| V2 | ≤ |U| and h • m = | V2 |, we get that: -2 • µ| V2 | ≤ -4 • µ • i • m. So, i ≤ h/2 and h -i ≥ h/2. Hence, at least h -i ≥ h/2 ground sets contribute more than (1 -4 • µ)m elements to U. ✷
In Claim 2.3, C ′ does not min-rep covers M ′ . We now show that this relation also holds for many important color-classes pairs: C i an important color-class of type 1, and M ′ , with M ′ = M f ∩ U, M f a proper ground set.

Consider important color-class C i of type 1. Call C i problematic if it min-rep covers at least h/4 of the proper superedges (namely, for roughly half of the proper superedges f = (A e , B e ′ ), C i contains at least one pair (a, b) ∈ E, a ∈ A e , b j ∈ B e ′ and (a, b) ∈ M RG(I)). Since I is a no-instance, using Lemma 1.6 we show that the number of problematic C i is small. Claim 3.8 Given a constant µ, we can choose the parallel repetition ℓ to be a large enough universal constant (depending on µ) so that every problematic color-class C i contains at least 2q/µ vertices.

Proof: As C i min-rep covers α = 1/4 > 1/5 fraction of the edges, it follows from Lemma 1.6 that, if we put |C i | ≥ 2qk, then k must satisfy: Proof: We show that if a lucky pair does not exist, then for µ small enough, |C i | ≥ 3q. This is a contradiction: C i has at most one vertex per A e and B e ′ , |C i | ≤ 2q.

1/5 < 32 • k 2 • 2 -cℓ 1/3 .
Let C i be an arbitrary important and non-problematic type 1 color-class. We know from Claim 3.7 that at least h/2 M f contribute to U at least (1 -4 • µ)m vertices. For every f M ′ = M f ∩ U has size |M ′ | ≥ (1-4•µ)m, M ′ ⊆ U. Among those, at least h/2-h/4 are M f so that C i does not min-rep covers f . All these h/4 M ′ sets contain vertices that appear after C i in the partition. Thus, C i is a dominating set of all those M ′ .

Choose ρ = 3. Choose µ to be the appropriate universal constant (that follows by the choice of ρ = 3). Examine the pair C ′ = C i and M ′ = M ′ ( f ) as defined above. The properties we already know are: We now bound from below the size of C i . Every one of the h/4 (or more) proper superedges f not min-rep covered by C i "adds" to C i at least 24 elements of its set A e ∪ B e ′ for a total of 24 • h. However, in this way, every A e and every B e ′ are counted d times. Thus:

1. |M ′ | ≥ (1 -4µ)m.
|C i | ≥ 24 • h 4 • 2d = 3 • q.
This gives the desired contradiction, and hence a lucky pair must exist. ✷

Open problems

It would be interesting to get a super-constant lower bound on the approximability of the grundy number problem. In addition, no nontrivial approximation algorithm for the grundy number problem exists even on bipartite graphs. In the author's opinion, any o(n) approximation is of interest. See [START_REF] Kortsarz | Approximating the achromatic number problem on bipartite graphs[END_REF] for an O(n 4/5 ) approximation algorithm for the achromatic number of bipartite graphs. The hope would be that [START_REF] Kortsarz | Approximating the achromatic number problem on bipartite graphs[END_REF] can be used to a sublinear approximation for grundy number of bipartite graphs. However, there seem to be considerable difficulties involved.

Fig. 1 :

 1 Fig. 1: The graph induced by Ae ∪ B e ′ for ℓ = 1. There are 6 vertices split into 3 classes. Each class has 2 vertices. This graph is a union of vertex-disjoint complete bipartite graphs.

Fig. 2 :

 2 Fig. 2: The sets C and H f (C) have complementing neighbors in M f . In this example ℓ = 1 and m = 8.

Tab. 1 :

 1 Summary of notation classes in the order. The next half of the color-classes after the dominating sets are the vertices of V2 , each forming its own color-class. Formally: Lemma 2.1 The graph Ĝ that corresponds to a yes-instance I admits a grundy number of size 2 • | V2 | Proof: Let I be a yes-instance. Choose a collection {S i } | V2| i=1 of subsets of V1 so that each S i contains exactly one vertex from A e , B e ′ and corresponds to a min-rep cover. The existence of such S i follows from Lemma 1.6 and because every Ṽ1 vertices is duplicated | V2 |/6 ℓ times. We place these sets as the first | V2 | color-classes in the ordering. After that, we place | V2 | color-classes, each containing a single | V2 | vertex.

Corollary 3. 2

 2 If I is a no-instance, then for small enough µ, with probability1 -exp(-Θ(m)) opt ≤ (2 -µ)| V2 |.Proof: If I is a no-instance, then from Claim 2.3 probability at least 1 -exp(-Θ(m)) there is not a lucky pair. Hence by Lemma 3.1 Assumption 2.1 cannot hold, and so opt≤ (2 -µ)| V2 | ✷ Theorem 3.3 There exists a constant τ so that approximating the grundy number problem within (1 + τ ) is NP-hard, under randomized reductions Proof: By Lemma 2.1, Ĝ that corresponds to a yes-instance has grundy number bounded below by 2| V2 |. By Corollary 3.2, with high probability a no-instance has a size (2-µ)| V2 | size partition for some universal constant µ. The claim follows. ✷

  contain a neighbor of v. Recall that d is the degree of every supervertex in the supergraph SG(I). The degree of v in Ĝ is less than| V2 | + d • m.Indeed, say without loss of generality that v ∈ A e . Thus, v has | V2 | -1 neighbors in A e (recall that A e was cliqued). In addition, for every one of the d superedges involving A e in SG(I), v is joined to half of the m vertices in the corresponding ground set.It thus follows thati max < | V2 | + d • m = | V2 | + | V2 |/q. Note that q > n.The claim follows. ✷ Corollary 3.5 The last (1-2µ)| V2 | color-classes in the optimal partition are type 2 color-classes, namely, are color-classes containing a single V2 vertex. In addition, the first (1 + µ)| V2 | color-classes include at least (1 -µ)| V2 | type 1 color-classes. Proof: The first part of the corollary follows directly from Claim 3.4. In addition, as the last (1 -2µ)| V2 | color-classes are of type 2 (by Claim 3.4), there could be at most 2 • µ| V2 | additional type 2 or type 3 color-classes among the first (1 + µ)| V2 | color-classes. Indeed, each type 2 or 3 cluster contains a vertex of V2 . The claim follows. ✷ Corollary 3.6 The optimum solution has (1 -µ)| V2 | color-classes that are type 1 (subsets of V1 ) and are followed by (1 -2µ)| V2 | type 2 color-classes (color-classes containing a single V2 vertex). We focus on this subset of color-classes: Definition 3.1 The (1 -µ)| V2 | (at least) color-classes of type 1 that are followed by (1 -2 • µ)| V2 | (at least) type 2 color-classes are the important color-classes.

  The claim follows for a large enough ℓ. ✷As V1 = 2q • | V2 |, we get the following corollary.Corollary 3.9 The number of type 1 problematicC i is bounded by µ • | V2 |. Hence, there are at least (1 -2µ)| V2 | type 1 non-problematic important color-classes C i . Proof: The total number of V1 vertices is 2q • | V2 |. If C i is not problematic, C i contains at least 2q/µelements (Claim 3.8). Let j be the number of type 1 problematic color-classes. Clearly:j • 2q/µ ≤ | V1 | = 2q • | V2 |. Thus, j ≤ µ • | V2 |.As from Corollary 3.6 we know that there are at least (1 -µ)| V2 | important color-classes, the claim follows. ✷Finally, we prove Lemma 3.1. Namely, that under Assumption 2.1 a lucky pair exist.

  2. C i does not min-rep cover f .3. DS(C′ , M ′ ) holds (C ′ is a dominating set of M ′ ).The only missing property from the definition of a lucky pair is|C ′ ∩ (A e ∪ B e ′ )| ≤ 8 • ρ.By the assumption that there is no lucky pair, |C i ∩ (A e ∪ B e ′ )| > 8 • ρ = 24

Acknowledgment

The author thanks Rajiv Gandhi and Magnus M. Halldórsson for useful discussions and comments.


Ludger Rüschendorf

Eva-Maria Schopp

Note on the weighted internal path length of b-ary trees

Keywords: b-ary random trees, continuous time tree models, contraction method, internal path length

 to recursive sequences of random variables with continuous time parameter.

Introduction

In this paper we derive a limit theorem for the internal path length of edge-weighted b-ary random trees. For this class of trees which includes as particular cases many well known types of random trees as e.g. random binary search trees, random recursive trees, random split trees and others in a recent paper by [START_REF] Broutin | Large deviations for the weighted height of an extended class of trees[END_REF], a general law of large numbers for the weighted height was established.

The weighted b-ary tree is defined as follows. Let T ∞ denote an infinite complete rooted b-ary tree. To each node u in T ∞ independently a random vector ((Z 1 , E 1 ), . . . , (Z b , E b )) is assigned corresponding to the b outgoing edges of u where Z i , E i ≥ 0, each pair (Z i , E i ) is identically distributed as (Z, E) and where Z, E have finite expectations. We also assume that (Z i ) and (E i ) are independent. Z e assigns a weight and E e an age to edge e. Then for node u

G u := e∈π(u)
E e is the age of u

(1)

D u := e∈π(u)
Z e is the weighted depth of u.

(2)

Here π(u) is the set of edges in T ∞ on the path of the root to node u. The b-ary tree of age ≤ t then is defined in continuous time t ≥ 0 by

T t := {u ∈ T ∞ ; G u ≤ t}.
(3)

H n n -→ P c, (6)
where E) } denotes the Cramer function of (Z, E). This result applies to rBST, random recursive trees, plane oriented trees, oriented trees, split trees and others. Their proof was based on Chernoff's theorem and extends earlier results of [START_REF] Biggins | A note on the growth of random trees[END_REF] and [START_REF] Biggins | Chernoff's theorem in the branching random walk[END_REF][START_REF] Biggins | The asymptotic shape of the branching random walk[END_REF] using branching random walks. The upper bound in (6) can be extended to dependent reproduction based on the Gärtner-Ellis theorem (see [START_REF] Schopp | Stochastische Fixpunktgleichungen, exponentielle tail Abschätzungen und large deviation für rekursive Algorithmen[END_REF]). The lower bound however needs a new Galton-Watson type result for the case of dependent reproduction which seems to be not available in sufficient generally. The application of our limit theorem to concrete examples depends upon an expansion of the first moment of the path length resp. in some cases of the first two moments.

c = argmax{ α ρ ; (ρ, α) ∈ C Z,E }, with C Z,E = {(ρ, α); Λ * Z,E (α, ρ) = log b, ρ ≤ E(E), α ≥ E(Z)}. Here Λ * Z,E = sup λ∈R 2 { t, λ -log Ee λ,(Z,
2 Limit theorem for the weighted internal path length For the internal path length of b-ary weighted trees as introduced in Section 1 we obtain the following recursive equation in continuous time which arises when splitting the tree at the root:

Y t d = b i=1 Y (i) t-Ei 1l {Ei≤t} + b t , t > 0 (7) where b t = b i=1 Z i V (i) t-Ei , defining Y 0 := 0, V s := 0 for s ≤ 0. Here (Y (i) t ) are independent copies of the internal path length process Y t , V (i) t-Ei is the number of nodes in subtree i with age ≤ t -E i , (V (i) t )
are independent copies of each other. To argue for (7) let u 1 , . . . , u b the b nodes of T t below the root with corresponding ages E 1 , . . . , E b . If E 1 > t, then V t-E1 the number of nodes in the subtree with root u 1 , is zero and we get no contribution of this subtree to the internal path length. Only the nodes in the subtree of u 1 of age less than t -E 1 contribute to the internal path length. For each of them we have to add the weight Z 1 of the edge from the root to u 1 , i.e. Z 1 V

(1) t-E1 . Similarly, the contribution of the other subtrees is accounted in (7) yielding the recursion

Y t d = b i=1 Y (i) t-Ei 1l {Ei≤t} + b t . ( 8
)
To deal with the recursive random variables (Y t ) with continuous time parameter t as in (8) we derive in the following an extension to continuous time of the contraction method as developed in [START_REF] Neininger | A general limit theorem for recursive algorithms and combinatorial structures[END_REF] (see also [START_REF] Rösler | The contraction method for recursive algorithms[END_REF]). Let 0 < s ≤ 3, let Y t be s-integrable for all t, and consider the normalized version X t of Y t defined by

X t := Y t -M t √ C t , (9)
where for 1 < s ≤ 3, M t := EY t and for 2 < s ≤ 3, C t := Var(Y t ), C t > 0 else (for the motivation of this normalization see [START_REF] Neininger | A general limit theorem for recursive algorithms and combinatorial structures[END_REF]). Convergence will be formulated w.r.t. the Zolotarev metric

ζ s (X, Y ) = sup f ∈Fs |E(f (X) -f (Y ))|, (10)
where

s = m + α, 0 < α ≤ 1, m = ⌈s⌉ -1 ≥ 0 is an integer and F s = {f ∈ C m (R, R); f (m) (x) - f (m) (y) ≤ |x -y| α }
ζ s (X + Z, Y + Z) ≤ ζ s (X, Y ), ζ s (cX, cY ) = |c| s ζ s (X, Y ). ( 11
)
The normalized version X t of Y t satisfies a recursive equation of a form similar to (8):

X t d = b r=1 A (t) r X (r) t-Er + b (t) , (12)
where

A (t) r := 1l {Er≤t} C t-Er Ct and b (t) := 1 √ C t b t -M t + b r=1 1l {Er≤t} M t-Er . ( 13
)
Theorem 1 Let 0 < s ≤ 3 und X t ∈ L s satisfy the recursive equation ( 12) and assume that A

(t) r s < ∞, b (t)
s < ∞ and sup 0≤u≤t X u s < ∞ for all t > 0. Assume further that 1)

A (t) r L s → A * r , b (t) L s → b * as t → ∞ (14) 2) E b r=1 |A * r | s < 1 (15) 3) For all τ > 0 holds E b r=1 1l {t-Er<τ } |A (t) r | s → 0. ( 16
)
Then X t converges in distribution to a limit X,

ζ s (X t , X) → 0 as t → ∞ (17)
and X is in law the unique solution of the fixpoint equation

X d = b r=1 A * r X (r) + b * (18)
in L s with EX = 0 for 1 < s ≤ 3 and Var X = 1 for 2 < s ≤ 3.

Proof: Note that by the normalization for 1 < s ≤ 2 X t is centered, thus Eb (t) = 0. For 2 < s ≤ 3 EX t = 0, Var(X t ) = 1 and thus Eb (t) = 0 and E(b

(t) ) 2 + E b r=1 (A (t)
r ) 2 = 1. Thus from assumption ( 14) we obtain Eb * = 0, 1 < s ≤ 2 and

Eb * = 0, E(b * ) 2 + E b r=1 (A * r ) 2 = 1, for 2 < s ≤ 3. ( 19
)
This implies by Corollary 3.4 of [START_REF] Neininger | A general limit theorem for recursive algorithms and combinatorial structures[END_REF] existence and uniqueness of a solution of (17) in M s (0, 1), the class of distributions of all X ∈ L s with moments as specified above. We introduce as in the discrete time case an accompanying sequence Q t of X t by

Q t := b r=1 A (t) r 1l {0≤t-Er<τ } X (r) t-Er + 1l {t-Er≥τ } X (r) + b (t) , t > 0, (20)
where (X (r) ), (X (r) t ) are independent copies of X, X t and τ is some suitable positive number specified later in the proof. Then for 2 < s ≤ 3 Var(Q t ) = Var(X t ) and thus Q t ∈ M s (0, 1) and the distance between X t , Q t , X w.r.t. the Zolotarev metric is finite for all t > 0.

By the triangle inequality holds

d t := ζ s (X t , X) ≤ ζ s (X t , Q t ) + ζ s (Q t , X). ( 21
)
As in the discrete case we obtain that the remainder term r t := ζ s (Q t , X) → 0 as t → ∞ using ( 16) and the condition sup 0<t≤τ X t s < ∞. Further, using the ideality properties of the ζ s -metric we obtain

ζ s (X t , Q t ) ≤ E b r=1 1l {0≤t-Er>τ } |A (t) r | s d t-Er
and thus by (21

) for t ≥ τ d t ≤ E b r=1 1l {0≤t-Er≥τ } |A (t) r | s d t-Er + r t (22) ≤ E b r=1 1l {0≤t-Er≥τ } |A (t) r | s sup τ ≤u≤t d u + r * ,
where r * = sup τ ≤t r t < ∞. By an inequality due to Zolotarev

d * t := sup τ ≤u≤t d u ≤ C X s s + sup τ ≤u≤t X u s s < ∞
with some constant C > 0. Thus we obtain by assumption (15) from ( 22)

d t ≤ η • d * t + r * , t > τ (23)
for some η < 1 if τ is chosen large enough. This implies d * t ≤ ηd * t + r * by monotonicity of d * t , i.e. d * t ≤ r * 1-η for all t > τ . Thus we get that d t is bounded. Now we refine the estimate as in the discrete case to obtain that d t → 0. Let d := lim sup t→∞ d t . Then for any ǫ > 0 holds d t ≤ d + ǫ for all t ≥ τ 1 and thus by ( 20), ( 21

) with d * ∞ = sup t d * t d t ≤ E b r=1 1l {τ ≤t-Er≤τ1} |A (t) r | s d * ∞ + E b r=1 1l {t-Er>τ1} |A (t) r | s (d + ǫ) + r t . (24)
Using assumptions ( 15), ( 16), this implies

d ≤ ξ(d + ǫ) where ξ = E b r=1 |A * r | s < 1 a contradiction for ǫ ≤ ǫ 0 .
Since ζ s -convergence implies weak convergence we obtain the conclusion of the theorem. ✷ Remark.

a) In order to apply the limit theorem to concrete b-ary weighted trees we have to control the first moment of Y t for 1 < s ≤ 2 and the first and second moment for 2 < s ≤ 3 (as typically in the case of normal limits). In the case of discrete time recursive sequences several examples of this type have been given in [START_REF] Neininger | A general limit theorem for recursive algorithms and combinatorial structures[END_REF]. [START_REF] Broutin | Large deviations for the weighted height of an extended class of trees[END_REF] applied their results on the height of b-ary weighted trees to several trees. In the case where the age variables are exponential the corresponding b-ary tree has a Markov structure, the number of nodes V t can be determined by a law of large numbers and so a transference to e.g. rBST's is possible (see [START_REF] Broutin | Large deviations for the weighted height of an extended class of trees[END_REF]).

b) Assumption 3) of Theorem 1 can be weakened a bit for the limit theorem (see [START_REF] Schopp | Stochastische Fixpunktgleichungen, exponentielle tail Abschätzungen und large deviation für rekursive Algorithmen[END_REF]). Also the random subtree sizes t -E r in the recursive equation ( 12) can be replaced in the formulation of Theorem 1 by general subtree size I r (t) ≤ t as in the discrete time case in [START_REF] Neininger | A general limit theorem for recursive algorithms and combinatorial structures[END_REF]. In a recent paper of [START_REF] Janson | The size of random fragmentation trees[END_REF] a similar extension of the limit theorem of [START_REF] Neininger | A general limit theorem for recursive algorithms and combinatorial structures[END_REF] to the continuous time case has been independently established (even in the multivariate case) and has been applied to a fragmentation process. c) In Theorem 1 we assume finiteness of the s-th absolute moments of the random modified coefficients (A (t) r ) and the modified toll terms (b (t) ). Thus integrability properties of Z, E may have an impact on the applicability of the theorem.

In many applications (see [START_REF] Broutin | Large deviations for the weighted height of an extended class of trees[END_REF]) Z is a bounded random variable. Thus for the finiteness of the s-th moment of b (t) it suffices in that case to estimate the sth absolute moment of the number of nodes up to time t, since

b (t) s ≤ 1 √ C t b ZV t s + c(t),
where c(t) is a constant depending on t.

If for example E is Exponential(1)-distributed, then { V t ≤ n} = {t n ≥ t}, where t n is the time of the n-th birth and V t denote the number of external nodes in the b-ary tree.

As

t k d = k i=1
Ei 1+(i-1)(b-1) we obtain

P ( V t ≥ k) = P k i=1 E i 1 + (i -1)(b -1) ≤ t = P 1 b -1 k i=1 E i 1 b-1 + (i -1) ≤ t ≤ P k i=1 E i i ≤ t(b -1) = P max{E 1 , . . . , E k } ≤ t(b -1)
= (1e -t(b-1) ) k .

Therefore the s-th moment of V t is bounded by the s-th moment of a geometric G(e -t(b-1) ) random variable, and since P (V t ≥ k) = P ( V t ≥ (b -1)k + 1) we have also a bound for V t .

  |T t | the random number of nodes of T t .[START_REF] Broutin | Large deviations for the weighted height of an extended class of trees[END_REF] proved a strong law for the height assuming that Z i , E i are independent. More precisely they established

	Important parameters of T (4)
	the path length of T t ,
	Y t :=	D u	(5)
	u∈Tt
	and V t =
	1365-8050 c 2007 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

t are the height of T t H t := max{D u : u ∈ T t }

  denotes the space of m-fold continuously differentiable real functions on R 1 with a Hölder condition for the m-th derivative. ζ s (X, Y ) is finite if X, Y have finite absolute moments of order s and the moments of order 1, . . . , m of X and Y coincide. ζ s is an ideal metric of order s, i.e. for Z independent of X, Y and any c ∈ R holds