Jean-Florent Raymond
email: jean-florent.raymond@ens-lyon.org

Dimitrios M Thilikos

Low Polynomial Exclusion of Planar Graph Patterns

Keywords:

The celebrated grid exclusion theorem states that for every h-vertex planar graph H, there is a constant c h such that if a graph G does not contain H as a minor then G has treewidth at most c h . We are looking for patterns of H where this bound can become a low degree polynomial. We provide such bounds for the following parameterized graphs: the wheel (c h = O(h)), the double wheel (c h = O(h 2 • log 2 h)), any graph of pathwidth at most 2 (c h = O(h 2 )), and the yurt graph (c h = O(h 4 )).

Introduction

Treewidth is one of the most important graph invariants in modern graph theory. It has been introduced in [START_REF] Robertson | Graph minors. II. algorithmic aspects of tree-width[END_REF] by Robertson and Seymour as one of the cornerstones of their Graph Minors series. Apart from its huge combinatorial value, it has been extensively used in graph algorithm design (see [START_REF] Hans | A partial k-arboretum of graphs with bounded treewidth[END_REF] for an extensive survey on treewidth). On an intuitive level, treewidth expresses how close the topology of the graph is to that of a tree and, in a sense, can be seen as a measure of the "global connectivity" of a graph.

Formally, a tree decomposition of a graph G is a pair (T, X ) where T is a tree and X a family (X t ) t∈V (T ) of subsets of V (G) (called bags) indexed by elements of V (T ) and such that (i) t∈V (T ) X t = V (G);

(ii) for every edge e of G there is an element of X containing both ends of e;

(iii) for every v ∈ V (G), the subgraph of T induced by {t ∈ V (T ) | v ∈ X t } is connected.

The width of a tree decomposition is equal to max t∈V (T ) |X t | -1, while the treewidth of G, written tw(G), is the minimum width of any of its tree decompositions. Similarly one may define the notions of path decomposition and pathwidth by additionally asking that T is a path (see Section 2).

We say that a graph H is a minor of a graph G if a graph isomorphic to H can be obtained from a subgraph of G by applying a series of edge contractions, and we denote this fact by H m G.

1

The grid exclusion theorem. One of the most celebrated results from the Graph Minors series of Robertson and Seymour is the following result, also known as the grid exclusion theorem.

Proposition 1 ([22]

). There exists a function f : N → N such that, for every for every planar graph H on h vertices, every graph G that does not contain a minor isomorphic to H has treewidth at most f (h).

The original proof the the above result in [START_REF] Robertson | Graph minors. V. Excluding a planar graph[END_REF] did not provided any explicit estimation for the function f . Later, in [START_REF] Robertson | Quickly excluding a planar graph[END_REF], Robertson, Seymour, and Thomas proved the same result for f (h) = 2 O(h 5 ) , while a less complicated proof appeared in [START_REF] Diestel | Highly connected sets and the excluded grid theorem[END_REF]. The bound f (h) h -2 was also obtained in [START_REF] Bienstock | Quickly excluding a forest[END_REF] in the case where H is required to be a forest.

For a long time, whether Proposition 1 can be proved for a polynomial f was an open problem. In [START_REF] Robertson | Quickly excluding a planar graph[END_REF], an Ω(h 2 • log h) lower bound was provided for the best possible estimation of f and was also conjectured that the optimal estimation should not be far away from this lower bound. In fact, a more precise variant of the same conjecture was given by Demaine, Hajiaghayi, and Kawarabayashi in [START_REF] Demaine | Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction[END_REF] where they conjectured that Proposition 1 holds for f (h) = O(h 3 ). The bounds of [START_REF] Robertson | Quickly excluding a planar graph[END_REF] were recently improved by Kawarabayashi and Kobayashi [START_REF] Ichi | Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid[END_REF], where they show that Proposition 1 holds for f (h) = 2 O(h•log h) . The same bounds were obtained by Leaf and Seymour [START_REF] Leaf | Treewidth and planar minors[END_REF]. Until recently, this was the best known estimation of the function f .

Very recently, in a breakthrough result [START_REF] Chekuri | Polynomial bounds for the grid-minor theorem[END_REF], Chekuri and Chuzhoy proved that Proposition 1 holds for f (h) = O(h 228 ). The remaining open question is whether the degree of this polynomial bound can be substantially reduced in general. In this direction, one may still consider restrictions either on the graph G or on the graph H that yield a low polynomial dependence between the treewidth and the size of the excluded minor. In the first direction, Demaine and Hajiaghayi proved in [START_REF] Demaine | Linearity of grid minors in treewidth with applications through bidimensionality[END_REF] that, when G is restricted to belong in some graph class excluding some fixed graph R as a minor, then Proposition 1 (optimally) holds for f (h) = O(h). Similar results have been proved by Fomin, Saurabh, and Lokshtanov, in [START_REF] Fedor | Bidimensionality and geometric graphs[END_REF], for the case where G is either a unit disk graph or a map graph that does not contain a clique as a subgraph.

In a second direction, one may consider H to be some specific planar graph and find a good upper bound for the treewidth of the graphs that exclude it as a minor. More generally, we can consider a parametrized class of planar graphs H k where each graph in H k has size bounded by a polynomial in k, and prove that the following fragment of Proposition 1 holds for some low degree polynomial function f : N → N:

∀k 0 ∀H ∈ H k , if H m G then tw(G) f (k). (1)
The question can be stated as follows: find pairs (H k , g(k)) for which (1) holds for some

