Olivier Bodini
email: olivier.bodini@lip6.fr

Thomas Fernique
email: thomas.fernique@lif.univ-mrs.fr

Éric Rémila
email: eric.remila@ens-lyon.fr

E Remila

Distances on Lozenge Tilings

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Lozenge tilings are now a classical model, used by physicists as a model for quasicrystals [START_REF] Grunbaum | Tilings and Patterns[END_REF], since the discovery of the famous Penrose tilings, with a pentagonal symmetry. We are especially interested on tilings of finite 2n-gons. If such a tiling contains three rhombic tiles which pairwise share an edge, then a new tiling of the same 2n-gon can be obtained by just changing the position of those three tiles. This operation is called a flip. The tiling space of a fixed 2n-gon is the graph whose vertices are tilings of and two tilings being linked by an edge if they differ by a single flip.

The combinatorial properties of tiling spaces are not trivial for n ≥ 4. The connectivity of these spaces has been proved in [START_REF] Kenyon | Tiling a polygon with parallelograms[END_REF], nevertheless in the case of infinite tilings as Penrose tiling this property is not true even if we admit an infinite number of flips [START_REF] Bodini | Characterizations of Flip-accessibility for Rhombus Tilings of the Whole Plane[END_REF][START_REF] Bodini | Characterizations of Flip-accessibility for Domino Tilings of the Whole Plane FPSAC[END_REF]. The main argument is the following: each tiling is linked to a special fixed tiling T 0 . Therefore, this proof does not give a precise result for the flip-distance between any pair (T , T ′ ) of tilings in the tiling space. Moreover, by elementary geometrical considerations (de Bruijn lines), a lower bound for the flip-distance, called the Hamming-distance, is canonically obtained.

In this paper, we precisely investigate the quality of this lower bound. We first prove that, for octagonal tilings (i.e. n = 4), the Hamming-distance is actually the flip-distance (section 4). This is an extension of the same result about the previously known hexagonal tilings [START_REF] Rémila | On the lattice structure of the set of tilings of a simply connected figure with dominoes[END_REF]. The lack of a distributive lattice structure on the tiling space for the octagonal tilings makes the proof more difficult and the result more surprising. Conversely, there exists a (very small in average) difference when n ≥ 6. Indeed, there are a few number of pairs of tilings for which the Hamming-distance is strickly lower than the flip-distance (section 5). The case n = 5 needs a tedious case-study. We only indicates, in this paper, some hints about the way of proving it (section 6). The exhaustive proof is a work in progress.

Regarding related results, it has be proven in [START_REF] Felsner | A theorem on higher Bruhat orders[END_REF] that there exists a fixed special tiling T 0 in a unitary 2n-gon such that the flip-distance and the Hammingdistance between a variable tiling T and T 0 are always equal. But this situation cannot be extended to any arbitrary pairs of tilings of general (m 1 , . . . , m n )-2ngons (i.e. with m i pseudo-lines of type i).

2n-gons, tilings and de Bruijn lines

Let V = (v 1 , . . . , v n ) be a n-uple of vectors of R 2 (with no pair of colinear vectors) and (m 1 , . . . , m n ) be a n-uple of positive integers (n > 1). The (m 1 , . . . , m n )-2n-gon is the subset of R 2 :

Z(V, M ) = {v|v = n k=1 λ k v k , λ k ∈ [-m k , m k ]}
The 2n-gon is regular if, for 0 ≤ k < n, we have v k+1 = (cos(πk/n), sin(πk/n)). We only work on regular zonotopes. When m 1 = . . . = m n = 1, the regular 2n-gon is unitary.

For 1 ≤ i < j ≤ n, we denote by T ij the lozenge prototile: T ij = {λv i + µv j , -1 ≤ λ, µ ≤ 1}. A lozenge tilings of 2n-gon is a set of translated copies of lozenge prototiles with pairwise disjoint interiors whose union is the 2n-gon. Let T be a lozenge tiling, the vertices (resp. edges) of T are the vertices (resp. edges) of the tiles which belong to T .

The combinatorial structure of tilings of a (m 1 , . . . , m n )-2n-gon depends only on the n-uple (m 1 , . . . , m n ) but not on the vectors v i of the 2n-gon. This important property is not true in dimension 3 or higher [START_REF] Desoutter | Flip dynamics in three-dimensional random tilings[END_REF], and induces that the choice to study tilings of regular 2n-gons is not a restriction 'in fine' for the 2D-problem.