f (k) = O(g(k)
, where H k is as general as possible and g is as small as possible (and certainly polynomial). It is known, for example, that (1) holds for the pair ({C k }, k), where C k is the cycle or a path of k vertices (see e.g. [START_REF] Hans | On linear time minor tests with depth-first search[END_REF][START_REF] Michael | On search, decision, and the efficiency of polynomial-time algorithms[END_REF]), and for the pair ({K 2,k }, k), (see [START_REF] Hans | On interval routing schemes and treewidth[END_REF]). Two more results in the same direction that appeared recently are the following: according to the result of Birmelé, Bondy, and Reed in [START_REF] Birmelé | Brambles, prisms and grids[END_REF], (1) holds for the pair (P k , k 2 ) where P k contains all minors of K 2 × C k (we denote by K 2 × C k the Cartesian product of K 2 and the cycle of k vertices, also known as the k-prism). Finally, one of the consequences of the recent results of Leaf and Seymour in [START_REF] Leaf | Treewidth and planar minors[END_REF], implies that (1) holds for the pair (F r , k), where F r contains every graph on r vertices that contains a vertex that meets all its cycles.

Our results. In this paper we provide polynomially bounded minor exclusion theorems for the following parameterized graph classes:

H 0 k : containing all graphs on k vertices that have pathwidth at most 2. H 1 k : containing all minors of a wheel on k + 1 vertices -see Figure 1.

H 2 k : containing all minors of a double wheel on k + 2 vertices -see Figure 1.

H 3 k : containing all minors of the yurt graph on 2k + 1 vertices (i.e. the graph obtained it we take a (2 × k)-grid and add a new vertex adjacent with all the vertices of its "upper layer" -see Figure 4).

Notice that none of the above classes is minor comparable with the classes P k and F k treated in [START_REF] Birmelé | Brambles, prisms and grids[END_REF] and [START_REF] Leaf | Treewidth and planar minors[END_REF]. Moreover, H 1 k ⊂ H 2 k ⊂ H 3 k , while H 0 k is not minor comparable with the other three. In this paper we prove that (1) holds for the pairs:

• (H 0 k , k 2 ), • (H 1 k , k), • (H 2 k , k 2 log 2 n), and
• (H 3 k , k 4 ).
The above results are presented in detail, without the O-notation, in Section 3. All of our proofs use as a departure point the results of Leaf and Seymour in [START_REF] Leaf | Treewidth and planar minors[END_REF].

Definitions

All graphs in this paper are finite and simple, i.e., do not have loops nor multiple edges. We denote by V (G) (resp. E(G)) the sets of vertices (resp. edges) of G. For every i, j ∈ N, i j, the notation i, j stands for the interval of integers {i, i + 1, . . . , j}. Logarithms are binary.

Definition 1 (path decomposition, pathwidth). A path decomposition of a graph G is a tree decomposition T of G such that T is a path. Its width is the width of the tree decomposition T and the pathwidth of G, written pw(G), is the minimum width of any of its path decompositions. An optimal path decomposition is a path decomposition of minimum width.

Definition 2 (contraction and dissolution). The contraction of an edge {u, v} in a graph G is the operation which creates a new vertex adjacent to the neighbors of u and those of v, and deletes both u and v. The dissolution of a vertex of degree two is the contraction of one of the edges incident with it.

Definition 3 (minor model). A minor model (sometimes abbreviated model ) of a graph H in a graph G is a pair (M, ϕ) where M is a set of pairwise disjoint subsets of Definition 6 (left-contains, [START_REF] Leaf | Treewidth and planar minors[END_REF]). Let H be a graph on r vertices, G a graph and (A, B) a separation of order r in G. We say that (A, B) left-contains

V (G) such that ∀X ∈ M, G [X] is connected and ϕ : V (H) → M is a bijection that satisfies ∀{u, v} ∈ E(H), ∃u ∈ ϕ(u), ∃v ∈ ϕ(v), {u , v } ∈ E(G).
H if G [A] contains a minor model M of H such that ∀M ∈ M, |M ∩ (A ∩ B)| = 1
Definition 7 (Trees and cycles). Given a tree T we denote by L(T ) the set of its leaves, i.e. vertices of degree 1 and by diam(T ) its diameter, that is the maximum length (in number of edges) of a path in T.

For every two vertices u, v ∈ V (T ), there is exactly one path in T between u and v, that we denote by uT v. Also, given that uT v has at least 2 vertices, we denote by ůT v (resp. uTv) the path uT v with the vertex u (resp. v) deleted.

Let C be a cycle on which we fixed some orientation. Then, there is exactly one path following this orientation between any two vertices u, v ∈ V (C). Similarly, we denote this path by uCv and we define ůCv and uCv as we did for the tree.

In a rooted tree T with root r, the least common ancestor of two vertices u and v, written lca T (u, v) is the first common vertex of the paths uT r and vT r. We refer to the root of T by the notation root(T ).

For every integer h > 0, we denote by B h the complete binary tree of height h.

Results

We present in this paper bounds on the treewidth of graphs not containing the following parameterized graphs: the wheel of order k (section 5), the double wheel of order k (section 6), any graph on k vertices and pathwidth at most 2 (section 7) and the yurt graph of order k (section 8). The definitions of these graphs can be found in the corresponding sections. In section 4, we recall some propositions that we will use and we prove two lemmata which will be useful later. The theorems we then prove are the following.

Theorem 1. Let k > 0 be an integer and G be a graph. If tw(G) 36k -2, then G contains a wheel of order k as minor.

Theorem 2. Let k > 0 be an integer and G be a graph. If tw(G) 12(8k log(8k) + 2) 2 -4, then G contains a double wheel of order at least k as minor.

Theorem 3. Let k > 0 be an integer, G be a graph and H be a graph on k vertices and of pathwidth at most 2. If tw(G) 3k(k -4) + 8 then G contains H as minor.

Theorem 4. Let k > 0 be an integer and G be a graph. If tw(G) 6k 4 -24k 3 +48k 2 -48k +23, then G contains the yurt graph of order k as minor.

Preliminaries

Proposition 2 ([18, (4.3)]). Let k > 0 be an integer, let F be a forest on k vertices and let G be a graph.

If tw(G) 3 2 k -1, then G has a separation (A, B) of order k such that • G [B \ A] is connected; • A ∩ B is linked in G [B]; • (A, B) left-contains F .
Proposition 3 (Erdős-Szekeres Theorem, [START_REF] Erdős | A combinatorial problem in geometry[END_REF]). Let k and be two positive integers. Then any sequence of ( -1)(k -1) + 1 distinct integers contains either an increasing subsequence of length k or a decreasing subsequence of length .

+ 1.

Proof. Root T to a vertex r ∈ V (T ) that is halfway of a longest path of T . For each leaf

x ∈ L(T ), we know that |V (xTr)| diam(T ) 2 . Observe that V (T ) = {r} ∪ x∈L(T ) V (xTr). Therefore, |V (T )| x∈L(T ) |V (xTr)| + 1 |V (T )| |L(T )| • diam(T ) 2 + 1.
Notice that equality holds for the subdivided star (obtained from K 1,n by subdividing k times every edge, for some n, k ∈ N).

Definition 8 (The set Λ(T )). Let T be a tree. We denote by Λ(T ) the set containing every graph obtained as follows: take the disjoint union of T , a path P where |V (P )| |L(T )|, and an extra vertex v new , and add edges such that (i) there is an edge between v new and every vertex of P ;

(ii) there are |V (P )| disjoint edges between P and L(T );

(iii) there are no more edges than the edges of T and P and the edges mentioned in (i) and (ii).

Lemma 2. Let n 1 be an integer, T be a tree on n vertices an let G be a graph.

If tw(G) 3n -1, then H m G for some H ∈ Λ(T ).
Proof. Let n, T , and G be as in the statement of the lemma. Let l be the number of leaves of T , and let J be a path on l vertices. We consider the disjoint union of J and T .

The graph G has treewidth at least 3 2 (n + l) -1, then by Proposition 2, G has a separation (A, B) of order n + l such that

(i) G [B \ A] is connected; (ii) A ∩ B is linked in G [B] ; (iii) (A, B) left-contains the graph J ∪ T . Let (M, ϕ) be the a model of J ∪ T in G [A] that witnesses (iii).
We call the vertices of A ∩ B that belong to ϕ(v) for some v ∈ V (J) the J-part, and vertices that belong to ϕ(v) for some v ∈ L(T ) forms the L(T )-part. Notice that two distinct vertices of the J-part (resp. L(T )-part) will be contracted to distinct vertices by the model.

Let P a set of l disjoint paths with the one endpoint in the J-part and the other in the L(T )-part, and whose interior belongs to B \ A. The existence of such paths is given by (ii). For each P ∈ P, we arbitrarily choose a vertex v P of the interior of P , that is, v P ∈ V (P ) \ A. By (i), G [B \ A] is connected: let Y be a smallest tree spanning the vertices {v P } P ∈P . Let s = |L(T )|, and let Y * be the tree obtained from Y by dissolving every vertex of degree two that is not v P for some P ∈ P. We are now facing two possible situations. Case 1: Y * has a path of length s. Let Q be the path of Y corresponding to a path of lenght s in Y * and let S be the set of vertices u ∈ V (Q) that are not of degree two or that are v P for some P ∈ P. Observe that from every u ∈ S, there is a path J u to the L(T )-part and a path J u to the J-part. Indeed, if u = v P for some P ∈ P, then u is a vertex of P linking (by definition) a vertex of the L(T )-part to a vertex of the J-part. Otherwise, u is of degree at least 3 in Y and every leaf of the subtrees of Y \ Q (at least one of which is adjacent to u), is a v P for some P ∈ P (by minimality of Y ), so is connected to the L(T )-part and the J-part as explained above. Furthermore, for every two distinct u, v ∈ S, the aforementioned path are disjoint.

Let us now summarize. G ∪ v∈V (J) ϕ(v) is a connected subgraph of G, which is connected by the s disjoint paths J uu∈S to the path Y . All the endpoints of the paths J uu∈S on Y are connected by s disjoint paths J uu∈S to the L(T )-part, which correspond to the leaves in a model of T . Therefore this graph contains a member of Λ(T ) as a minor, as required.

Case 2: diam(Y * ) < s. From Lemma 1, |L(Y )| = |L(Y * )| s.
Observe that L(Y ) ⊆ {v P } P ∈P (this follows by the minimality of Y ). Let S = V (Y ) \ L(Y ). We consider the minor of G obtained by contracting, for every P ∈ P such that v P ∈ L(Y ), every edge of the subpath connecting the J-part to a leaf of Y . In this graph, S induces a connected subgraph adjacent to at least s distinct vertices of the J-part. All these s vertices of the J-part are connected by s disjoint paths to distinct vertices of the L(T )-part. Thus this contains a member of Λ(T ) as a minor, and so do G.

5 Excluding a wheel with a linear bound on treewidth Definition 9 (wheel). Let r > 2 be an integer. The wheel of order r (denoted W r ) is a cycle of length r whose each vertex is adjacent to an extra vertex, in other words it is a the graph of the form

V (G) = {o, w 1 , . . . , w r } E(G) = {{w 1 , w 2 } , {w 2 , w 3 } , . . . , {w r-1 , w r } , {w r , w 1 }} ∪ {{o, w 1 } , .
. . , {o, w r }} (see Figure 1 for an example). Lemma 3. Let h > 2 be an integer. Let G be a graph obtained from the union of the tree T = B h and a path P by adding the edges {l, ψ(l)} ∈ E(G) for every l ∈ L(T ), where ψ : L(T ) → V (P ) is a bijection. Then G contains a wheel of order 2 h-2 + 1 as a minor.

Proof. Let h, ψ, T , P = p 1 . . . p 2 h and G be as above. Let r be the root of T .

In the arguments to follow, if t ∈ V (T ), we denote by T t the subtree of T rooted at t (i.e. the subtree of T whose vertices are all the vertices t ∈ V (T ) such that the path t T r contains t).

We consider the vertices

u = ψ -1 (p 1 ) ∈ L(T ) and v = ψ -1 (p 2 h ) ∈ L(T ) and w = lca T (u, v) ∈ V (T ) \ L(T ).
Let τ be a largest subtree of T which is disjoint from uT v. Let L τ = L(τ ) ∩ L(T ) and let Q = ψ(L τ ) ⊆ P . It is not hard to see that G contains W |Q|+1 as a minor. Indeed, the paths P and uT v together with the edges {p 1 , u} and {p 2h , v} form a cycle in G. Besides, the tree τ , which is disjoint from this cycle, has at least |Q| + 1 vertices that are adjacent to distinct vertices of P : |Q| of them are the elements of Q, and the other one is the (only) vertex of τ adjacent to uT v (which exists by maximality of τ ). In the subgraph of G induced by V (P ) ∪ V (uT v) ∪ V (τ ), contracting τ to a vertex gives a vertex adjacent to at least |Q| + 1 vertices of a (non necessarily induced) cycle, a graph containing W |Q|+1 as subgraph.

Depending on G, |Q| may take different values. However, we show that it is never less than 2 h-2 . Remember, |Q| is the number of leaves that a largest subtree of T that is disjoint from uT v shares with T . The root r of T has two children r 1 and r 2 , inducing two subtrees T r1 and T r2 of T . Recall, w = lca T (u, v).

Case 1. w = r. As w = r, w is a vertex of one of {T r1 , T r2 }, say T r1 , which contains also u and v, and thus the path uT v. The other subtree T r2 is then disjoint from uT v, it has height h -1 and is complete so it has 2 h-1 leaves. Consequently, in this case |Q| 2 h-1 .

Case 2. w = r. In this case, the path uT v contains r (and r = u, r = v as u and v are leaves) so u and v are not in the same subtree of {T r1 , T r2 } and uT v contains the two edges {r, r 1 } and {r, r 2 }. For every i ∈ {1, 2}, we denote by r i,1 and r i,2 the two children of r i in T . We assume without loss of generality that u ∈ V (T r1,1 ) and v ∈ V (T r2,1 ) (if not, we just rename the r i 's ans r i,j 's). Notice that the path uT v is the concatenation of the paths

uT r1 r 1 , r 1 T r 2 , r 2 T r2 v. Since the tree T r1,2 is disjoint from uT v, is complete and is of height h -2, it has 2 h-2 leaves. Therefore we have |Q| 2 h-2 .
In both cases, |Q| 2 h-2 and according to what we proved before, G contains a model of W |Q|+1 . As every wheel contains as a minor every smaller wheel, we proved that G contains a wheel of order at least 2 h-2 . Theorem 5. Let k > 0 be an integer and G be a graph. If tw(G) 36k -2, then G contains a W k -model.

Proof. Let k > 0 be an integer, G be a graph such that tw(G) 36k -2, and let h = log 4k . Since every wheel contains a model of every smaller wheel, we have

W k m W 2 log k +1 m W 2 (log 4k)-2 +1 m W 2 h-2 +1
Therefore, if we prove that G contains a W 2 h-2 +1 -model, then we are done because the minor relation is transitive. Let Y - h be the graph of the following form: the disjoint union of the complete binary tree B h of height h with leaves set Y L and of the path Y P on 2 h vertices, and let Y h be the set of graphs of the same form, but with the extra edges {{l, φ(l)}} l∈Y L , where φ : Y L → V (Y P ) is a bijection. As we proved in Lemma 3 that every graph in Y h contains the wheel of order 2 h-2 + 1 as minor, showing that G contains an element of Y h as minor suffices to prove this lemma. That is what we will do.

From our initial assumption, we deduce the following.

tw(G) 36k - 5 2 3 2 (3 • 2 log 8k -1) -1 3 2 (3 • 2 log 4k +1 -1) -1 tw(G) 3 2 (3 • 2 h -1) -1
According to Proposition 2, G has a separation (A, B) of order 3

• 2 h -1 such that (i) G [B \ A] is connected; (ii) A ∩ B is linked in G [B]; (iii) (A, B) left-contains the graph Y - h . By definition of left-contains, G [A] contains a model (M -, ϕ -) of Y -
h and every element of M -contains exactly one element of A ∩ B. For every x ∈ A ∩ B, we denote by M -

x the element of M -that contains x. Let L (resp. R) be the subset of A ∩ B of vertices that belong to an element of M related to the leaves of B h in Y - h (resp. to the path P ). We remark that these sets are both of cardinality 2 h .

Since

A ∩ B is linked in G [B] (see (ii)
), there is a set P of 2 h disjoint paths between the vertices of L and the elements of R. Let ψ : L → V (P ) be the function that match each element l of L with the (unique) element of R it is linked to by a path (that we call P l ) of P. Observe that ψ is a bijection. We set

∀l ∈ L, M l = M - l ∪ V (lP l ψ(l)) ∀r ∈ (A ∩ B) \ L, M r = M - r M = x∈A∪B M x .
Let us show that M allows us to define a model of some H ∈ Y h . Let us consider the following mapping.

ϕ : V (Y - h ) → M x → M x
We claim that (M, ϕ) is a model of H for some H ∈ Y h . This is a consequence of the following remarks.

Remark 1. Every element of M is either an element of M -, or the union of a element M of M -and of the vertices of a path that start in M , thus every element of M induces a connected subgraph of G.

Remark 2. The paths of P are all disjoint and are disjoint from the elements of M -. Every interior of path of P is in but one element of M, therefore the elements of M are disjoint.

Remark 3. The elements {m l } l∈L are in bijection with the elements of {m r } r∈R (thanks to the function ψ) and every two vertices l ∈ L and ψ(l) ∈ R are such that there is an edge between m l and m ψ(l) (by definition of M + ).

We just proved that (M, ϕ) is a model of a graph of Y h in G. Finally, we apply Lemma 3 to find a model of the wheel of order 2 h-2 + 1 = 2 log k -2 + 1 k in G and this concludes the proof.

6 Excluding a double wheel with a (l log l) 2 bound on treewidth Definition 10 (double wheel). Let r > 2 be an integer. The double wheel of order r (denoted W 2 r ) is a cycle of length r whose each vertex is adjacent to two different extra vertices, in other words it is the graph of the form

V (G) ={o 1 , o 2 , w 1 , . . . , w r } E(G) ={{w 1 , w 2 } , {w 2 , w 3 } , . . . , {w r-1 , w r } , {w r , w 1 }} ∪ {{o 1 , w 1 } , . . . , {o 1 , w r }} ∪ {{o 2 , w 1 } , .
. . , {o 2 , w r }} (see Figure 1 for an example). Proof. Let h and G be as above. Observe that tw(G)

3(2 h+1 -1) -1. As the binary tree T = B h has 2 h+1 -1 vertices, G contains a graph H ∈ Λ(B h ) as minor (by Lemma 2). Let us show that any graph H ∈ Λ(B h ) contains a double wheel of order at least 2 We also define u (resp. u ) as the vertex of L(T ) that is adjacent to one end of P (resp. to the other end of P ) and Q = uT u .

As T is a binary tree of height h, Q has at most 2h -1 vertices. Each vertex of Q is of degree at most 3 in T except the two ends which are of degree 1. Consequently, T \ Q has at most 2h -3 connected components that are subtrees of T. Notice that every vertex of the 2 h 2 elements of L is either a leaf of one of these 2h -3 subtrees, or one of the two ends of Q. By the pigeonhole principle, one of these subtrees, which we call T 1 , has at least 2 Let M o1 be the set of vertices of this subtree T 1 . We also set M o2 = {v new } (cf. Definition 8 for a definition of v new ). Let us consider the cycle C made by the concatenation of the paths uP u and u T u in H.

By definition of M o1 , there are at least

2 h 2 -2
2h-3 vertices of C adjacent to vertices of M o1 . Let J = j 1 , . . . , j |J| be the set of such vertices of C, in the same order as they appear in C (we

then have |J| 2 h 2 -2 2h-3 ).
We arbitrarily choose an orientation of C and define the sets of vertices M 1 , M 2 , . . . , M |J| as follows.

∀i ∈ 1, |J| -1 , M i = V (j i C j i+1 ) M |J| = V (j |J| C j1 ) Let M = M 1 , . . . , M |J| , M o1 , M o2 and ψ : V (W 2 |J| ) → M be the function defined by ∀i ∈ 1, |J| , ψ(w i ) = M i ψ(o 1 ) = M o1 ψ(o 2 ) = M o2
Notice that ψ maps the vertices of W

Our initial assumption on tw(G) gives the following.

tw(G) 12l -4 6 • 2 log(2l) -4 6 • 2 log l+1 -4 6 • 2 log l -4 by (2)
By Lemma 4, G contains a double wheel of order at least

q = 2 log l 2 -2 2 log l -3 2 1 2 log l -2 2(log l -1) -3 by (2) √ l -2 2 log l -5
Therefore, G contains a double wheel of order q √ l-2 2 log l-5 , as required.

Theorem 6 (follows from Corollary 1). Let k > 0 be an integer and G be a graph. If tw(G) 12(8k log(8k) + 2) 2 -4, then G contains a double wheel of order at least k as minor.

Proof. Applying Corollary 1 for l = (8k log(8k) + 2) 2 yields that G contains a double wheel of order at least q √ l -2 2 log l -5 8k log(8k) 4 log(8k log(8k) + 2) -5 8k log(8k) 4 log(8k log(8k)) -1 8k log(8k) 4(log(8k) + log log(8k)) -1 8k log(8k) 8 log(8k) -1 k Consequently G contains a double wheel of order q k and we are done.

Excluding a graph of pathwidth at most 2 with a quadratic bound on treewidth

Definition 11 (graph Ξ r ). We define the graph Ξ r as the graph of the following form (see figure 2).

V (G) = {x 0 , . . . , x r-1 , y 0 , . . . , y r-1 , z 0 , . . . , z r-

1 } E(G) = {{x i , x i+1 } , {z i , z i+1 }} i∈ 1,r-1 ∪ {{x i , y i } , {y i , z i }} i∈ 0,r-1 z0 z1 z2 z3 z4 y0 y1 y2 y3 y4 x0 x1 x2 x3 x4
Figure 2: The graph Ξ 5

Graphs of pathwidth 2 in Ξ r

Instead of proving that having a graph H of pathwidth 2 as minor forces a treewidth quadratic in |V (H)|, we prove that a Ξ r -minor forces a treewidth quadratic in r and that every graph of pathwidth at most 2 on r vertices is minor of Ξ r . For this, we first need some lemmata and remarks about path decompositions.

Definition 12 (nice path decompostion, [START_REF] Kloks | Computations and Approximations[END_REF]). A path decomposition p 1 p 2 . . . p k , {X pi } i∈ 1,k of a graph G is said to be nice if

|X p1 | = 1 and ∀i ∈ 2, k , (X pi \ X pi-1 ) ∪ (X pi-1 \ X pi ) = 1
It is known [START_REF] Hans | Computing small search numbers in linear time[END_REF] that every graph have an optimal path decomposition which is nice and that in such decomposition, every node X i is either an introduce node (i.e. either i = 1 or X pi \ X pi-1 = 1) or a forget node (i.e. X pi-1 \ X pi = 1).

Remark 4. It is easy to observe that for every graph G on n vertices, there is an optimal path decomposition with n introduce nodes and n forget nodes (one of each for each vertex of G), thus of length 2n.

Remark 5. Let G be a graph and let (p 1 p 2 . . . p k , X ), X = {X pi } i∈ 1,k be a nice (non necessarly optimal) path decomposition of G. Let w be the width of this decomposition. For every i ∈ 2, k -1 , if p i is a forget node, |X pi | w -1 and p i+1 is an introduce node, then by setting

X pi = X pi-1 ∪ X pi+1 ∀j ∈ 1, k , j = i, X pj = X pj X = X pj j∈ 1,k
we create from (p 1 p 2 . . . p k , X ) a valid path decomposition of G, where p i is now an introduce node and p i+1 a forget node. Observe that X pi X pi + 2 = w + 1 Therefore the new path decomposition the same width as the original one. Note that the condition |X pi | w -1 holds, for instance, when p i-1 is required to be a forget node too (for i ∈ 3, k -1 ). Remark 6. Let G be a graph and P = (p 1 p 2 . . . p k , X ) be a nice path decomposition of G. For every i ∈ 1, k , the path p 1 . . . p i contains at most as many forget nodes as introduce nodes and the difference between these two numbers is at most w + 1 where w is the width of P.

Lemma 5. Let G be a graph on n vertices . Then G has an optimal path decomposition P such that (i) every bag of P has size pw(G) + 1;

(ii) every two adjacent bags differs by exactly one element, i.e. for every two adjacent vertices u and

v of P , |X u \ X v | = |X v \ X u | = 1.
Proof. Let P = (p 1 p 2 . . . p 2k , X ) with X = {X pi } i∈ 1,2k be a nice optimal path decomposition of G with as many introduce nodes (resp. forget nodes) as there are vertices in G.

Let s = pw(G) + 1. According to Remarks 5 and 6, P can be modified into a path decomposition of G of the same width and such that (a) the s first vertices of P are introduce nodes and p s+1 is a forget node;

(b) the s last vertices of P are forget nodes and p 2k-s is an introduce node; (c) for every i ∈ s, 2k -s , p i and p i+1 are nodes of different type.

In the arguments to follow, we assume that P satisfies this property.

Remark 7. Introduce nodes all have bags of cardinality s. Remark 8. For every i ∈ 0, k -s , the node p s+2i is an introduce node and the node p s+2i+1 is a forget node, which implies X ps+2i X ps+2i+1 . Also note that for every i ∈ 1, s -1 , X pi X ps and for every i ∈ 2k -s + 1, 2k , X pi X p 2k-s .

Intuitively, every bag X that is included in one of its adjacent bags X contains no more information than what X already contains, so we will just remove it.

We thus define P = p s p s+2 . . . p s+2i . . . p 2k-s (a path made of all introduce nodes of P ). Clearly, P and P have the same width and as we deleted only redundant nodes, P is still a valid path decomposition of G.

Since every two adjacent nodes of P were introduce nodes separated by a forget node in P , they only differ by one element. According to Remark 7 and since every node of P was an introduce node in P , every bag of P have size pw(G) + 1. Consequently, P is an optimal path decomposition that satisfies the conditions of the lemma statement.

Remark 9. The path decomposition of Lemma 5 has length V (G) -pw(G).

Proof. Let (P, X ) be such a path decomposition. Remember that the first node of P has a bag of size pw(G) + 1 and that every two adjacent nodes of P have bags which differs by exactly one element. Since every vertex of G is in a bag of P , in addition to the first bag containing pw(G) + 1 vertices of G, P must have V (G) -pw(G) -1 other bags in order to contain all vertices of G. Therefore P has length V (G) -pw(G).

A proof of a slightly weaker version of the following lemma previously appeared [START_REF] Proskurowski | Maximal Graphs of Path-width K Or Searching a Partial K-caterpillar[END_REF]. Lemma 6. For every graph G on n vertices and of pathwidth at most 2, there is a minor model of G in Ξ n-1 .

Proof. Let G be as in the statement of the lemma. We assume that pw(G) = 2 (if this is not the case we add edges to G in order to obtain a graph of pathwidth 2 which contains G as a minor). Let r = V (G) -pw(G) = n -2.

Let P = (p 1 . . . p r , {X p1 , . . . , X pr }) be an optimal path decomposition of G satisfying the properties of Lemma 5, of length r. Such decomposition exists according to Lemma 5 and Remark 9).

Using this decomposition, we will now define a labeling λ of the vertices of Ξ r+1 . When dealing with the vertices of Ξ r+1 we will use the notations defined in Definition 11. Let λ : V (Ξ r+1 ) → V (G) be the function defined as follows:

(a) λ(x 0 ) and λ(y 0 ) are both equal to one (arbitrarily chosen) element of the set X p1 ∩ X p2 ;

(b) λ(z 0 ) is equal to the only element of the set X p1 ∩ X p2 \ {λ(x 1 )};

(c) ∀i ∈ 2, r , λ(y i ) = X pi \ X pi-1 and we consider two cases:

Case 1: X pi-1 ∩ X pi = X pi ∩ X pi+1 λ(x i ) = λ(x i-1 ) and λ(z i ) = λ(z i-1 ); Case 2: X pi-1 ∩ X pi = X pi ∩ X pi+1 if X pi-1 ∩ X pi ∩ X pi+1 = λ(x i-1 ), then λ(x i ) = λ(x i-1 ) and λ(z i ) = X pi \ X pi-1 ; else λ(x i ) = X pi \ X pi-1 and λ(z i ) = λ(z i-1 ).
Thanks to this labeling, we are now able to present a minor model of G in Ξ r+1 :

∀v ∈ V (G), M v = {u ∈ V (Ξ r+1 ), λ(u) = v} M = {M v } v∈V (G) ϕ : V (G) → M u → M u
To show that (M, ϕ) is a G-model in Ξ r+1 , we now check if it matches the definition of a minor model.