For each integer k ∈ {1, ..., n}, and each tiling T of Z(V, M ), a k-located height function (classical height functions have been introduced by Thurston [START_REF] Thurston | Conway's tiling group[END_REF] h T,k is a function from vertices to Z such that, for any pair (x, x ′ ) of vertices of T with x ′ = x + 2v i and [x, x ′ ] being an edge of T , We use the normalized k-located height function such that, for each vertex x, h T,k (x) ≥ 0 and there exists a vertex x 0 with h T,k (x 0 ) = 0. The existence of height function and uniqueness of normalized height functions is well known [START_REF] Bodini | Generalized Tilings with Height Functions[END_REF].

-h T,k (x ′ ) = h T,k (x) + 1 if i = k, -h T,k (x ′ ) = h T,k (x) otherwise.
Following [START_REF] De Bruijn | Dualization of multigrids[END_REF], we define the de Bruijn line S i,j of T as the set of tiles whose normalized i-located function is j -1 on one edge, and j on the opposite one. See Figure 1. A de Bruijn line S i,j is said of type i. It is interesting to note that two distinct de Bruijn lines of the same type do not intersect while two de Bruijn lines of different types share a single tile. Conversely, each tile is the intersection of two de Bruijn lines of different types. The de Bruijn line S i,j disconnects T into two parts:

-△(S i,j ) formed by tiles for which the i-located function is at least j on any vertex. -▽(S i,j ) formed by tiles for which the i-located function is at most j -1 on any vertex.

Three de Bruijn lines of pairwise different types i, j, k define a tiled region of the zonotope, called pseudo-triangle of type ijk. A minimal (for inclusion) pseudo-triangle is reduced to three tiles, each of them being the intersection of a pair of de Bruijn lines.

Hamming-distance and flip-distance between two tilings

We introduce in this section the notions of flip-distance and Hamming-distance between two tilings.

Flip-distance

Two tiles are adjacent if they share an edge. Assume that three tiles of a tiling T are pairwise adjacent (i. e. form a minimal pseudo-triangle). In this case, one can replace in a unique way these three tiles by three other tiles of the same

S k x , k S i x , i Sj x , j
Fig. 2. In gray, a pseudo-triangle type, to obtain another tiling T ′ of the same 2n-gon. This operation is called a flip (see. Fig. 3). The tiling space of Z(V, M ) is the undirected graph whose vertices are tilings of Z(V, M ), and two tilings are linked by an edge if they differ by a flip. Definition 1. The flip-distance between two tilings T 1 and T 2 of Z(V, M ), denoted by d F (T 1 , T 2 ), is the length of the shortest path relying T 1 with T 2 in the tiling space. It is a finite value, since the tiling space is connected [START_REF] Kenyon | Tiling a polygon with parallelograms[END_REF].

The figure 4 illustrates the topology of such a graph.

Hamming-distance

For every triple of de Bruijn lines (S i,αi , S j,αj , S k,α k ), such that i < j < k, we state:

-T(S i,αi , S j,αj , S k,α k ) = + if the tile S i,αi ∩ S j,αj belongs to △(S k,α k ), -T(S i,αi , S j,αj , S k,α k ) = -otherwise.
In this way, each tiling induces a one dimensionnal array T containing + or as entries and indexed on the set L m of all possible triples. It can be easily proved that the array T totally characterises the tiling.

---------- Nevertheless, there exist some m-uples of {-, +} m that do not correspond to any tiling. A characterization of m-uples induced by tilings has been given by Chavanon-Rémila [START_REF] Chavanon | Rhombus tilings: decomposition and space structure[END_REF]. It uses a set of "local" conditions, in a sense that each of them involving a finite number (two or four) values of the array.

+ --------- ------+ --- ---------+ + + -------- + --------+ ---+ --+ --- ------+ + -- --------+ + + + + ------- + + -+ ------ + + -------+ + -------+ + + + + + ------ + + + ------+ + + -+ --+ --- + + + + + ----- + + + + --+ --- + + + --+ ---+ + + + + + + ---- + + + + + -+ --- + + + + + + + --- + + + + + + ---+ + + + + + -+ + -- + + + + + + + + -- + + + + + + --+ + -+ -+ --+ --- ---+ --+ + -- ------+ + + - -+ -+ --+ + -- ---+ + -+ +
Let T and T ′ be two tilings whose associated arrays are respectively T and T ′ . The triple (S i,αi , S j,αj , S k,α k ) (or, by extension, the pseudo-triangle of corresponding de Bruijn lines) is inverted when

T(S i,αi , S j,αj , S k,α k ) = T ′ (S i,αi , S j,αj , S k,α k ).
Definition 2. The Hamming-distance between T and T ′ , denoted by d H (T , T ′ ), is the number of inverted triples. This is exactly the classical Hamming-distance between arrays T and T ′ . Proposition 1. For every two tilings T and T ′ of a 2n-gon, the following inequality holds:

d H (T , T ′ ) ≤ d F (T , T ′ )
Proof. Each inverted triangle need to be reversed. But a flip can only turn upside down a unique triangle.

Distance comparison: our results

The goal of this paper is to compare flip-distance and Hamming-distance. More precisely, we are interested in the existence and the ratio of deficient configurations. The deficience are naturally defined as follows:

Definition 3. The pair (T 1 , T 2 ) of tilings is deficient if its flip-distance is strictly greater than its Hamming-distance.

Proposition 2 ( [START_REF] Rémila | On the lattice structure of the set of tilings of a simply connected figure with dominoes[END_REF]). For hexagons (i. e. n = 3), the Hamming-distance between two lozenge tilings is equal to the flip-distance between them.

This result, which also holds for any polygon, is strongly related to the structure of distributive lattice of the space of lozenge tilings, (for n = 3). It also can be interpreted in terms of "stepped surface" [START_REF] Arnoux | Functional stepped surfaces, flips and generalized substitutions[END_REF]: the Hamming-distance is exactly the volume of the solid inbetween the stepped surfaces defined by the tilings. It is possible to crush this gap by deforming the stepped surfaces decreasing the current volume. But for the general 2n-gons one cannot use the same type of arguments, since the lattice structure and the volume interpretation are both lost.

Distance equality for n = 4

Distances between the tilings of the unitary 8-gon. It is well-known that there exists only 8 tilings of the unitary 8-gon centered in Ω. These 8 tilings are isometrically equivalent. They can be obtain of acting the dihedral group of order 16 (which is isomorph to the group of isometry that preserves the octagon) from one of them. More precisely, the flip which is in general a local move can be seen here as the global map s • ρ or s • ρ -1 where ρ is the rotation of angle 2π/2n centered in Ω and s is the central symmetry of center Ω. The tiling space of these tilings is a cycle (of length 8) which is also the orbit of a tiling under s • ρ. We can easily remark that the Hamming-distance between two unitary 8-gon tilings is equal to their flip-distance. Up to isometry, there only exists 4 types of pair of tilings which corresponds to important configurations related to the next lemma 1.

Fig. 5. The tiling space of the unitary octagon.

Distances between general 8-gon tilings. In fact, the distance equality is also true for general 8-gons. But, the proof is not straightforward. Let (T 1 , T 2 ) be a pair of tilings, we need to introduce another array B as follows:

-B(S i,αi , S j,αj , S k,α k ) = 1 if the pseudo-triangle (S i,αi , S j,αj , S k,α k ) is inverted (i.e. T(S i,αi , S j,αj , S k,α k ) = T ′ (S i,αi , S j,αj , S k,α k ).), -B(S i,αi , S j,αj , S k,α k ) = 0 otherwise. Some consistence conditions (lemma 1,2) in B are similar (and local) to those appearing in the characterization of T.

Lemma 1. Let (T 1 , T 2 ) be a pair of tilings of the (m 1 , . . . , m n )-2n-gon and let us consider four de Bruijn lines, namely S 1 , S 2 , S 3 , S 4 , and consider that their relative positions in T 1 are:

1. such that S 3 and S 4 have the same type and S 4 cuts the pseudo-triangle (S 1 , S 2 , S 3 ) (see figure 6a). Then, we have:

B(S 1 , S 2 , S 3 ) = 1 ⇒ B(S 1 , S 2 , S 4 ) = 1 and B(S 1 , S 2 , S 4 ) = 0 ⇒ B(S 1 , S 2 , S 3 ) = 0.
In other words, (B(S 1 , S 2 , S 3 ), B(S 1 , S 2 , S 4 )) belongs to {(0, 0), (0, 1), (1, 1)}. 2. such that the pseudo-triangle (S 2 , S 3 , S 4 ) is included in the pseudo-triangle (S 1 , S 2 , S 3 ) as described in the figure 6b. Then, the following sequence:

(B(S 1 , S 3 , S 4 ), B(S 1 , S 2 , S 4 ), B(S 1 , S 2 , S 3 ), B(S 2 , S 3 , S 4 ))
is monotonic. In other words, it belongs to the set {(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 1), (0, 1, 1, 1), (1, 1, 1, 1), (1, 1, 1, 0), (1, 1, 0, 0), (1, 0, 0, 0)}.

Proof. This can easily be done with the following arguments :

1. We have to keep the order between the de Bruijn lines of a same type in the both tilings. 2. This can be done from the study of the 8 tilings of the unitary octagon. Lemma 2. Let (T 1 , T 2 ) be a pair of tilings of the (m 1 , . . . , m n )-2n-gon, if the pseudo-triangle (S i , S j , S k ) of T 1 of type ijk is inverted and it is only cut by de Bruijn lines of type i,j or k then every sub-pseudo-triangle (S ′ i , S ′ j , S ′ k ) included in (S i , S j , S k ) is inverted. In particular, (S i , S j , S k ) contains an inverted minimal sub-pseudo-triangle.

Proof. First, by lemma 1, an easy induction on the number of de Bruijn lines proves that every sub-pseudo-triangle (S ′ i , S ′ j , S ′ k ) of (S i , S j , S k ) is inverted. In the same way, it is clear that the configuration always contains a minimal pseudotriangle. Proof. We first prove that for every pair of distinct tilings (T 1 , T 2 ) of the (m 1 , . . . , m 4 )-8-gon, T 1 contains an inverted minimal pseudo-triangle (a closer flip is feasible on it).

Considering all these previous lemmas, an induction on the number m 4 of de Bruijn lines of type 4 can be done.

For initialization, if m 4 = 0, the 8-gon is actually a hexagon for which the result is previously known. Suppose that m 4 = 1 and when we remove the de Bruijn line S of type 4, T 1 \S are identical to T 2 \S. In this case, the positions of the de Bruijn line S in T 1 and T 2 mark the boundary of a stepped surface U in T 1 \S which is a hexagonal tiling (see figure 7).

The flip-distance and the Hamming-distance between T 1 and T 2 are exactly the number of tiles in U . Indeed, one easily proves that, in any case, a flip can be done, corresponding to a local transformation on the position of the de Bruijn line S in T 2 (i.e. surrounding a unique tile by the other side). Now, for the other cases, we can remove a de Bruijn line S = S 4,α , of type 4, in both tilings T 1 , T 2 in such a way that T 1 \S are distinct to T 2 \S (this is always possible when m 4 > 1). Henceforward, we are going to only work on the tiling T 1 . By hypothesis of induction, there exists an inverted minimal pseudotriangle (S a , S b , S c ), in the tiling T 1 obtained by removing of S and sticking the two remaining parts of the initial tiling.

After this, let us replace the removed de Bruijn line S. The only tricky case arises when S cuts the pseudo-triangle (S a , S b , S c ) and the types of de Bruijn lines S a , S b and S c are respectively 1, 2 and 3. Moreover, the minimal subpseudo-triangle of (S a , S b , S c ) (which is (S a , S b , S) or (S b , S c , S)) is not inverted (in any other configuration, the existence of an inverted minimal pseudo-triangle is trivial).

We can consider without loss of generality that T(S a , S b , S c ) = + and that (S a , S b , S) is the non-inverted minimal sub-pseudo-triangle of (S a , S b , S c ). The 3 other cases are in fact isometrically equivalent.

Since (S a , S b , S) is not inverted, we have by lemma 1.2 applying on the pseudo-lines {S a , S b , S c , S} that the pseudo-triangle (S a , S c , S) is inverted. If this pseudo-triangle is minimal, then the result ensues. Otherwise, (S a , S c , S) Fig. 7. The bold (resp. dotted) line indicates the position of the de Bruijn line S in T 1 (resp. in T 2 ). The stepped surface U is in dark gray inbetween the two de Bruijn lines.

can only be cut by de Bruijn lines of type 1 or 2, because of the minimality of the pseudo-triangle (S a , S b , S c ) in T 1 \S. Let S 1,j1 (resp. S 2,j2 ) be (if there exists) the de Bruijn line of type 1 (resp. type 2), with j 1 minimal such that S 1,j1 cuts (S a , S c , S) (resp. with j 2 minimal such that S 2,j2 cuts (S a , S c , S)) (see fig. 8). The pseudo-triangle (S 1,j1 , S c , S) (resp. (S 2,j2 , S c , S)) is inverted. Indeed this follows of applying lemma 1.1 to the pseudo-triangles (S a , S c , S) (resp. (S b , S c , S)) which are both inverted. If one of them is minimal, we can conclude. Otherwise, the tile S 1,j1 ∩ S 2,j2 belongs to △(S c ) ∩ ▽(S) and necessarily at least one of the pseudo-triangles (S 1,j1 , S 2,j2 , S c ) and (S 1,j1 , S 2,j2 , S) is inverted (by applying lemma 1.2 on {S c , S, S 1,j1 , S 2,j2 } with (S 1,j1 , S c , S) inverted). But (S 1,j1 , S 2,j2 , S c ) (resp. (S 1,j1 , S 2,j2 , S)) can only be cut by de Bruijn lines of type 1 (resp. type 2). Because of the minimality of j 1 and j 2 , it includes by lemma 2 an inverted minimal sub-pseudo-triangle of type 123 (resp. type 124). Thus, we always have a inverted minimal pseudo-triangle in T 1 . Now, we can prove the theorem. Indeed, by absurd, let (T 1 , T 2 ) be a deficient pair of tiling of a (m 1 , . . . , m 4 )-8-gon. Moreover, we suppose that it is flip-distance minimum belong the deficient pairs. So, T 1 does not contain any inverted minimal pseudo-triangle. Indeed, an inverted minimum pseudo-triangle corresponds to a flippable position which brings closer T 1 from T 2 . But this is in contradiction with what we proved above.

Corollary 1. A (m 1 , . . . , m 4 )-8-gon tiling (resp. 4 → 2 tiling of the plan) is uniquely determined by the value of T for its minimal pseudo-triangles.

Proof. Consider T 1 and T 2 be a pair of tiling of a (m 1 , . . . , m 4 )-8-gon with the same set M of minimal pseudo-triangle. If T 1 (v) = T 2 (v) for every v ∈ M , then T 1 has no inverted minimal pseudo-triangle. So, by theorem 1, T 1 = T 2 . For the 4 → 2 tilings, it suffices to take the limit when (m 1 , m 2 , m 3 , m 4 ) tends to ∞.

Counterexamples for n = 6

There exist deficient pairs of tilings of the unitary 12-gon, which yields that this is also true for every 2n-gon, for n ≥ 6. It is possible, using a computer, to find every deficient pair for the unitary 12-gon : up to isometry there exists only two deficient pairs of tilings. For these two pairs the Hamming-distance is 16 but the flip-distance is 18. From the first pair (T 1 , T 2 ) which has no symmetry (Fig. 9), one obtains, by symmetry 12 different deficient pairs of tilings. The second one (Fig. 10) induces 4 different deficient pairs of tilings. These 16 pairs of tilings are exactly the deficient pairs of tilings among the (908) 2 possible pairs of tilings (there are 908 different tilings in the unitary 12-gon). The expected flip-distance between two tilings is not 10 (i. e. the expected Hamming-distance, as it would be if there were no deficient pair) but around 10,000 07. This is somewhat surprising.

Distances between general 10-gon tilings and Conclusion

This section is dedicated to explain the remained objectives of this work. In particular, we give below the main ideas of a currently hypothetic proof for the following conjecture:

Conjecture 1. The hamming-distance between two tilings of any (m 1 , . . . , m 5 )-10-gon is equal to their flip-distance. At present time, we have not already proven all the huge number of cases that occurs in the process of such a proof. But we keep hope alive to be able to achieve this tedious case-study. The following proved lemmas are the cornerstone of our plan.

Lemma 3 (The harp lemma). Let P = (S 1 , S 2 , S 3 ) be an inverted pseudotriangle of type ijk. Let us consider that P is cut only by de Bruijn lines S 4 , ..., S p of type l and m different with i, j and k. Then, the configuration formed by S 1 , ..., S p contains an inverted minimal subtriangle (S α , S β , S γ ).

Lemma 4 (10-cycle lemma). Suppose that there exits a deficient pair of tilings (T 1 , T 2 ) for a (m 1 , . . . , m 5 )-10-gon, and consider the smallest m 5 possible. If we delete a de Bruijn line S of type 5, we obtain a pair of tilings which (are equal or) contains an inverted minimal pseudo-triangle P of type ijk (say 123). Then, when we undelete the de Bruijn line S, we have that P is cut by S and an inverted pseudo-triangle P 1 of type 135 is created. The pseudo-triangle P 1 also needs to be cut by a de bruijn line which is of type 4. This creates an inverted pseudo-triangle of type 345, and so on. The complete process gives the 10-cycle described below (fig. 11).

But in the 10-cycle lemma, it seems to be impossible to start from a pseudotriangle T of type ijk and after a 10-cycle to return to the same pseudo-triangle T . In each already studied case, we always reach a new pseudo-traingle T ′ of type ijk. So, we strongly conjecture that the property that the Hamming-distance between two tilings is equal to the flip-distance is also true for 10-gons too, but the proof is a huge case-study that has not been precisely checked yet. It is a work in progress.

This study is the first step of a more general research. Indeed, the combinatorics of the set parallelogram tiling of general n-dimensional zonotopes is always very misleading, even though recent works [6] [8] have proved that the tiling space is connected in a large case of zonotopes [START_REF] Björner | Oriented Matroids[END_REF]. But, the problem is always opened for 6 → 3 zonotopes (i. e. constructed with 6 vectors of R 3 ) with icosaedral symmetry. The answer could have interesting application in quasicrystal theory and statistical mechanics. It is a persective for the future.

Fig. 1 .

 1 Fig. 1. The 2-located height function and two de Bruijn lines.

Fig. 3 .

 3 Fig. 3. Two neighbor tilings. One can pass from one to the other one by a single flip.

Fig. 4 .

 4 Fig. 4. The tiling space of the (1, 1, 1, 1, 1)-10-gon.

Fig. 6 .

 6 Fig. 6. The configurations for the lemma 1.

Fig. 8 .

 8 Fig. 8. A configuration involving the de Bruijn lines S 1,j1 and S 2,j2 such that their intersection is in (S a , S c , S).

Fig. 9 .

 9 Fig. 9. The first deficient pair of tilings of the unitary 12-gon.

Fig. 10 .

 10 Fig. 10. The second deficient pair of tilings of the unitary 12-gon.

Fig. 11 .

 11 Fig. 11. The 10-cycle.


Olivier Bodini

On the Minimum Size of a Contraction-Universal Tree

A tree Tuni is m-universal for the class of trees if for every tree T of size m, T can be obtained from Tuni by successive contractions of edges. We prove that a m-universal tree for the class of trees has at least m ln(m) + (γ -1)m + O(1) edges where γ is the Euler's constant and we build such a tree with less than m c edges for a fixed constant c = 1.984...

Introduction 2 Terminology

Our graphs are undirected and simple (with neither loops nor multiple edges). We denote by G(V, E) a graph (its vertex set is V (G) and its edge set is E(G) (a subset of the family of all the V (G)-subsets of cardinality 2)). Referring to C. Thomassen [START_REF] Thomassen | Embeddings and Minors, chapter 5 in Handbook of Combinatorics[END_REF], we recall some basic definitions that are useful for our purpose:

We denote by P n the path of size n. If x is a vertex then d(x), the degree of x, is the number of edges incident to x.

Let e be an edge of E(G), the graph denoted by Ge is the graph on the vertex set of G, whose edge set is the edge set of G without e. We call classically this operation deletion.

Let e = {a, b} be an edge of G(V, E), we name contraction of G along e, the graph denoted by G/e = H(V ′ , E ′ ), with V ′ = (V / {a, b}) ∪ {c} where c is a new vertex and E ′ the edge set which contains all the edges of the sub-graph G 1 on V /e and all the edges of the form {c, x} for {a, x} or {b, x} belonging to E.

We say that H is a minor of G if and only if we can obtain it from G by successively deleting and /or contracting edges, in an other way, we can define the set M (G) of minors of G by the recursive formula :

M (G) = G ∪   e∈E(G) M (G/e)   ∪   e∈E(G) M (G -e)  
The notion of minor induces a partial order on graphs. We write A B to mean "A is a minor of B".

For technical reasons, we prefer to use the size of a tree (edge number) rather than its order (vertex number).

Finally, let us recall that, a graph G uni is m-universal for a sub-class C of graphs if for every element G of C with m edges, G is a minor of G uni .

A Lower Bound

In this section, we prove that a m-universal tree T uni for the trees has asymptotically at least m ln(m) edges. We use the fact that T uni has to contain all spiders of size m as minors. A spider S on a vertex w is a tree such that ∀v ∈ V (S) \ {w} , d(v) ≤ 2. We denote the spider constituted by paths of lengths 1 ≤ m 1 ≤ ... ≤ m k by Sp(m 1 , ..., m k ) (Fig. 1). Definition 1. Let T be a tree, we denote by ∂T the subtree of T with V (∂T ) = V (T )\A, where A is the set of the leaves of T . Also, we denote by Proof. This just follows from an observation.

∂ k the k-th iteration of ∂. Lemma 1. Sp(m 1 , ..., m k ) T involves that ∂Sp(m 1 , ..., m k ) ∂T . Moreover, if for all i, m i = 1 then ∂Sp(m 1 , ..., m k ) is a vertex. Otherwise, put a the first value such that m a > 1, we have ∂Sp(m 1 , ..., m k ) = Sp(m a -1, ..., m k -1) excepted for k = 1, in this last case we have ∂Sp(m 1 ) = Sp(m 1 -2).
m i ≥ 1 + m-1 i=1,i =2 m i -1 . ⊓ ⊔
What the above proof shows, in fact, is the following :

Corollary 1. A minimum m-universal spider for the class of spiders has m i=1,i =2 m i edges. Proof. The spider Sp m m , m m-1 , ..., m 2 , m 2 is clearly a m-universal spi- der of size m i=1,i =2 m i
for the class of spiders, and by theorem 3 it is a minimum value. ⊓ ⊔

The Main Stem

In the sequel, we deal with rooted graph, i.e. graph G where we can distinguish a special vertex denoted by r(G), called the root. Conventionally, any contracted graph G ′ of same rooted graph G will be rooted at the unique vertex which is the image of the root under the contraction mapping, we say in this case that the rooted graph G ′ is a rooted contraction of G. Note that, the contraction operator suffices to obtain all minor trees of a tree. So, we can now define the following new notion for sub-classes of rooted trees : a rooted tree T uni is strongly m-universal for a sub-classes C of rooted trees if for every rooted tree T in C of size m, T is a rooted contraction of T uni . The concept of root is introduced to avoid problems with graph isomorphisms that, otherwise would greatly impede our inductive proof.

For every edge e of a tree T , the forest T \e has two connected components. We call e-branch, denoted by B e , the connected component of T ′ which does not contain r (T ), we define the root of B e as e ∩ V (B e ) .

A main stem of a rooted tree of size m is defined as a path P which is issued from the root and such that for all e-branches B e with e / ∈ E (C), we have |E (B e )| < m 2 (Fig. 2).

Fig.2. A main stem in bold

The following lemma suggests the procedure which will be used to find a subquadratic upper bound for universal trees. Roughly speaking, it endows every tree with some recursive structure constructed with the help of main stems. Lemma 3. Every rooted tree has a main stem.

Proof. By induction on the size of the rooted tree. Let T be a rooted tree, if T has one or two edges, it is trivial. Otherwise let us consider the sub-graph T \r (T ), which is a forest. We choose a connected component T 1 with maximum size and we denote by b 1 the unique vertex of T 1 which is adjacent to r(T ). Tree T 1 , rooted in b 1 , has, by the induction hypothesis, a main stem B. Then the path (

V (B) ∪ {r (T )} , E (B) ∪ {{r (T ) , b 1 }}) is a main stem of T . ⊓ ⊔ Remark 1.
A tree may possess in general several main stems. Let us notice also that a main stem is not necessarily one of the longest paths which contain the root.

The Upper Bound

We need some new definitions. A rooted brush (Fig. 3) is a rooted tree such that the vertices of degree greater than 2 are on a same path P issued from the root.

Fig.3. A rooted brush

A rooted comb X (Fig. 4) is a rooted brush with d (r (X)) ≤ 2 and ∀v ∈ V (X), d (v) ≤ 3.

Fig.4. A rooted comb

The length of a rooted comb corresponds to the length of the longest path P issued from the root which contains all vertices of degree greater than 2.

To obtain an upper bound, we consider two building processes : the first one, a brushing M B , maps rooted trees with a main stem into rooted brushes, the second one, a ramifying M T , consists in obtaining a sequence of rooted trees, assuming that we have an increasing sequence of rooted combs. We note M k T the k-th element of the sequence. These building processes will possess the following fundamental property: Property 1. Let (T, σ) a rooted tree with a main stem σ and (X n ) n∈N a sequence of rooted combs :

∀T ′ T, M B (T ′ , σ) X |E(T ′ )| ⇒ T M |E(T )| T (X n ) n∈N .
Lemma 4. If building processes verify the property 1 and if for all i, the rooted comb X i is strongly i-universal for the class of rooted brushes then the rooted tree M m T (X n ) n∈N is strongly m-universal for the class of rooted trees. Proof. It is just an interpretation of the property.

⊓ ⊔

We now establish the existence of building processes which satisfy property 1.

Brushing M B (Fig. 5). Let T be a rooted tree with a main stem σ. We are going to associate a rooted brush B with it, denoted M B (T, σ) of the same size built from the same main stem σ with the following process: every e-branch B e connected to the main stem by edge e is replaced by a path of length |E (B e )| connected by the same edge. Ramifying M k T . For the second building process we work in two steps : First step. Given rooted trees T 1 , ..., T k with disjoint vertex sets, we build another rooted tree T , denoted [T 1 , ..., T k ], in the following way :

V (T ) = k i=1 V (T i ) ∪ {v 1 , ..., v k+1 } , E(T ) = k i=1 E (T i ) ∪ {{v 1 , r (T 1 )} , ..., {v k , r (T k )}} ∪ {{v 1 , v 2 } , ..., {v k , v k+1 }} , and r(T ) = v 1 .
If

T i = ∅, conventionally {v i , r (T i )} = ∅.
Prosaically, from a path P k = [v 1 , ..., v k+1 ] of size k and from k rooted trees T 1 , ..., T k , we build a rooted tree joining a branch T i to the vertex v i of P (Fig. 6).

Second step. By convention, P -1 = ∅.

We are going to construct rooted trees T k in the following way : T -1 = ∅, T 0 = X 0 , and ∀i, 1 ≤ i ≤ k, T i = T min(u1,i-1) , ..., T min(un i ,i-1) if X i = P u1 , ..., P un i . We can now define M k T :

M k T (X n ) n∈N = T k .
Lemma 5. The building processes described above verify the property 1.

Proof. First, note that M T (X n ) n∈N is an increasing sequence. We prove the lemma by recurrence on the size m of T . When m = 0 or m = 1, this is trivial. We suppose the property is verified for T with size m < m 0 . Let T be a rooted tree of size m 0 with a stem σ, we note e 1 , ..., e k the edges of T issued from σ which do not belong to σ. To each e-branch of T with e ∈ {e 1 , ..., e k } corresponds by M B a e-branch (it is a path of same size) in M B (T, σ). So there exists k distinct e-branches R 1 , ..., R k in X m0 that we can respectively contract to obtain each e-branch with e = e 1 , ..., e k in M B (T, σ). By recurrence hypothesis, we have for 1

≤ i ≤ k, B ei M |E(Be i )| T (X n
) n∈N and we have also

M |E(Be i )| T (X n ) n∈N M |E(Ri)| T (X n ) n∈N . So each e-branch of T is a minor contraction of M |E(Ri)| T (X n ) n∈N .
By associativity of contraction map, we have T M

|E(T )| T (X n ) n∈N . ⊓ ⊔
In this phase, we determine a sequence of rooted combs (X i ) i∈N such that the rooted combs X i are strongly i-universal for the rooted brushes.

In order to achieve this result, we define F p as the set of functions f : {1, ..., p} → 1, ..., p 2 satisfying the following property :

(∀n ∈ {1, ..., p}) ∀i ≤ n 2 (∃k ∈ N) (n -i + 1 ≤ k ≤ n and f (k) ≥ i)
Lemma 6. F p is not empty, it contains the following function ϕ p , defined for 1 ≤ i ≤ p by :

ϕ p (i) = min 2 υ2(i)+1 -1, p 2 , i -1
where υ 2 (k) the 2-valuation of k (i.e. the greatest power of 2 dividing k).

Proof. The verification is obvious. ⊓ ⊔

WG (2002)

Lemma 7. For every sequence F = (f 1 , f 2 , ...) of functions such that f i ∈ F i for i ≥ 1 and f i (k) ≤ f i+1 (k) for all i ≥ 1 and 1 ≤ k ≤ i, the rooted comb defined by Comb F m = [P f m 1 , ..., P f m m ] where P f m i designs the path of size f m (m + 1i) -1, for 1 ≤ i ≤ m is strongly m-universal for the rooted brushes.

Proof. By induction on m : Comb F 1 is strongly 1-universal for the rooted brushes. Suppose that Comb F i has all rooted brushes with i -1 edges as rooted contractions.

We consider two cases depending on the shape of a rooted brush B of size i : case 1 case 2

Brushes of case 1 are clearly rooted contractions of the rooted comb

Comb F i (B ′ Comb F i-1 , so B P 0 , P f i-1 1 , ..., P f i-1 i-1
Comb F i ). Let us study case 2 : B ′ is by induction hypothesis a rooted contraction of the rooted comb Comb F i-j , moreover Comb F i-j P f i j+1 , ..., P f i i . Finally, by the property of f i , there exists 1 ≤ α ≤ j, such that P f i α has more than j edges. Linking these two points, we can conclude that the rooted brush B is always a rooted contraction of the rooted comb Comb F i .

⊓ ⊔

The rooted comb built as in lemma 7 will be said to be associated to the sequence F and denoted by Comb By convention, we put Comb F 0 = P 0 (tree reduced in a vertex) We define T ree F m = M m T Comb F n n∈N . As before, we will say that the tree built in such a way is recursively associated to the sequence F and denoted by T ree F m . Thus, we have : Theorem 5. The rooted tree T ree F m is strongly m-universal for the class of rooted trees.

We now analyze the size of T ree F m .

Proposition 1. Let F = (f 1 , f 2 , ...) be a sequence of functions such that f i ∈ F i for i ≥ 1. The size of a m-universal tree constructed from the sequence is given by the following recursive formula :

u -1 = -1, u 0 = 0 and u k = 2k -1 + k i=1 u f k (i)-1
Proof. It derives from the following observation : m edges constitute the main stem, we have to add m -1 edges to link branches to the main stem and k i=1 u f k (i)-1 edges for the branches.

⊓ ⊔

Theorem 6. There is a sequence of functions G = (g 1 , g 2 , ...) such that g i ∈ F i and E T ree G m < (2m) c where c = 1.984... is the unique positive solution of the equation

1 2 c + 1 2 2c + 1 2 (c-1) -1 -1 2 c -1 = 1.
Proof. We take the following sequence of functions : g m (i) = min 2 υ2(i)+1 , i if i < m and i even, g m (i) = 1 if i odd and g m (m) = m 4 . It is clear that, if m is a power of 2, the comb Comb G m is strongly muniversal for the brushes.

In fact, the function g m takes the value 2 υ2(i)+1 when i is not a power of 2, otherwise it is equal to i. Thanks to this remark and with u m < m + m i=1 u fm(i) ,

(the sequence of sizes is increasing), we obtain u

2 n < 2 n + 2 n-1 + n-1 i=2 2 n-i u 2 i - n-1 i=2 u 2 i +u 2 n-1 +u 2 n-2 .
Thus, in evaluating the sums and reorganizing the terms, we obtain :

u 2 n < α n + 2 nc β with α n = 2 n-1 + 1 + 2 c + 1 2 c -1 - 2 n 2 (c-1) -1 + 2 n(c-1) WG (2002) β = 1 2 c + 1 2 2c + 1 2 (c-1) -1 - 1 2 c -1
Now α n < 0 when m > 1 and β ≤ 1 by definition of c. So u 2 n < 2 nc , hence u m < (2m) c . ⊓ ⊔ Remark 2. We observe that c = ln(x) ln [START_REF] Füredi | Nonexistence of universal graphs without some trees[END_REF] , where x is the positive root of X 4 -5X 3 + 4X 2 + X -2 = 0. Theorem 2 then follows since any rooted tree which is strongly m-universal for the rooted trees is also clearly m-universal for the class of trees.

Conclusion and Related Questions

When using the sequence Φ = (ϕ 1 , ϕ 2 , ...) of lemma 7, the induction step leads to involved expressions that do not allow us to find the asymptotic behavior of the corresponding term u m . A computer simulation gives that such a m-universal tree for the trees has less than m 1.88 edges. In any case, the constructive approach we proposed here, seems to be hopeless to reach the asymptotic best size of a m-universal tree for the trees.

Conjecture 1. The minimal size of a m-universal tree for the trees is m 1+o (1) . As a possible way to prove such a conjecture, it would be interesting to obtain an explicit effective coding of a tree of size m using a list of contracted edges taken in a m-universal tree for the trees.

A variant of our problem consists in determining a minimum tree which contains as a subtree every tree of size m. This is closely related to a well known still open conjecture due to Erdös and Sös (see [START_REF] Erdös | On maximal paths and circuits of graphs[END_REF]).

Fig. 1 .

 1 Fig.1. Sp(2, 2, 2, 3, 3)

Fig. 5 .

 5 Fig.5.

Fig. 6 .

 6 Fig.6. A rooted comb [T1, T2, T3]

F m . Theorem 4 .

 4 A minimum strongly m-universal rooted brush for the rooted brushes has O(m ln(m)) edges.Proof. Proceeding as for theorem 1, we obtain, mutatis mutandis, that a muniversal brush for the brushes has at least m ln(m) + O(m) edges. This order of magnitude is precisely the size of the strongly m-universal rooted comb Comb F m for the class of rooted brushes.⊓ ⊔We have this immediate corollary :Corollary 2. A minimum m-universal brush for the brushes has O(m ln(m)) edges.

  Lemma 2. For every tree T , Sp(m 1 , ..., m k ) T ⇒ T has at least k leaves. T uni . Moreover, it is clear that the terminal edges of the ∂ p T uni constitute a partition of T uni . By the lemma 2, this involves that T uni has at least

	Proof. Trivial.				⊓ ⊔
	Theorem 3. A m-universal tree T uni for the class of trees has at least	m i=1,i =2	m i
	edges.
	Proof. A m-universal tree T uni for the class of trees has to contain as minors all
	spiders of size m. So, for all p it contains as minors the spiders Sp(p, ..., p) where
	we have m p	times the letter p. By the lemma 1, for all p ≤ m 2 , Sp(1, ..., 1)
	∂ p-1 T uni and if m is odd, Sp(1)	∂ ⌊ m 2 ⌋-1 ⌊ m 2 ⌋ i=1 m i	edges if m is even and 1 +	⌊ m 2 ⌋ i=1	m i
	edges if m is odd. An easy calculation proves that these values are always equal to m i=1,i =2 m i . ⊓ ⊔
	Proof. (of the theorem 1) it follows from the usual estimate	n i=1	1 i ∼ ln (n) + γ +
	O 1 n and the inequality	m i=1,i =2

⊓ ⊔