By definition, every element of M is a subset of V (Ξ r+1 ). To show that every element of M induces a connected subgraph in G, it suffices to show that nodes of Ξ r+1 which have the same label induces a connected subgraph in G (by construction of the elements of M). This can easily be seen by remarking that for every i ∈ 2, r , every vertex y i of Ξ r+1 gets a new label and that every vertex x i (resp. z i ) of Ξ r+1 receive either the same label as y i , or the same label as x i-1 (resp. z i-1 ).

Let us show that this labeling ensure that if two vertices u and v of G are in the same bag of P , there are two adjacent vertices of Ξ r+1 that respectively gets labels u and v. Let u, v be two vertices of G which are in the same bag of P . Let i be such that X i is the first bag of P (with respect to the subscripts of the bags of P ) which contains both u and v. The case i = 1 is trivial so we assume that i > 1. We also assume without loss of generality that X i \ X i-1 = {v}, what gives λ(y i ) = v. Depending on in what case we are, either either λ(x i ) = u (c1) or λ(z i ) = u (c1 and c2). In both cases, u and v are the labels of two adjacent nodes of Ξ r+1 . By construction of the elements of M, this implies that if {u, v} ∈ E(G), then there are vertices u ∈ ϕ(u) and v ∈ ϕ(v) such that {u , v } ∈ E(Ξ r+1 ).

Therefore, (M, ϕ) is a G-model in Ξ n-1 , what we wanted to find.

Exclusion of Ξ r

Lemma 7. For any graph, if tw(G) 3 -1 then G contains as minor the following graph: a path P = p 1 . . . p 2 of length 2 and a family Q of paths of length 2 such that every vertex of P is the end of exactly one path of Q and every path of Q has one end in p 1 . . . p l (the first half of P ) and the other end in p l+1 . . . p 2l (the second half of P ) (see figure 3). Proof. Let > 0 be an integer and G be a graph of treewidth at least 3 -1. According to Proposition 2, G has a separation (A, B) of order 2 such that

(i) G [B \ A] is connected; (ii) A ∩ B is linked in G [B];
(iii) (A, B) left-contains a path P = p 1 . . . p 2 of length 2 .

Let (M, ϕ) be a model of P in G [A] , with M = {M 1 , . . . , M 2 }. We assume without loss of generality that ϕ maps p i to M i for every i ∈ 1, 2 .

As

A ∩ B is linked in G [B], there is a set Q of disjoint paths in G [B]
of length at least 2 and such that every path q ∈ Q has one end in (A ∩ B) ∩ i∈ 1, M i , the other end in (A ∩ B) ∩ i∈ +1,2 M i and its internal vertices are not in A ∩ B.

Let G be the graph obtained from G q∈Q V (q) ∪ M ∈M M after the following operations.

1. iteratively contract the edges of every path of Q until it reaches a length of 2. The paths of Q have length at least 2, so this is always possible.

2. for every i ∈ 1, 2 , contract M i to a single vertex. The elements of a model are connected (by definition) thus this operation can always be performed.

As one can easily check, the graph G is the graph we were looking for and it has been obtained by contracting some edges of a subgraph of G, therefore G m G.

Theorem 7. Let G be a graph and H be a graph on h vertices satisfying pw(H)

2. If tw(G) 3(h -2) 2 -1 then G contains H as a minor.
Proof. Let G, H and h be as in the statement of the Lemma. According to Lemma 6, every graph of pathwidth at most two on n vertices is minor of Ξ n-1 . Therefore in order to show that G m H it is enough to prove that G m Ξ h-1 . This is what we will do.

According to Lemma 7, G contains as minor two paths P = p 1 . . . p (h-2) 2 and R = r 1 . . . r h-2) 2 and a family Q of (k -2) 2 paths of length 2 such that every vertex of P or R is the end of exactly one path of Q and every path of Q has one end in P and the other end in R. For every p ∈ P , we denote by ϕ(p) the (unique) vertex of R to which p is linked to by a path of Q. Observe that ϕ is a bijection. By Proposition 3, there is a subsequence P = (p 1 , p 2 , . . . , p h-1 ) of the vertices of P such that the vertices ϕ(p 1 ), ϕ(p 2 ), . . . , ϕ(p h-1 ) appear in R either in this order or in the reverse order. Let R = (ϕ(p 1 ), ϕ(p 2 ), . . . , ϕ(p h-1 )) and Q be the set of inner vertices of the paths from p i to ϕ(p i ) for all i ∈ 1, h -1 .

Iteratively contracting in Gwhich have at most one end in P (resp. in R ) and removing the vertices that are not in P , R or Q gives the graph Ξ h-1 . The operations used to obtain it are vertices and edge deletions, and edge contractions, thus Ξ h-1 is a minor of G. This concludes the proof.

8 Excluding a yurt graph Definition 13 (yurt graph of order r). Let r > 0 be an integer. In this paper, we call yurt graph of order r the graph Y r of the form V (Y r ) = {x 1 , . . . , x r , y 1 , . . . , y r , o} E(Y r ) = {x i , x i+1 } i∈ 1,r-1 ∪ {y i , y i+1 } i∈ 1,r-1 ∪ {{x i , y i }} i∈ 1,r ∪ {{y i , o}} i∈ 1,r (see Figure 4 for an example). For every r > 0, we define the comb of order r as the tree made from the path p 1 p 2 . . . p r and the extra vertices v 1 , v 2 , . . . , v r by adding an edge between p i and v i for every i ∈ 1, r . Let us prove that every graph of Λ(C) contains the yurt graph of order k. Let H be a graph of Λ(C). We respectively call T , P and o the tree, path and extra vertex of Λ(C). Let F be the subset of edges between P and the leaves of T Let L = l 0 , . . . , l k 2 -2k+2 (resp. Q = q 0 , . . . , q k 2 -2k+2 ) be the leaves of T (resp. of P )that are the end of an edge of F We assume without loss of generality that they appears in this order.

According to Proposition 3, there is a subsequence Q of Q of length k such that the corresponding vertices L of L appear in the same order. As one can easily see, this graph contains the yurt of order k and we are done.

Discussion and open problems

An natural question is whether the results of this paper for the classes H i k , i ∈ {1, . . . , 3} are tight. This is indeed the case for the wheels in H 1 k as (1) does not hold for any pair of the form (H 1 k , f (k)) where f = o(k). To see this it is enough to observe that a clique K k does not contain any wheel on k + 1 vertices as a minor while has treewidth k -1 = Ω(k). Clearly, the same lower bound holds for H 2 k (i.e., the double wheels). It is easy to prove that (1) does not hold for any pair of the form (H 0 k , f (k)) or (H 3 k , f (k)) where f = o(k log k). To see this, consider a n-vertex 3-regular Ramanujan graph R (see [START_REF] Morgenstern | Existence and explicit constructions of q + 1 regular ramanujan graphs for every prime power q[END_REF]). Such a graph has girth at least c log n for some universal constant c (see [START_REF] Biggs | Note on the girth of ramanujan graphs[END_REF]), and satisfies tw(R) = Ω(n) (cf. [START_REF] Bezrukov | New spectral lower bounds on the bisection width of graphs[END_REF]Corollary 1]).

Let k be the minimum integer such that n < k • c log n holds. Notice that n = Ω(k log k ), thus tw(R) = Ω(k log k ). We will show that no graph of H 0 2k ∪ H 3 2k is a minor of R. As every graph of H 0 2k ∪ H 3 2k contains k • K 3 as a minor, it is enough to show that k • K 3 is not a minor of R. If k • K 3 is a minor of R, then R contains a collection of k vertex-disjoint cycles. As the girth of R is at least c log n, we have that n k • c log n, a contradiction.

The above observation implies that a function f (k) = Θ(k log k) is the best for which (1) may hold for the pairs (H 0 k , f (k)) and (H 3 k , f (k)) and we conjecture that this is indeed the case. Observe that by the same remark, the lower bound Ω(k log k) also holds for any class {H k } k∈N such that for every k ∈ N, H k m dk • K 3 , for some universal constant d ∈ R. Interestingly, the above proof does not apply for the double wheels in H 2 k . This tempts us to conjecture that (1) holds (optimally) for the pair (H 2 k , k).

2 Figure 1 :

 21 Figure 1: A wheel of order six (left) and a double wheel of order 6 (right)

Lemma 4 .h 2 - 2 2h- 3 .

 4223 Let G be a graph and h > 0 be an integer. If tw(G) 6 • 2 h -4, then G contains as minor a double wheel of order at least2

h 2 - 2 2h- 3 2 h 2 2 h 2 ,

 2232222 as minor. Let P be the path of length at least in the definition of H. Let L be the set, of size at least of the leaves of T that are adjacent to P in H. Such a set exists by definition of Λ(B h ).

h 2 - 2 2h- 3

 223 leaves that are elements of L.

h 2 - 2 2h- 3 ,Corollary 1 .- 2 2

 22312 which is what we wanted to show. Let l > 0 be an integer and G be a graph. If tw(G) 12l -4 then G contains a double wheel of order at least √ llog l-5 as minor. Proof. Let l and G be as above. First remark that log l -1 log l log l

Figure 3 :

 3 Figure 3: Example for Lemma 7

Figure 4 :

 4 Figure 4: The yurt graph of order 5, Y 5

Theorem 8 .

 8 Let k > 0 be an integer and G be a graph. If tw(G) 6k 4 -24k 3 +48k 2 -48k +23, then G contains Y k as minor. Proof. Let k > 0 be an integer and G be a graph such that tw(G) 6k 4 -24k 3 +48k 2 -48k +23. Let C be the comb with l = k 4 -4k 3 + 8k 2 -8k + 4 teeth. As tw(G) 3 |V (C)| -1, G contains some graph of Λ(C) by Lemma 2.

  We say that a graph H is a minor of a graph G (H m G) if there is a minor model of H in G. Notice that H is a minor of G if H can be obtained from subgraph of G by edges contractions.

	Definition 4 (linked set). Let G be a graph and S ⊆ V (G). The set S is said to be linked in G
	if for every two subsets X 1 , X 2 of S (not necessarily disjoint) such that |X 1 | = |X 2 |, there is a
	set Q of |X 1 | (vertex-)disjoint paths between X 1 and X 2 in G whose length is not one (but can
	be null) and whose endpoints only are in S.
	Definition 5 (separation). A pair (A, B) of subsets of V (G) is a called a separation of order k

in G if k = |A ∩ B|, none of A, B is a subset of the other, and there is no edge of G between A \ B and B \ A.

  2 |J| to connected subgraphs of H such that ∀(v, w) ∈ E(W 2 |J| ), there is a vertex of ψ(v) adjacent in H to a vertex of ψ(w). Therefore, (M, ψ) is a W 2 |J| -model in H.

	Since |J|	2 2h-3 , H contains a double wheel of order at least 2 h 2 -2

Acknowledgement. We wish to thank Konstantinos Stavropoulos for bringing the results in [18] (and, in particular, Proposition 2) to our attention, during Dagstuhl Seminar 11071.

Cofinanced by the E.U. (European Social Fund -ESF) and Greek national funds through the Operational Program "Education and Lifelong Learning" of the National Strategic Reference Framework (NSRF) -Research Funding Program: "Thales. Investing in knowledge society through the European Social Fund".


Sébastien Ferenczi
email: ferenczisebastien@yahoo.fr

Luca Q Zamboni
email: zamboni@math.univ-lyon1.fr

Clustering Words and Interval Exchanges

We characterize words which cluster under the Burrows-Wheeler transform as those words w such that ww occurs in a trajectory of an interval exchange transformation, and build examples of clustering words.

1

Introduction

In 1994 Michael Burrows and David Wheeler [START_REF] Burrows | A block sorting data compression algorithm[END_REF] introduced a transformation on words which proved very powerful in data compression. The aim of the present note is to characterize those words which cluster under the Burrows-Wheeler transform, that is to say, those words that are transformed into expressions such as 4 a 3 b 2 c 1 d or 2 a 5 b 3 c 1 d 4 e . Clustering words on a binary alphabet have already been extensively studied (see, for instance, [START_REF] Jenkinson | Characterisations of balanced words via orderings[END_REF][START_REF] Mantaci | Burrows-Wheeler transform and Sturmian words[END_REF]) and identified as particular factors of the Sturmian words. Some generalizations and partial characterizations to r letters appear in Restivo and Rosone [START_REF] Restivo | Burrows-Wheeler transform and palindromic richness, Theoret[END_REF], but it had not yet been observed that clustering words are intrinsically related to a dynamical object called interval exchange transformations introduced in Oseledets [START_REF] Oseledets | On the spectrum of ergodic automorphisms[END_REF]: we shall define them in Definitions 1 and 2 below, and refer the reader to [START_REF] Viana | Dynamics of interval exchange maps and Teichmüller flows[END_REF] which constitutes a classical course on general interval exchange transformations and contains many of the technical terms found in Section 4 below. This link comes essentially from the fact that the array of conjugates used to define the Burrows-Wheeler transform gives rise to a discrete interval exchange transformation sending its first column to its last column. It turns out that the converse is also true: interval exchange transformations generate clustering words. Indeed we prove that clustering words are exactly those words w such that ww occurs in a trajectory of an interval exchange transformation. On a binary letter alphabet, this condition amounts to saying that ww is a factor of an infinite Sturmian word. We end the paper by some examples and questions on how to generate clustering words.

This paper began during a workshop on board Via Rail Canada train number 2. We are grateful to Laboratoire International Franco-Québécois de Recherche en Combinatoire (LIRCO) for funding and Via for providing optimal working conditions. The second author is partially supported by a FiDiPro grant from the Academy of Finland.

The authors owe much to Jean-Paul Allouche, the first mathematician who revealed to both of them the beauty of combinatorics on words, and who taught the first author that not every paper needs to begin with "Let (X, T, µ) be a system ...".

Definitions

Let A = {a 1 < a 2 < • • • < a r } be an ordered alphabet and w = w 1 • • • w n a primitive word on the alphabet A, i.e., w is not a power of another word. For simplification we suppose that each letter of A occurs in w.

The Parikh vector of w is the integer vector (n 1 , . . . , n k ) where n i is the number of occurrences of a i in w. The (cyclic) conjugates of w are the words

w i • • • w n w 1 • • • w i-1 , 1 ≤ i ≤ n. As w is primitive, w has precisely n-cyclic conjugates. Let w i,1 • • • w i,n
denote the ith conjugate of w where the n-conjugates of w are ordered by ascending lexicographical order. Then the Burrows-Wheeler transform of w, denoted by B(w), is the word

w 1,n w 2,n • • • w n,n .
In other words, B(w) is obtained from w by first ordering its cyclic conjugates in ascending order in a rectangular array, and then reading off the last column. For instance B(2314132) = 4332211. We say w is π-clustering if B(w) = a n π1 π1 • • • a nπr πr , where π = Id is a permutation on {1, . . . , r}. We say w is perfectly clustering if it is π-clustering for πi = r + 1i, 1 ≤ i ≤ r. For instance 2314132 is perfectly clustering. Restivo and Rosone [START_REF] Restivo | Burrows-Wheeler transform and palindromic richness, Theoret[END_REF] showed that if w perfectly clusters, then w is strongly (or circularly) rich, i.e., w 2 has |w 2 | + 1 distinct palindromic factors. But this condition is not a characterization of perfectly clustering words (see Example 6.4 in Restivo and Rosone [START_REF] Restivo | Burrows-Wheeler transform and palindromic richness, Theoret[END_REF]). Definition 1. A (continuous) r-interval exchange transformation T with probability vector (α 1 , α 2 , . . . , α r ), and permutation π is defined on the interval [0, 1[, partitioned into r intervals

∆ i = j<i α j , j≤i α j , by T x = x + τ i when x ∈ ∆ i ,
where

τ i = π -1 (j)<π -1 (i) α j -j<i α j .
Intuitively this means that the intervals ∆ i are re-ordered by T following the permutation π. Note that our use of the word "continuous" does not imply that T is a continuous map on [0, 1[ (though it can be modified to be made so); it is there to emphasize the difference with its discrete analogue. Definition 2. A discrete r-interval exchange transformation T with length vector (n 1 , n 2 , . . . , n r ), and permutation π is defined on a set of

n 1 + • • • + n r points x 1 , . . . , x n 1 +•••+nr partitioned into r intervals ∆ i = {x k , j<i n j < k ≤ j≤i n j } by T x k = x k+s i when x k ∈ ∆ i ,
where

s i = π -1 (j)<π -1 (i) n j -j<i n j .
We recall the following notions, defined for any transformation T on a set X equipped with a partition ∆ i , 1 ≤ i ≤ r. Definition 3. The trajectory of a point x under T is the infinite sequence (x n ) n∈IN defined by Proof. (( 2), ( 3) or ( 4) implies ( 1)) By assumption there exists a point x whose initial trajectory of length 2n is the word ww. Consider the set E = {T x, T 2 x, . . . , T n x}. Then for each y ∈ E, the initial trajectory of y of length n, denoted O(y), is a cyclic conjugate of w. Suppose y and z are in E, and y is to the left of z (meaning y < z.). Let j be the smallest nonnegative integer such that T j y and T j z are not in the same ∆ i . Then T j y is to the left of T j z, either because j = 0 or because T is increasing on each ∆ i . Thus O(y) is lexicographically smaller that O(z).

x n = i if T n x belongs to ∆ i , 1 ≤ i ≤ r. The mapping T is minimal if whenever E is a nonempty closed subset of X and T -1 E = E, then E = X.

Main result

Thus B(w) is obtained from the last letter l(y) of O(y) where the points y are ordered from left to right. But l(y) is the label of the interval ∆ i where T n-1 y, or equivalently T -1 y, falls. Thus by definition of T , if y is to the left of z then π -1 (l(y)) ≤ π -1 (l(z)), and if y ′ is between y and z with l(y) = l(z), then l(y ′ ) = l(y) = l(z), hence the claimed result.

Proof. ((2) implies ( 3) implies ( 4)) The first implication is trivial. The second follows from the fact that the trajectories of the discrete r-interval exchange transformation with length vector (n 1 , n 2 , . . . , n r ), and permutation π, and of the continous r-interval exchange transformation with probability vector (

n 1 n 1 +•••+nr , . . . , nr n 1 +•••+nr
) and permutation π are the same. We note that this continuous interval exchange transformation is never minimal, while the discrete one may be.

We now turn to the proof of the converse, which uses a succession of lemmas. Throughout this proof, unless otherwise stated, a given word w is a primitive word on {1, . . . , r}, and every letter of {1, . . . , r} occurs in w; (n 1 , . . . , n r ) is its Parikh vector, the w i,1 • • • w i,n are its conjugates.

The first lemma states that B is injective on the conjugacy classes, which is proved for example in Crochemore, Désarménien, and Perrin [START_REF] Crochemore | A note on the Burrows-Wheeler transformation[END_REF] or Mantaci, Restivo, Rosone and Sciortino citerr1; we give here a short proof for sake of completeness. Lemma 5. If w and w ′ are words such that B(w) = B(w ′ ), then w and w ′ are cyclically conjugate Proof. In the array of the conjugates of w, each column word w 1,j • • • w n,j has the same Parikh vector as w, so we retrieve this vector from B(w); thus we know the first column word, which is 1 n 1 . . . r nr , and the last column word which is B(w). Then the words w n,j w 1,j are precisely all words of length 2 occurring in the conjugates of w, and by ordering them we get the first two columns of the array. Then w n,j w 1,j w 2,j constitute all words of length 3 occurring in the conjugates of w, and we get also the subsequent column, and so on until we have retrieved the whole array, thus w up to conjugacy.

It is easy to see that B, viewed as a mapping from words to words, is not surjective (see for instance [START_REF] Mantaci | An extension of the Burrows-Wheeler transform[END_REF]). A more precise result will be proved in Corollary 7 below. Lemma 6. If w is π-clustering, the mapping w 1,j → w n,j defines a discrete r-interval exchange transformation with length vector (n 1 , n 2 , . . . , n r ), and permutation π.

Proof. We order the occurrences of each letter in w by putting w i < w j if the conjugate

w i • • • w n w 1 • • • w i-1 is lexicographically smaller than w j • • • w n w 1 • • • w j-1 .
By primitivity, the n letters of w are uniquely ordered as

1 1 < • • • < 1 n 1 < 2 1 < • • • < 2 n 2 < • • • < r 1 < • • • < r nr ,
and the first column word is

1 1 • • • 1 n 1 2 1 • • • 2 n 2 • • • r 1 • • • r nr .
We look at the last column word: if w n,j and w n,j+1 are both some letter k, the order between these two occurrences of k is given the next letter in the conjugates of w, and these are respectively w 1,j and w 1,j+1 . Thus w n,j < w n,j+1 . Together with the hypothesis, this implies that the last column word is

(π1) 1 • • • (π1) n π1 • • • (πr) 1 • • • (πr) nπr .
Thus, if we regard the rule w 1,j → w n,j as a mapping on the n 1 + . . . + n r points {1 1 , . . . , 1 n 1 , 2 1 , . . . 2 n 2 , . . . , r 1 , . . . , r nr }, and put ∆ i = {i 1 , . . . , i n i }, we get the claimed result.

Corollary 7. If the discrete r-interval exchange transformation T with length vector (n 1 , n 2 , . . . , n r ), and permutation π is not minimal, the word (π1) n π1 . . . (πr) nπr has no primitive pre-image by the Burrows-Wheeler transform.

Proof. Let w be such an antecedent. By the previous lemma, the map w 1,j → w n,j corresponds to T . If T is not minimal, there is a proper subset E of {1 1 , . . . , 1 n 1 , 2 1 , . . . 2 n 2 , . . . , r 1 , . . . , r nr } which is invariant under w 1,j → w n,j . Thus in the conjugates of w, preceding any occurrence of a letter of E is another occurrence of a letter of E. This implies that w is made up entirely of letters of E, a contradiction. 2)) Let w be as in the hypothesis. Then B(w) = (π1) n π1 • • • (πr) nπr . Thus the transformation T of Lemma 7 is minimal, and thus has a periodic trajectory w ′ w ′ w ′ . . ., where w ′ has Parikh vector (n 1 , . . . , n r ). If w ′ = u k , then n i = kn ′ i for all i, and the set made with the n ′ i leftmost points of each ∆ i is T -invariant, thus w ′ must be primitive. By the proof, made above, that (2) implies (1), w ′ is π-clustering. Hence B(w ′ ) = B(w) and, by Lemma 5, w is conjugate to w ′ , hence ww occurs also in a trajectory of T . Some of the hypotheses of Theorem 4 may be weakened.

Proof. ((1) implies (

Alphabet. {1, . . . , r} can be replaced by any ordered set A = {a 1 < a 2 < • • • < a r } by using a letter-to-letter morphism. Thus for a given word w, we can restrict the alphabet to the letters occurring in w. Note that if ww occurs in a trajectory of an r-interval exchange transformation, but only the letters j 1 , . . . , j d occur in w, then, by the reasoning of the proof that ( 4) implies (1), w is π ′ -clustering, where π ′ is the unique permutation on {1, . . . , d} such that (π ′ ) -1 (y) < (π ′ ) ′-1 (z) iff π -1 (j y ) < π -1 (j z ). If π is a permutation defining perfect clustering, then so is π ′ .

Primitivity. The Burrows-Wheeler transformation can be extended to a non-primitive word w 1 • • • w n , by ordering its n (non necessarily different) conjugates w i • • • w n w 1 • • • w i-1 by nonstrictly increasing lexicographical order and taking the word made by their last letters.

In this case the result of Lemma 7 does not extend: For example B(1322313223) = 3333222211 though the discrete 3-interval exchange transformation with length vector [START_REF] Crochemore | A note on the Burrows-Wheeler transformation[END_REF][START_REF] Crochemore | A note on the Burrows-Wheeler transformation[END_REF][START_REF] Ferenczi | The self-dual induction for every interval exchange transformation[END_REF], and permutation π1 = 3, π2 = 2, π3 = 1 is not minimal. Note that if (π1) n π1 • • • (πr) nπr has a non-primitive antecedent by the Burrows-Wheeler transform, then the n i have a common factor k. exist (see below) non-minimal discrete interval exchange transformations which do not satisfy that condition, and thus words such as 32221 which have no antecedent at all by the Burrows-Wheeler transformation.

But our Theorem 4 is still valid for non-primitive words: the proof in the first direction does not use the primitivity, while in the reverse direction we write w = u k , apply our proof to the primitive u, and check that u 2k occurs also in a trajectory.

Two permutations. An extension of Theorem 4 which fails is to consider, as the dynamicians do [START_REF] Viana | Dynamics of interval exchange maps and Teichmüller flows[END_REF], interval exchange transformations defined by permutations π and π ′ ; this amounts to coding the interval ∆ i by π ′ i instead of i. A simple counter-example will be clearer than a long definition: take points x 1 , . . . , x 9 labelled 223331111 and send them to 111133322 by a (minimal) discrete 3-interval exchange transformation, but where the points are not labelled as in Definition 3 (namely T x 1 = x 8 , T x 3 = x 5 etc...). Then w = 123131312 is such that ww occurs in trajectories of T but B(w) = 323311112.

Building clustering words

Theorem 4 provides two different ways to build clustering words, from infinite trajectories either of discrete (or rational) interval exchange transformations or of continuous aperiodic interval exchange transformations. For r = 2 and the permutation π1 = 2, π2 = 1, the first way gives all the periodic balanced words, and the second way gives (by Proposition 10 below) all infinite Sturmian words: both ways of building clustering words on two letters are used, explicitly or implicitly, in Jenkinson and Zamboni [START_REF] Jenkinson | Characterisations of balanced words via orderings[END_REF].

The use of discrete interval exchange transformations leads naturally to the question of characterizing all minimal discrete r-interval exchange transformations through their length vector; this has been solved by Pak and Redlich [START_REF] Pak | Long cycles in abc-permutations[END_REF] for n = 3 and π1 = 3, π2 = 2, π3 = 1: if the length vector is (n 1 , n 2 , n 3 ), minimality is equivalent to (n 1 + n 2 ) and (n 2 + n 3 ) being coprime. Thus Example 8. With the discrete interval exchange 11223333 → 333322111, we get the perfectly clustering word 313131223.

The same reasoning can be extended to other permutations: for π1 = 2, π2 = 3, π3 = 1, minimality is equivalent to n 1 and (n 2 + n 3 ) being coprime; for π1 = 3, π2 = 1, π3 = 2, minimality is equivalent to n 3 and (n 2 + n 1 ) being coprime; for other permutation on these three letters, T is never minimal.

For r ≥ 4 intervals, the question is still open. An immediate equivalent condition for non-minimality is m i=1 s w i = 0 for m < n 1 + • • • + n r and w 1 • • w m a word occurring in a trajectory. It is easy to build non-minimal examples satisfying such an equality for simple words w, for example for r = 4 and π1 = 4, π2 = 3, π3 = 2, π4 = 1, n 1 = n 2 = n 3 = 1 gives non-minimal examples for any value of n 4 , the equality being satisfied for w = 24 q if n 4 = 3q, w = 14 q+1 if n 4 = 3q + 1, w = 34 q if n 4 = 3q + 2. Similarly, the following example shows how we still do get clustering words, but they may be somewhat trivial.

Example 9. The discrete interval exchange 111233444 → 444332111 satisfies the above equality for w = 14; it is non-minimal and gives two perfectly clustering words on smaller alphabets, 41 and 323.

To study continuous aperiodic interval exchange transformations we need a technical condition called i.d.o.c. [START_REF] Keane | Interval exchange transformations[END_REF] which states that the orbits of the discontinuities of T are infinite and disjoint. It is proved in Keane [9] or in Viana [16] that this condition implies aperiodicity and minimality, and that, if π is primitive, i.e., π{1, . . . , d} = {1, . . . , d} for d < r, then the r-interval exchange transformation with probability vector (α 1 , . . . , α r ) and permutation π satisfies the i.d.o.c. condition if α 1 , . . . , α r and 1 are rationally independent. We can now prove Proposition 10. Let w = w 1 • • • w n be a primitive word on A = {1, . . . , r}, such that every letter of A occurs in w. Then w is π-clustering if and only if ww occurs in a trajectory of a continuous r-interval exchange transformation with permutation π, satisfying the i.d.o.c. condition.

Proof. The "if" direction is as in Theorem 4. To get the "only if", we generate w by a minimal discrete interval exchange transformation as in (2) of Theorem 4, and thus π is primitive. Then we replace it by a continuous periodic interval exchange transformation as in the proof that (3) implies (4). But, because cylinders are always semi-open intervals, if a given word ww occurs in a trajectory of a continuous r-interval exchange transformation with permutation π and probability vector (α 1 , . . . , α r ), it occurs also in trajectories of every r-interval exchange transformation with the same permutation whose probability vector is close enough to (α 1 , . . . , α r ). Thus we can change the α i to get the irrationality condition which implies the i.d.o.c. condition.

Trajectories of interval exchange transformations satisfying the i.d.o.c. condition may be explicitly constructed via the self-dual induction algorithms of [START_REF] Ferenczi | Structure of three-interval exchange transformations. II. A combinatorial description of the trajectories[END_REF] for r = 3 and π1 = 3, π2 = 2, π3 = 1, [START_REF] Ferenczi | Structure of k-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] for all r and πi = r + 1i, and the forthcoming [START_REF] Ferenczi | The self-dual induction for every interval exchange transformation[END_REF] in the most general case. More precisely, Proposition 4.1 of [START_REF] Ferenczi | Structure of k-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] shows that if the permutation is πi = r + 1i (or more generally if the permutation is in the Rauzy class of πi = r + 1i), then there exist infinitely many words ww in the trajectories. It also gives a sufficient condition for building such words: if a bispecial word w, a suffix s and a prefix p of w are such that pw = ws, then both pp and ss occur in the trajectories. In turn, a recipe to achieve that relation is given in (i) of Theorem 2.8 of [START_REF] Ferenczi | Structure of k-interval exchange transformations: induction, trajectories, and distance theorems[END_REF]: we just need that in the underlying algorithm described in Section 2.6 of [START_REF] Ferenczi | Structure of k-interval exchange transformations: induction, trajectories, and distance theorems[END_REF], either p n (i) = i or m n (i) = i (except for some initial values of n, where, for i = 1, p and s are longer than w). Many explicit examples of ww have been built in this way.

• For r = 3, w = A k , w = B k (see Ferenczi, Holton and Zamboni Prop. • For all r = n , w = P k,1,1 , w = P k,n-i,i+1 P k,i+1,n-i , w = M k,n+1-i,i-1 M k,i-1,n+1-i (see Ferenczi [START_REF] Ferenczi | Billiards in regular 2n-gons and the self-dual induction[END_REF]Theorem 12]);

Example 13. 5252434252516152516161525161 is perfectly clustering.

For other permutations, we describe in Ferenczi [START_REF] Ferenczi | The self-dual induction for every interval exchange transformation[END_REF] an algorithm generalizing the one in Ferenczi and Zamboni [START_REF] Ferenczi | Structure of k-interval exchange transformations: induction, trajectories, and distance theorems[END_REF], but we do not know if every interval exchange transformation produces infinitely many ww. For the permutation π1 = 4, π2 = 3, π3 = 1, π4 = 2, examples can be found in Theorem 5.2 of [START_REF] Ferenczi | Structure of k-interval exchange transformations: induction, trajectories, and distance theorems[END_REF], with w = P 1,qn M 2,qn , w = P 2,qn M 3,qn , w = P 3,qn M 1,qn , Example 14. 4123231312412 is π-clustering, We remark that our self-dual induction algorithms for aperiodic interval exchange transformations generate families of nested clustering words with increasing length, and thus may be more efficient in producing very long clustering words than the more immediate algorithm discrete interval exchange transformations.

Theorem 4 ., 4 .

 44 Let w = w 1 • • • w n be a primitive word on A = {1, . . . , r}, such that every letter of A occurs in w. The following are equivalent:1. w is π-clustering, 2.ww occurs in a trajectory of a minimal discrete r-interval exchange transformation with permutation π, 3. ww occurs in a trajectory of a discrete r-interval exchange transformation with permutation πww occurs in a trajectory of a continuous r-interval exchange transformation with permutation π.

  2.10]), Example 11. 13131312222 and 131312221312213122 are perfectly clustering. • For r = 4, w = M 2 (k), w = P 3 (k)M 1 (k) (see Ferenczi and Zamboni [7, Lemmas 4.1 and 5.1]), Example 12. 2 m (3141) n 32 are perfectly clustering for any m and n.