Nicole Anderton

Craig Stuart Carlson

Albert Thijs Poortinga

Momoka Yamasaku

Naoyuki Otake

Nobuki Kudo

Michiel Postema

Calcium carbonate theranostic agent in an ultrasound field

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

Paper ID: 3P5-9 : Nicole.Anderton@tuni.fi Theranostic agents are materials that act both as tracers during diagnostic imaging and as vehicles carrying and releasing therapeutics during treatment. Ultrasound-triggered theranostic agents comprise shell-encapsulated microbubbles that pulsate during low-amplitude sonication and release their payload upon higher-amplitude sonication. High-amplitude sonication may be undesirable due to unwanted side effects related to inertial cavitation. However, low-amplitude release from microbubbles typically requires thin encapsulating shells, which in turn may be permanently disrupted under diagnostic imaging conditions. The purpose of this study was to investigate a novel microbubble agent with thick shells composed of calcium carbonate.

Research funding: This work was supported by JSPS KAKENHI, Grant Nos. JP17H00864 and JP20H04542, by the National Research Foundation of South Africa, Grant No. 127102, and by the Academy of Finland, Grant No. 340026. Conflict of interest: Authors state no conflict of interest.

Sonication conditions:

• 1-MHz centre frequency;

• 3-cycle single pulse;


est destinée au dépôt

Background and objective

In Mali, women living with HIV (WLHIV) who disclose their positive status are often confronted with stigma, violence, economic pressure, and social exclusion, including from family.

To evaluate the effectiveness of an intervention for the empowerment of WLHIV on the decision to disclose or not their HIV-positive status, and associated factors.

The ANRS 12373 Gundo-So study

Randomized trial implemented in 6 community-based clinics in Mali in 2019-2020

Intervention:

9 weekly sessions of peer-support for strengthening the capacity of WLHIV to manage the consequences concerning (non)disclosure of their HIV positive status.

The intervention does not promote disclosure nor not disclosure!

Data and Methods

Individual and psychosocial characteristics were collected at enrolment, pre-/post-intervention, then quarterly over 9 months.

Statistical analysis

A growth curve model using Poisson distribution was estimated to investigate changes before (=0) and after the intervention (=1) (Figure 1).

Advantages: Random-effects allowed controlling for unobserved and/or unobservable characteristics. This technique accounts for missing data and unequally spaced time points. 1 Aix Marseille Univ, Inserm, Ird, Sesstim, Isspam -Marseille (France), 2 Arcad Santé Plus -Bamako (Mali), 3 Community-based Research Laboratory, Coalition PLUS -Pantin (France), 4 Umr 1296, Université Lyon 2 -Lyon (France)

TUPED09

Effectiveness

Evaluated at each time point using a scale measuring the psychological burden related to the sero-status secret from 0 (none) to 5 (very high).

Results

Conclusions

Our results have demonstrated that the Gundo-So intervention as effective for the empowerment of Malian WLHIV to reduce the psychological burden of HIV disclosure-related issues. Social and behavioral interventions adopting a community-based approach can effectively promote health outcomes among people confronted to sociocultural hostile environments such as Mali. -139 (58.0%) followed-up at M3, and -136 (56.6%) at both M6 and M9.

A

  growth curve model to assess the effectiveness of a community-based intervention for the empowerment of Malian females in the decision to disclose (or not) their HIV status (ANRS-12373 Gundo-So) L Sagaon-Teyssier, B Coulibaly, L Riegel, V Villes, D Traoré, B Spire, M Mora, M Perray, G Maradan, M Fiorentino, et al. To cite this version: L Sagaon-Teyssier, B Coulibaly, L Riegel, V Villes, D Traoré, et al.. A growth curve model to assess the effectiveness of a community-based intervention for the empowerment of Malian females in the decision to disclose (or not) their HIV status (ANRS-12373 Gundo-So). Conférence IAS 2023 : Tour d'horizon des travaux de l'agence présenté, Jul 2023, Brisbane, Australia. inserm-04315577

A

  growth curve model to assess the effectiveness of a community-based intervention for the empowerment of Malian females in the decision to disclose (or not) their HIV status (ANRS-12373 Gundo-So) L. Sagaon-Teyssier 1,2* , B. Coulibaly 2 , L. Riegel 3 , V. Villes 3 , D. Traoré 2 , B. Spire 1 , M. Mora 1 , M. Perray 4 , G. Maradan 1 , M. Fiorentino 1 , B. Dembele 2 , M. Bourrelly 1,3 , R.M. Delabre 3 , D. Rojas Castro 3 , A. Yattassaye 2 , M. Préau 4 .

Figure 1 .

 1 Figure 1. Growth curve model for the psychological burden of serostatus secret with Poisson distribution


Édouard Bonnet

Colin Geniet

Romain Tessera

Stéphan Thomassé

TWIN-WIDTH VII: GROUPS

Keywords: 2020 Mathematics Subject Classification. Primary 05C25; Secondary 20F65, 05C30 Twin-width, Cayley graphs, coarse embeddings, excluded permutations, small classes, small cancellation. The first, second

Twin-width is a recently introduced graph parameter with applications in algorithmics, combinatorics, and finite model theory. For graphs of bounded degree, finiteness of twin-width is preserved by quasiisometry. Thus, through Cayley graphs, it defines a group invariant.

We prove that groups which are abelian, hyperbolic, ordered, solvable, or with polynomial growth, have finite twin-width. Twin-width can be characterised by excluding patterns in the self-action by product of the group elements. Based on this characterisation, we propose a strengthening called uniform twin-width, which is stable under constructions such as group extensions, direct products, and direct limits.

The existence of finitely generated groups with infinite twin-width is not immediate. We construct one using a result of Osajda on embeddings of graphs into groups. This implies the existence of a class of finite graphs with unbounded twin-width but containing 2 O(n) • n! graphs on vertex set {1, . . . , n}, settling a question asked in a previous work.

Introduction

Twin-width is an invariant of graphs and matrices introduced in [START_REF] Bonnet | Twinwidth I: tractable FO model checking[END_REF], with applications in algorithmics, logic, enumerative combinatorics [START_REF] Bonnet | Twin-width II: small classes[END_REF][START_REF] Bonnet | Twin-width III: max independent set, min dominating set, and coloring[END_REF][START_REF] Bonnet | Twin-width IV: ordered graphs and matrices[END_REF]. Finite twin-width is known to be a group invariant of Cayley graphs [START_REF] Bonnet | Twin-width II: small classes[END_REF]Section 7]. Our main result is the construction of groups with infinite twin-width, using an embedding theorem of Osajda [START_REF] Osajda | Small cancellation labellings of some infinite graphs and applications[END_REF].

Theorem 1.1. There is a finitely generated group with infinite twin-width.

This disproves the 'small conjecture' proposed in [START_REF] Bonnet | Twin-width II: small classes[END_REF], related to the Stanley-Wilf conjecture proved by Marcus and Tardos [START_REF] Marcus | Excluded permutation matrices and the Stanley-Wilf conjecture[END_REF], see section 1.1 below. It is also related to the problem of finding graphs with bounded degree and infinite twin-width, see section 1.3.

We study characterisations, variants, and stability properties of twinwidth of groups, and prove that a number of well-known classes of groups have finite twin-width, see section 1.2. Twin-width of groups has an interesting relation to queue number, a more restrictive graph parameter: a number of results of this paper also hold for the queue number, see section 1.4.

1.1. Growth of classes excluding substructures. Marcus and Tardos proved that any n × n 0-1 matrix with more than c k n 1-entries contains all k × k permutation matrices as submatrices, for an appropriate c k function of k only [START_REF] Marcus | Excluded permutation matrices and the Stanley-Wilf conjecture[END_REF]. A major corollary is the Stanley-Wilf conjecture: For any fixed permutation σ, the class of permutations avoiding σ as pattern has singleexponential growth-as opposed to the class of all permutations which has factorial growth. Guillemot and Marx built on the result of Marcus and Tardos by giving a characterisation of classes of permutations which exclude some pattern [START_REF] Guillemot | Finding small patterns in permutations in linear time[END_REF]: they have bounded width, which is defined by representing permutations with points in the plane, iteratively contracting these points down to a single one while measuring a number of conflicts throughout this contraction sequence, and minimizing the number of conflicts over all choices of contraction sequence.

A natural generalisation of the Stanley-Wilf conjecture to arbitrary 0-1 matrices is the following: Any class of matrices C closed under taking submatrices has growth at most single-exponential or at least factorial. This was established in [START_REF] Bonnet | Twin-width IV: ordered graphs and matrices[END_REF], by proving that classes of matrices with exponential growth are exactly the classes with bounded twin-width, a natural generalisation of Guillemot and Marx's width to graphs and matrices proposed in [START_REF] Bonnet | Twinwidth I: tractable FO model checking[END_REF]. Matrices with bounded twin-width are also characterised by excluding grids of high rank, which can be seen as a generalisation of excluding patterns.

The logical next question in this line of work is the generalisation to graphs. One may think of graphs as essentially the same as a 0-1 matrix, through adjacency matrices. But a major difference is that matrices have an innate order, which is lost in graphs. For graphs, the sensible equivalent of classes with exponential growth is small classes: classes of graphs which contain at most n! • c n graphs on vertices 1, . . . , n, for some constant c. The additional n! compensates for the choice of a permutation of the vertices.

Well known examples of small classes of graphs include trees, planar graphs, and more generally proper minor-closed classes [START_REF] Norine | Proper minorclosed families are small[END_REF]. These examples are generalised by the following.

Theorem 1.2 ([3]). Classes of graphs with bounded twin-width are small. With this result, and the cases of matrices and permutations in mind, the following very natural conjecture was raised.

Conjecture 1.3 (Small conjecture [START_REF] Bonnet | Twin-width II: small classes[END_REF]). A class of graphs closed under induced subgraphs is small if and only if it has bounded twin-width.

We disprove Conjecture 1.3 using an approach suggested in [START_REF] Bonnet | Twin-width II: small classes[END_REF]: if G is a Cayley graph of some group Γ, then the class of finite subgraphs of G is small [START_REF] Bonnet | Twin-width II: small classes[END_REF]Lemma 8.1]. If Γ is a group with infinite twin-width, then this class furthermore has unbounded twin-width, hence is a counterexample to Conjecture 1.3. Thus Theorem 1.1 gives: Corollary 1.4. There is a small class of graphs closed under induced subgraphs and with unbounded twin-width.

1.2. Properties of twin-width of groups. We prove that for bounded degree graphs, finiteness of twin-width is preserved by quasi-isometries, i.e. maps which preserve distances up to some affine lower and upper bounds, and more generally by coarse and regular embeddings. This is a generalisation of [START_REF] Bonnet | Twin-width II: small classes[END_REF]Lemma 8.2], which proved that finite twin-width is a group invariant of Cayley graphs: given a group Γ, all Cayley graphs of Γ are quasi-isometric, hence either all or none of them have finite twin-width. In relation with coarse geometry, we remark that Gromov-hyperbolic groups have finite twin-width, because they embed into finite products of trees with bounded degree [START_REF] Buyalo | Embedding of hyperbolic groups into products of binary trees[END_REF].

Groups with finite twin-width have a remarkable second characterisation: a group Γ has finite twin-width if and only if there is a total order < on Γ such that for any x ∈ Γ, the action of x on (Γ, <) by product is a permutation with finite width (in the sense of Guillemot and Marx [START_REF] Guillemot | Finding small patterns in permutations in linear time[END_REF]), or equivalently a permutation which avoids some pattern. For example, if < is a right-invariant order on Γ, the action of any x is an increasing permutation, i.e. a permutation which excludes a decreasing sequence of length 2 as pattern. This characterisation extends to non-finitely generated groups, and also suggests a natural strengthening called uniform twin-width: in the above statement, we require a uniform bound on the width of actions of elements of Γ, or equivalently require all these actions to avoid the same pattern. Having finite uniform twin-width implies finite twin-width, while the converse does not a priori hold.

Uniform twin-width is preserved by a number of group operations.

Lemma 1.5 (Lemmas 6.2, 6.5 and 6.13 to 6.15 in the text). The following constructions preserve finiteness of uniform twin-width:

(1) Group extensions (and thus Cartesian or semidirect products);

(2) Infinite direct products and direct sums;

(3) Direct limits;

(4) Taking supergroups with finite index;

(5) Quotienting by finite subgroups; (6) Wreath products.

From this and a few other results, we obtain many examples of groups with finite uniform twin-width: abelian groups, solvable groups, groups with polynomial growth, lamplighter groups, automorphism groups of trees.

We conjecture that uniform twin-width is strictly stronger than twinwidth, i.e. there are groups with finite twin-width and infinite uniform twinwidth. A candidate is the group of finitely supported permutations on Z: it has finite twin-width, and we think it is unlikely to have finite uniform twin-width as this would imply a universal bound on the uniform twin-width of finite groups, and more generally elementary amenable groups.

1.3. Twin-width of bounded degree graphs. Bounded degree graphs are an interesting and not very well understood special case in which to consider twin-width. It is known that graphs with bounded degree can have infinite twin-width by the counting argument of the previous section: it is easy to verify that the class of 3-regular graphs is not small, hence it contains finite graphs with arbitrarily large twin-width by Theorem 1.2-in fact, for any k, almost all 3-regular graphs have twin-width more than k. On the other hand, no explicit or deterministic construction for bounded degree graphs with unbounded twin-width is known. Finding such graphs could significantly help our understanding of twin-width. Bilu-Linial expanders [START_REF] Bilu | Lifts, discrepancy and nearly optimal spectral gap[END_REF] are an interesting example: they are 3-regular expanders, hence seemingly complex graphs, but with a structured construction which allows to prove that they have twin-width at most 6 [3, Section 5].

If Γ is a group with infinite twin-width, the class of subgraphs of some Cayley graph of Γ has bounded degree and unbounded twin-width, which could solve the aforementioned problem. Unfortunately, the group constructed in Theorem 1.1 does not help in this regard: its construction starts from a sequence of bounded degree graphs with unbounded twin-width in the first place, and relies largely on probabilistic methods. Thus the same question remains for groups: can we find a more explicit construction of a group with infinite twin-width, or one with a direct proof that twin-width is infinite? 1.4. Other graph parameters for groups. This paper proposes to consider twin-width on groups. It is natural to ask whether the same can be done with other classical graph parameters.

Tree-width-arguably the most important graph 'width' parameter-is a group invariant, studied by Kuske and Lohrey [START_REF] Kuske | Logical aspects of Cayley-graphs: the group case[END_REF]. Using that graphs with bounded tree-width and bounded degree can be partitioned into parts of bounded size so that the quotient is a tree [START_REF] Ding | Some results on tree decomposition of graphs[END_REF], they prove the equivalence between finite tree-width, virtually free, context-free word problem, and the Cayley graphs having decidable monadic second-order theory.

Stack and queue number are two other graph parameters, sitting between tree-width and twin-width: bounded tree-width implies bounded stack and queue number [START_REF] Joseph | The pagenumber of k-trees is O(k)[END_REF][START_REF] Dujmovic | Layout of graphs with bounded tree-width[END_REF], either of which implies bounded twin-width [3, Theorem 7.4]. Eppstein et al. recently proved that the 3-dimensional grid with diagonals has infinite stack number [START_REF] Eppstein | Three-dimensional graph products with unbounded stack-number[END_REF]. This is the first known explicit construction of bounded degree graphs with unbounded stack number (probabilistic constructions were previously known [START_REF] Malitz | Graphs with E edges have pagenumber O( √ E)[END_REF]). This implies that stack number is not a group invariant, because the 3-dimensional grid without diagonals has finite stack number, and both variants of the grid are Cayley graphs of Z 3 .

On the other hand, queue number can be shown to be a group invariant, and a surprisingly large part of the results of this paper can be adapted to queue number. The group of Theorem 1.1 of course has infinite queue number, since finite queue number implies finite twin-width. Queue number is characterised by excluding decreasing sequences in the adjacency matrix for some choice of vertex ordering. This somewhat resembles the matrix characterisation of twin-width, and allows to define a uniform queue number for groups. Most operations of Lemma 1.5 also preserve finite uniform queue number. However, unlike for twin-width, products and extensions preserve finiteness of uniform queue number, but not the exact bound on the latter. Thus, we still obtain for instance that finitely generated abelian groups have finite uniform queue number, but the proof does not give a uniform bound on the latter, and thus does not go through direct limits to reach non-finitely generated abelian groups. Despite this, we do not have examples of groups with finite twin-width and infinite queue number (or similarly for the uniform variants). Separating twin-width and queue number on sparse graphs is an open problem. 1.5. Organisation of the paper. Section 2 summarises basic notions and notations used in this paper. Section 3 presents the definition of twin-width, and known results used in this work. Because this paper focuses solely on graphs of bounded degree, we give a more restricted definition than the one of [START_REF] Bonnet | Twinwidth I: tractable FO model checking[END_REF], which slightly simplifies several of these results.

Section 4 presents twin-width as a quasi-isometric invariant property of Cayley graph, giving some basic examples, as well as examples related to geometric group theory. Section 5 introduces a second characterisation of twin-width of groups using matrices, and a natural strengthening: uniform twin-width. Section 6 proves a number of stability results for (uniform) twinwidth under common group operations, and uses these results to show that several well-known classes of groups have finite twin-width.

Section 7 constructs a finitely generated group with infinite twin-width, by embedding a well-chosen sequence of graphs of bounded degree into a group. This construction gives a recursive presentation, with decidable word problem. It follows that there are finitely presented groups with infinite twinwidth. This can be read independently of sections 5 and 6.

Finally, section 8 discusses the relation of twin-width and queue number in groups. We show that many results of this paper also hold when replacing twin-width with queue number, and we point out the points where this replacement fails.

Preliminaries and notations

2.1. Graphs. We consider undirected graphs, without loops nor multiple edges, and which may be finite or countably infinite. A graph is denoted as a pair G = (V, E) with V and E the sets of vertices and edges respectively, and we also write V (G) for V , and

E(G) for E. If G, H are graphs, H is a subgraph of G if V (H) ⊂ V (G) and E(H) ⊂ E(G). It is an induced subgraph if V (H) ⊂ V (G)
, and E(H) consists exactly of the edges in E(G) with endpoints in V (H). A class of graphs is a collection of graphs which is closed under isomorphism. A class is hereditary if it is also closed under taking induced subgraphs.

If v ∈ V (G), its degree d(v) is the number of edges incident to v. We denote by ∆(G) the maximum degree of vertices in G. A graph is k-regular if all its vertices have degree k. A cubic graph is a 3-regular graph.

The diameter of a connected graph G, denoted diam(G), is the maximum distance between two vertices of G. The girth of a graph G, denoted girth(G), is the minimum length of a cycle in G.

2.2.

Matrices. We consider binary, possibly infinite matrices, and pay particular attention to the order of their rows and columns. That is, if (X, < X ), (Y, < Y ) are two totally ordered, possibly infinite sets, an X × Y binary matrix is a map M : X × Y → {0, 1}. Equivalently, it is a binary relation between ordered sets. We call X, respectively Y , the set of column, respectively row, indices. The matrix M is finite if X, Y are finite. A submatrix of M is obtained by restricting M to X ′ × Y ′ for some X ′ ⊂ X, Y ′ ⊂ Y . By analogy with graphs, we call degree of a column or a row of a matrix the number of 1-entries it contains.

Given f : X → Y , the matrix M f of f is defined by M f (x, y) = 1 if and only if f (x) = y. We will primarily consider this construction when f is bijective, in which case we call M f a bijection matrix. Bijection matrices are exactly the matrices with all rows and columns of degree 1. In the finite case, they are more commonly called permutation matrices, but this would be abusive in general since X and Y need not be isomorphic as orders.

Given a graph G = (V, E) and a total order < on V , the adjacency matrix A < (G) is the (V, <) × (V, <) matrix such that A < (G)(x, y) = 1 if and only if x, y are adjacent in G.

Divisions of matrices.

If M is an X × Y matrix, a k × l-division of M consists of partitions of rows and columns into intervals; i.e. it is given by X = {X 1 , . . . , X k } partition of X, Y = {Y 1 , . . . , Y l } partition of Y , such that every X i or Y j is an interval, and with

X 1 < X • • • < X X k and Y 1 < Y • • • < Y Y l . The zone (i, j) of the division (X , Y) is the submatrix M restricted to X i × Y j . The quotient matrix M/(X , Y) is the X × Y matrix with a '1' at position X i , Y j if
(Γ, S) def = Γ, xy | x -1 y ∈ S ∪ S -1 .
Thus edges go from x to y by multiplying on the right by a generator.

A group presentation consists of a set S of generators, and a set R of relators which are finite words over S ⊎ S -1 , where S -1 denotes formal inverses of elements of S. The group associated to this presentation, denoted S; R , is the free group over S quotiented by the normal subgroup generated by R. A group G is said to admit S; R as presentation if it is isomorphic to S; R . A group is finitely presented if it admits a presentation with finite sets of generators and of relators.

For a group Γ finitely generated by S, the word problem is the following decision problem: given w a word over S ∪S -1 , is w interpreted as an element of Γ equal to the neutral element? This problem can be undecidable even for finitely presented groups. Decidability of the word problem is well known to be independent of the choice of S.

Coarse geometry.

In coarse geometry, distances in metric spaces are considered up to some possibly large error. The fundamental notion is the quasi-isometry. For λ 0, a map f : X → Y between metric spaces is a λ-quasi-isometric embedding if for all x, x ′ ∈ X,

λ -1 d X (x, x ′ ) -λ d Y f (x), f (x ′ ) λd X (x, x ′ ) + λ
Thus quasi-isometric embeddings are maps which preserve distances up to affine lower and upper bound. The map f is a λ-quasi-isometry if it is also λ-cobounded, i.e. every y ∈ Y is at distance at most λ of f (X). The spaces X and Y are said to be quasi-isometric if there is a λ-quasi-isometry X → Y for some λ. This is equivalent to having back and forth quasi-isometric embeddings between X and Y whose compositions are within a bounded distance of identity maps. Quasi-isometry is an equivalence relation.

In a graph G, the vertex set V (G) is equipped with the shortest path distance d G (x, y). This defines a metric space when G is connected. Remark that this metric space is quasi-isometric to the geometric realisation of G, in which one replaces each edge of G by a path isometric to the real segment [0, 1].

Given a group Γ and S, S ′ two finite generating sets of Γ, it is easy to verify that Cay(Γ, S) and Cay(Γ, S ′ ) are quasi-isometric. This is the foundation of coarse geometry on groups.

Regular embeddings are another notion of embedding in coarse geometry, which is particularly interesting for graphs seen as metric spaces. A map f : X → Y is a λ-regular embedding if it is λ-Lipschitz and for all y ∈ Y , |f -1 (y)| λ. If all balls of X have cardinality bounded by a function of their radius, then any quasi-isometric embedding X → Y is also a regular embedding. In particular, this is the case when X is a graph with bounded degree.

2.5. Direct limits. Let S be some structure (in our case, a group or a graph), and let (S i ) i∈I be a family of substructures of S. The family (S i ) i∈I is directed if for all i, j ∈ I, there exists k ∈ I with S i ∪S j ⊆ S k . The structure S is said to be direct limit of (S i ) i∈I if (S i ) i∈I is directed and S = i∈I S i . For instance, chains are a very special case of directed families, a graph is always direct limit of all its finite induced subgraphs, and similarly a group is direct limit of its finitely generated subgroups.

The following is a folklore lemma which we use to show that twin-width goes through direct limits. We give a proof with ultrafilter arguments. When the directed family is isomorphic to N as order, one can also prove it using Kőnig's theorem, or an induction and the axiom of countable choice.

Lemma 2.1. Let S be direct limit of (S i ) i∈I , and for each i ∈ I let < i be a total order on S i . Then there exists a total order < on S such that for any finite X ⊂ S, there is some i ∈ I with X ⊆ S i and such that < and < i coincide on X.

Proof. Order I by i j if S i ⊆ S j . For i ∈ I, define its upward closure ↑ i = {j | j i}. Consider the family of non-empty and eventually upwardclosed subsets

F def = {J ⊆ I | ∃i ∈ I, ↑ i ⊆ J} . If A ∈ F and A ⊂ B, then clearly B ∈ F. Furthermore, given A 1 , A 2 ∈ F, consider i 1 , i 2 such that ↑ i j ⊆ A j . Since (S i ) i∈I is directed, there exists k ∈ I such that i 1 , i 2 k. Then ↑ k ⊆ A 1 ∩ A 2 ,
and thus A 1 ∩ A 2 ∈ F. This proves that F is a proper filter, hence there is an ultrafilter U containing F.

For x = y ∈ S, consider the indices which order x before y.

I xy def = {i ∈ I | x < i y}
The limit order on S in then defined as x < y if and only if I xy ∈ U . Since S is direct limit of (S i ) i∈I , for any x, y ∈ S, there is some i ∈ I such that x, y ∈ S i . Assuming x = y, it is clear that ↑ i ⊆ I xy ∪ I yx : for any j i, x and y must be comparable by < j . Since U is an ultrafilter, it follows that either I xy ∈ U or I yx ∈ U (but not both as they are disjoint). Thus < is a total, irreflexive and antisymmetric relation. Let us prove the condition on < required by the lemma-transitivity follows from it. Given X ⊆ S any finite subset, there is some i ∈ I with X ⊆ S i . Define

A def = (↑ i) ∩ x,y∈X x<y I xy
Then A is a finite intersection of elements of U , hence A ∈ U and in particular it is non-empty. Choose j ∈ A. Then j i, hence X ⊆ S j . Furthermore for any x < y in X, we have j ∈ I xy hence x < j y. Since both < and < j are total, irreflexive, and antisymmetric on X, this implies that they coincide on X as desired.

Twin-Width of graphs and matrices

This section recalls the definition of twin-width [START_REF] Bonnet | Twinwidth I: tractable FO model checking[END_REF], and some fundamental results. We will present a simplified definition specialised for graphs of bounded degree, called strict twin-width. The two notions are equivalent on graphs of bounded degree, in the sense that they differ by at most the maximum degree of the graph. When considering matrices, strict twin-width is closely related to the work of Guillemot and Marx who first introduced twin-width for permutation matrices [START_REF] Guillemot | Finding small patterns in permutations in linear time[END_REF]. The reader may refer to [START_REF] Bonnet | Twinwidth I: tractable FO model checking[END_REF] for the general definition. See also [START_REF] Bonnet | Twin-width II: small classes[END_REF]Section 7] for a discussion on twin-width for sparse graphs beyond bounded degree.

Definitions and characterisations.

3.1.1. Twin-width of graphs. Let G = (V, E) be a finite graph and P be a partition of V (G). The quotient graph G/P has vertex set P, and its edges are all XY with X, Y ∈ P such that there exists an edge xy of G with x ∈ X and y ∈ Y . A partition sequence is a sequence P n , . . . , P 1 of partitions of V (G) such that P n = {{v} | v ∈ V } is the partition into singletons, P 1 = {V } is the trivial partition, and each P i-1 is obtained by merging two parts of P i . The width of this partition sequence is the maximum degree of the quotient graphs, i.e. max n i=1 ∆(G/P i ). The strict twin-width of G, denoted stww(G), is the minimum width of a partition sequence starting with G.

For a partition sequence P n , . . . , P 1 , one may also see the quotients graphs G/P n , . . . , G/P 1 as obtained by successive contractions of arbitrary pairs of vertices, starting from G and ending with a single vertex left, see Figure 1. Here, we insist that contracting pairs of non-adjacent vertices is allowed.

Remark that stww(G) is at least ∆(G). Strict twin-width is also nonincreasing when taking subgraphs. 1 Strict twin-width has the following relation to the general notion of twin-width, denoted tww(G), as defined in [START_REF] Bonnet | Twinwidth I: tractable FO model checking[END_REF].

(1)

max (∆(G), tww(G)) stww(G) ∆(G) + tww(G)
1 Non-strict twin-width is only stable under taking induced subgraphs, and has no relation to ∆(G).

Figure 1.

A contraction sequence of width 3 (i.e. the quotient graphs of a partition sequence), represented in reading order. At each step, vertices to be contracted are circled.

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Figure 2.
A matrix contraction sequence of width 2 (i.e. the quotient matrices of a division sequence). Only 1-coefficients are represented in the matrices. At each step, rows or columns to be contracted are marked with thick lines.

That is, the two notions are equivalent up to an additive constant on graphs of bounded degree. We will only use strict twin-width in this work, and will sometimes drop the 'strict' qualifier when unambiguous. Twin-width is continuously extended to an infinite graph G, i.e.

stww(G)

def = sup {stww(H) | H finite induced subgraph of G} .
The graph G has finite strict twin-width if stww(G) < ∞.

3.1.2. Twin-width of matrices. Twin-width extends to binary matrices, by contracting rows and columns instead of vertices. However, in the case of matrices we only allow contraction of consecutive rows and columns.

Let M be a finite matrix. Recall that a division of M is a partition of its row and column indices into intervals. A division sequence for M is a sequence

(X n , Y n ), . . . , (X 1 , Y 1 ) of divisions of M such that (X n , Y n ) is the division into singletons, (X 1 , Y 1 ) = ({X}, {Y }) is the trivial division, and (X i-1 , Y i-1 ) is obtained from (X i , Y i ) by merging two parts either in X i or in Y i .
The width of this division sequence is the maximum degree of any column or row in any quotient matrix M/(X i , Y i ), see Figure 2. The strict twin-width of M , denoted by stww(M ), is the minimum width of a division sequence of M . As with graphs, it is extended to infinite matrices by taking the supremum of strict twin-width over all finite submatrices. 3.1.3. Grids in matrices. For matrices, twin-width admits a dual characterisation by excluding grids. A k-grid in a matrix M is a k ×k-division in which all zones are non-zero, or equivalently for which the quotient matrix has only '1' coefficients, see Figure 3. The grid number of M , denoted gn(M ), is the supremum of sizes of grids in M .

Remark 3.1. Let M be an X × Y matrix. Then M contains a k-grid if and only if there exist x i,j ∈ X, y i,j ∈ Y for 1 i, j k such that (1) For all indices i, j, M (x i,j , y i,j ) = 1 (2) For all indices i, i ′ , j, j ′ , if i < i ′ then x i,j < X x i ′ ,j ′ , and if j < j ′ then y i,j < Y y i ′ ,j ′ .
Thus, M has a k-grid if and only if it has a k 2 × k 2 -submatrix with a k-grid. Hence the grid number of an infinite matrix is the supremum of the grid numbers of its finite submatrices.

Grid number and twin-width of matrices are related as follows. For finite matrices, Theorem 3.2 is a simple generalisation of [19, Proposition 3.6, Theorem 4.1] from permutation matrices to matrices with bounded degree. 2 It is also a simplified version of [6, Theorem 10]. 3 For infinite matrices, the theorem should of course be understood as stating 'stww(M ) is finite if and only if gn(M ) is finite, and in that case the stated inequalities hold'. The infinite case follows from the finite one, since twin-width and grid number of infinite matrices are obtained by taking the [START_REF] Fox | Stanley-Wilf limits are typically exponential[END_REF][START_REF] Cibulka | Füredi-Hajnal limits are typically subexponential[END_REF] of Marcus Tardos Theorem [START_REF] Marcus | Excluded permutation matrices and the Stanley-Wilf conjecture[END_REF], at the core of this proof.

2 In [19, Theorem 4.1], the bound on f is 2 O(n log n) . The bound f (n) = 2 O(n) follows from improvements

3

The main differences are the following.

(1) [6, Theorem 10] considers non-strict twin-width, and excludes mixed minors rather than grids, allowing dense graphs and matrices. (2) In general, excluding a k-mixed minor yields a division sequence of width f (k), but with a different order of rows and columns. Only when excluding grids in bounded degree matrices can we ensure a division sequence for the same order. (3) In the general case, the bound on f is doubly exponential.

supremum over finite submatrices. In the rest of this section, we will leave implicit this kind of considerations for infinite graphs and matrices, when they pose no particular problem.

3.1.4. Grid number of graphs. Given a finite graph G and a partition sequence of width k, one can always find a total order < on V (G) such that the partitions of that sequence only consist of intervals. For this order, the partition sequence immediately translates to a division sequence of width k + 1 in the adjacency matrix A < (G). This suggests the following definition: The grid number of G, denoted gn(G), is the minimum of gn(A < (G)) over all choices of < total order on V (G).

Similarly to matrices, the grid number of an infinite graph is the supremum of grid number over finite induced subgraphs, but here an additional argument is needed to order the infinite graph. Proof. For each finite induced subgraph H of G, fix an order < H witnessing that H has grid number at most k. Recall that G is direct limit of its finite induced subgraphs, hence by Lemma 2.1, there is an order < on G such that for any finite X ⊂ V (G), < coincides with < H on X for some finite induced subgraph H containing X.

We claim that G has grid number at most k with regards to order <. Indeed, suppose on the contrary that G has a (k + 1)-grid in this order. By Remark 3.1, this grid is formed by just (k + 1) 2 elements of G. Choose H finite subgraph such that < and < H coincide on these elements. The same elements give a (k + 1)-grid for H ordered by < H , a contradiction.

We can now adapt Theorem 3.2 to graphs. Proof. In the finite case, this is a simple variant of Theorem 3.2, where we preserve the symmetry between rows and columns in the adjacency matrix while building the division sequence (see [START_REF] Bonnet | Twinwidth I: tractable FO model checking[END_REF]Theorem 14]). Lemma 3.3 is used to prove the infinite case. ordered in the natural way, i.e. a < a ′ in A implies X a < X a ′ in X, while the order inside each X a is preserved, and similarly for Y .

1 1 1 1 ⊗ 1 1 = 1 1 1 1 1 1 1 1
Figure 4. The tensor product corresponds to substituting each 1-coefficient of the left matrix by the right matrix.

Let f : A → B be a bijection, and for each a ∈ A let g a : X a → Y f (a) also be a bijection. Then, the substitution of a by g a in f is the bijection f [a := g a ] a∈A : X → Y obtained by combining the g a along f , i.e.

for x ∈ A, y ∈ X x f [a := g a ] a∈A (x, y) def = (f (x), g x (y)).
In terms of matrices, we also write M f [(a, f (a)) := M ga ] for M f [a:=ga] , and call it the substitution of (a, f (a)) by M ga in M f .

A common special case of the above is when the maps g a are all isomorphic to some g : Proof. In the finite case, this is [START_REF] Guillemot | Finding small patterns in permutations in linear time[END_REF]Proposition 3.4]: in M f [a:=ga] , one begins by regrouping each block M ga in a single part using a division sequence for M ga . After this, the remaining quotient matrix is exactly M f .

C → D. Then X = A × C, Y = B × D are ordered lexicograph- ically, and f [a := g] a∈A is the product map (f, g), while M (f,g) = M f ⊗ M g is a tensor product, see
The infinite case reduces to the finite one by remarking that any finite submatrix of M f [a:=ga] is obtained by substituting finite submatrices of some M ga into a finite submatrix of M f . Because twin-width is defined through finite submatrices, the above argument still holds for infinitely nested substitutions. To avoid overwhelming notations, we will only use it for infinite tensor products. Lemma 3.6. Let (I, < I ) be a well-ordered set of indices, and for each i ∈ I consider (X i , < X i ), (Y i , < Y i ) two totally ordered sets, and

f i : X i → Y i a bijection. Consider the products X def = i∈I X i , Y def = i∈I Y i .
They are totally ordered by lexicographic order, i.e. for x =

x ′ x < X x ′ ⇐⇒ x i < X i x ′ i where i def = min j∈I x j = x ′ j .
Let f : X → Y be the product of all f i . Then

stww(M f ) = sup i∈I stww(M f i ).
Proof. Let M ′ be a finite submatrix of M f on rows X ′ and columns Y ′ . It suffices to bound stww(M ′ ) by the right-hand side of the lemma. For each pair of distinct elements of X ′ or Y ′ , consider the minimal index in I on which these elements differ, and let J be the (finite) collection of all these indices. Define X J = j∈J X j and Y J = j∈J Y j , equipped with the projections π X : X → X J and π Y : Y → Y J . Consider the bijection f J : X J → Y J obtained by product of (f j ) j∈J . By construction, π X is injective from X ′ to X J , and similarly for π Y . Furthermore, it is clear that if y = f (x), then π Y (y) = f J (π X (x)). Finally, if X J and Y J are again ordered lexicographically, π X and π Y are non-decreasing. From this it follows that stww(M ′ ) stww(M f J ), and since M f J is a finite tensor product of (M f j ) j∈J , we have stww(M f J ) sup i∈I stww(M f i ) as desired.

3.2.2. Superposition. Given M, N two X × Y matrices, define their superposition M ∨ N as the X × Y matrix with

(M ∨ N )(x, y) def = max (M (x, y), N (x, y)) .
A variant of the next lemma was recently observed [2, Lemma 18].

Lemma 3.7. If M 1 , . . . , M r are X × Y matrices with gn(M i ) < k, then gn ( r i=1 M i ) < r rk .
Proof. A classical Ramsey theory argument gives the following.

Claim 3.8. For any k ∈ N, fix ℓ = r rk . Then for any ℓ × ℓ matrix M whose coefficients are colors in {1, . . . , r}, there exists a k × k submatrix of M consisting of only one color. Now assume that r i=1 M i contains a ℓ-grid. Consider the quotient matrix corresponding to this grid, and color a zone Z with the minimum i such that Z is non-zero in M i . There must be such an i for each zone since all zones are non-zero in the superposition of all M i . The claim then gives a k×k submatrix with a single color i, which induces a k-grid in M i .

Bounded quotients.

Lemma 3.9. Let G be a graph and P a partition of V (G) such that every part P ∈ P has size |P | k. Then stww(G) k stww(G/P).

Proof. Given a partition sequence for G/P of width t, it can be extended to a partition sequence for G by first going from the partition in singletons of G to P in an arbitrary manner. During this process, the quotient graphs are of the form G/P ′ , where every part of P ′ is contained in some part of P. Since every P ∈ P has size at most k, it contains at most k distinct parts of P ′ , which clearly implies that ∆(G/P ′ ) k∆(G/P). It follows that stww(G) max (stww(G/P), k∆(G/P)) . and the right-hand side is bounded by k stww(G/P). A graph G with a partition P. In both G (2) /P and (G/P) (2) , parts A and B are adjacent because of the path a 1 , d, b. In (G/P) (2) only, A and C are adjacent thanks to the path a 1 , d, e, c, which can 'jump' from d to e since they are in the same part of P.

3.2.4.

First-order interpretations. If C is a class of finite graphs of bounded twin-width, then any first-order transduction of C also has bounded twinwidth [START_REF] Bonnet | Twinwidth I: tractable FO model checking[END_REF]Theorem 39]. However, this result only holds with non-strict twin-width, because first-order transductions can produce dense graphs from graphs of bounded degree. In our setting, we will only consider two special cases of interpretations which preserve bounded degree: powers of graphs, and composition of permutation matrices. We give simpler ad hoc proofs for these cases.

Let G be a graph. The k-th power of G, denoted by G (k) , is the graph with the same vertices as G, and such that x = y are adjacent in

G (k) if and only if d G (x, y) k. Remark that (2) ∆(G (k) ) (∆(G)) k .
Lemma 3.10. For any k ∈ N, and any graph G,

stww(G (k) ) stww(G) k .
Proof. We prove the finite case. If P is a partition of V (G), one verifies that (3) G (k) /P is a subgraph of (G/P) (k) .

Indeed, for X, Y ∈ P, there is an edge XY in G (k) /P if and only if there are x ∈ X, y ∈ Y and a path of length at most k in G from x to y. When that is the case, the parts containing the successive vertices of this path yield a path from X to Y of length at most k in G/P, see Figure 5. Now if P n , . . . , P 1 is a partition sequence of width t for G, then (G/P i ) (k) has degree bounded by t k by (2), hence so does G (k) /P i . Thus P n , . . . , P 1 is also a partition sequence of width at most t k for G (k) . Lemma 3.11. If σ : X → Y , τ : Y → Z are bijections between totally ordered sets with stww(M σ ), stww(M τ ) t, then

stww(M τ •σ ) = 2 O(t) .
Proof. By Theorem 3.2, assume that gn(M σ ), gn(M τ ) t ′ with t ′ = O(t). We order X ⊎ Z with X < Z, and consider the (X ⊎ Z) × Y matrix M consisting of M σ and M τ -1 put side by side (remark that M τ -1 is the transpose of M τ ). Clearly, gn(M ) 2t ′ + 1, hence by Theorem 3.2, there is a division sequence

(R n , C n ), . . . , (R 1 , C 1 ) of M of width 2 O(t) .
Let us construct a division sequence (X n , Z n ), . . . , (X 1 , Z 1 ) for M τ •σ . The partition X i of X into intervals is obtained by restricting R i to X, i.e.

X i def = {R ∩ X | R ∈ R i ∧ R ∩ X = ∅} .
The partition Z i of Z is defined similarly. It is easy to verify that for any i, either (X i , Z i ) = (X i+1 , Z i+1 ), or (X i , Z i ) is obtained by merging two parts in either X i+1 or Z i+1 . Hence, up to some trivial cleanup, this is a division sequence for M τ •σ .

We need to bound the degree of the quotient matrices

M τ •σ /(X i , Z i ). Let X ′ ∈ X i be a part, obtained as X ′ = X ∩ R for some R ∈ R i . Say that Y ′ ∈ C i is a neighbour of X ′ if there exists x ∈ X ′ with f (x) ∈ Y ′ . The number of neighbours of X ′ in C i is bounded by the degree of R in M/(R i , C i ). Similarly, for Y ′ ∈ C i , say that Z ′ ∈ Z i is a neighbour of Y ′ if there exists y ∈ Y ′ with g(y) ∈ Z ′ . Again, the number of neighbours of Y ′ in Z i is bounded by the degree of Y ′ in M/(R i , C i ). Now, if Z ′ ∈ Z i is such that there exists x ∈ X ′ with g(f (x)) ∈ Z ′ , then Z ′ is a neighbour in Z i of a neighbour in C i of X ′ . It follows that the degree of X ′ in M τ •σ /(X i , Z i ) is bounded by the square of the maximum degree in M/(R i , C i ), which is still 2 O(t)
. The same holds for the degree of a part Z ′ ∈ Z i .

Thus we have constructed a division sequence for M τ •σ of width 2 O(t) .

The former proof could be adapted to show that the composition of k bijection matrices of twin-width t has twin-width 2 O(tk) , instead of the tower of exponentials obtained repetitively applying the former lemma.

Twin-width as a geometric group invariant

In [3, Lemma 8.2], we already proved finite twin-width is a group invariant. This can be stated as a more general result on regular embeddings.

Lemma 4.1. If f : H → G is a λ-regular embedding, then stww(H) λ stww(G) λ . Proof. Let P = f -1 (v) | v ∈ V (G) be the preimage partition of V (H).
Since f is λ-regular, parts of P have size at most λ. One can see f as a map f : H/P → G, which is injective and λ-Lipschitz. This implies that H/P is isomorphic to a subgraph of G (λ) . Then, by Lemmas 3.9 and 3.10,

stww(H) λ stww(H/P) λ stww(G) λ .
Since quasi-isometries between graphs of bounded degree are regular embeddings, it follows that having finite twin-width is invariant under quasiisometry for graphs of bounded degree. In particular, whether or not a Cayley graph Cay(Γ, S) has finite twin-width depends only on the group Γ, not on the generating set S. This defines the notion of finite twin-width for finitely generated groups.

Let us give some simple examples.

(1) Finite groups trivially have finite twin-width.

(2) It is easy to see that the strict twin-width of a tree is exactly its maximum degree. Thus, the free group with k generators has finite twin-width, since it admits the k-regular tree as Cayley graph. (3) A cartesian product of groups corresponds to the cartesian product of Cayley graphs, which is known to preserve finite strict twin-width (see [START_REF] Bonnet | Twin-width II: small classes[END_REF]Theorem 7.2]). ( 4) By ( 1) and ( 2), all cyclic groups have finite twin-width, and thus by ( 3), all finitely generated abelian groups have finite twin-width. Finite twin-width being closed under quasi-isometry, it is natural to wonder if other well-known properties of groups preserved by quasi-isometry imply finite twin-width. Hyperbolicity in the sense of Gromov [START_REF] Gromov | Hyperbolic groups[END_REF] is arguably the most important quasi-isometric invariant of groups. By a remarkable result of Buyalo, Dranishnikov, and Schroeder, hyperbolic groups-and more generally, hyperbolic graphs of bounded degree-are quasi-isometric to finite Cartesian products of trees of bounded degree [START_REF] Buyalo | Embedding of hyperbolic groups into products of binary trees[END_REF]. Since trees of bounded degree have finite twin-width, and Cartesian products preserve it, we obtain the following. Proposition 4.2. groups and graphs of bounded degree have finite twin-width.

Matrix characterisation

In this section, we give a second characterisation of twin-width through matrices. This allows to generalise it beyond finitely generated groups, and suggests a natural strengthening, called uniform twin-width.

5.1.

Twin-Width of group actions. Let Γ be a group acting on X by φ : Γ → S X , where S X is the group of permutations on X. Given a total order < on X and g ∈ Γ, the (strict) twin-width of g acting on (X, <) is

stww (X,<) (φ(g)) def = stww M φ(g) ,
where the X × X bijection matrix M φ(g) is ordered according to <.

The action of Γ through φ is said to have finite twin-width with regards to < if stww (X,<) (φ(g)) is finite for every g ∈ Γ-but possibly arbitrarily large. This action is said to have finite twin-width it has finite twin-width with regards to some total order on X. Finite grid number for a group action is defined similarly. Lemma 5.1. For a finitely generated group Γ, the following are equivalent.

(1) Some (equivalently, every) Cayley graph of Γ has finite twin-width (equivalently, finite grid number).

(2) The action of Γ on itself by right product has finite twin-width (equivalently, finite grid number).

Proof. In the statement, equivalences of finite twin-width and finite grid number are from Theorems 3.2 and 3.4. For x ∈ Γ and < a total order on Γ, we denote by M < x the matrix of the action of x on (Γ, <) by right product. Suppose that the action of Γ on itself has finite grid number, witnessed by some total order < on Γ. Let us prove that Cay(Γ, S) has finite grid number for an arbitrary finite generating set S. Let M be the adjacency matrix of Cay(Γ, S) with regards to <. Then M is the superposition

M = s∈S∪S -1 M < s Any single M <
x has finite grid number by hypothesis, and S ∪ S -1 is finite, thus it follows from Lemma 3.7 that M has finite grid number.

Conversely, assume that Cay(Γ, S) has finite grid number for some finite generating set S. This is witnessed by a total order < on Γ such that the adjacency matrix M of Cay(Γ, S) with regards to < has finite twin-width. For any s ∈ S ∪ S -1 , one easily verifies that M < s is contained in M , in the sense that M < s (x, y) = 1 implies M (x, y) = 1. It follows that M < s has finite twin-width. If x ∈ Γ is now an arbitrary element, x can be decomposed as some product x = s 1 . . . s n with s i ∈ S ∪ S -1 , and the action of x is the composition of the actions of s 1 , . . . , s n . Since all M < s i have finite twin-width, it follows from Lemma 3.11 that M <

x has finite twin-width.

Thus we can take as alternative definition that Γ has finite twin-width if its action on itself by right product has finite twin-width. This definition immediately generalises to non-finitely generated groups.

Uniform twin-width.

There is a natural strengthening of the former characterisation. Consider an action of Γ on X given by φ : Γ → S X . Given a total order < on X, the uniform twin-width of φ with regards to < is

utww (X,<) (φ) def = sup g∈Γ stww (X,<) (φ(g)).
Then, the uniform twin-width of φ, denoted by utww(φ), is the minimum of utww (X,<) (φ) over all choices of < total order on X. The uniform twinwidth of a group Γ, denoted utww(Γ), is defined as the uniform twin-width of its action on itself by right product.

Unlike twin-width, the uniform twin-width of a group or group action is a well defined number (or infinity). For some fixed ordering, having finite uniform twin-width requires a uniform bound on the twin-width of the actions of each element, whereas having finite twin-width only requires the twin-width of each of these actions to be finite. Thus finite uniform twinwidth implies finite twin-width, while the converse is not a priori true.

Examples. Let us refine the examples of section 4.

A right-invariant order on a group Γ is a total order < such that for all x, y, z ∈ Γ, x < y implies xz < yz. A group is (right-)orderable if it admits a right-invariant total order. Groups of finite twin-width can be seen as a vast generalisation of orderable groups. Indeed, if < is a right-invariant order on Γ, then the action of any x ∈ Γ by right product is monotone, hence its matrix has strict twin-width 2 (the minimum possible value for non-trivial matrices). Proposition 5.2. Right-orderable groups have uniform twin-width 2.

Finitely generated free groups are known to be orderable, hence have uniform twin-width 2. It is easy to see that finite cyclic groups, with the natural order, also have uniform twin-width 2. Using Lemma 3.5, we obtain that Cartesian product preserves uniform twin-width, i.e.

utww(Γ 1 × Γ 2 ) = max(utww(Γ 1 ), utww(Γ 2 )).
This is witnessed by a lexicographic order on Γ 1 × Γ 2 . Therefore all finitely generated abelian groups have uniform twin-width 2.

Groups with finite twin-width

In this section, we prove that uniform twin-width is preserved by a number of group constructions, and use these results to provide examples of groups with finite twin-width. Here, unlike the rest of the paper, we use G, H etc. to denote groups and not graphs.

Let us start with the trivial remark that twin-width is monotone under taking subgroups. It is used for lower bounds in results of this section. Lemma 6.1. If G is a group, H G is a and G has finite twinwidth, then so does H, and utww(H) utww(G).

6.1. Limits. The characterisation of twin-width through matrices allows generalisation to infinitely generated groups. However, uniform twin-width can be reduced to the case of finitely generated groups, because it is stable by direct limits. Lemma 6.2. If G is direct limit of (G i ) i∈I , then

utww(G) = sup i∈I utww(G i ).
Proof. For each G i , let < i be an order witnessing that utww(G i ) k. By Lemma 2.1, there is an order < on G such that for any finite X ⊂ G, the orders < and < i coincide on X for some i.

For x ∈ G, let M x be the matrix of x acting on (G, <) by right product. We want to show stww(M x ) k, i.e. that for every finite submatrix M of M x , stww(M ) k. Let X contain the row and column indices of M , plus x. Since X is finite, there is some i with X ⊂ G i and such that < and < i coincide on X. Then M is a submatrix of the matrix of x acting on (G i , < i ) by right product, hence stww(M ) k, which implies the result. Proof. The group G is direct limit of H.

In section 5.3, we already proved that finitely generated abelian groups have uniform twin-width 2. Applying Corollary 6.3, we obtain Proposition 6.4. Abelian groups have uniform twin-width 2.

6.2. Products, subgroups, and quotients. In sections 4 and 5.3, we made the remark that (uniform) twin-width is stable under Cartesian product. We will now give a significant generalisation of this result.

Let G be a group and H G. We write G/H for the right quotient, i.e. the set of right cosets {Hg | g ∈ G}. Then, G acts on G/H by right product, and we abusively talk about the (uniform) twin-width of G/H when meaning the (uniform) twin-width of this action. When H is a normal subgroup, the (uniform) twin-width of G/H as group indeed coincides with that of G acting on G/H, justifying this convention. Lemma 6.5. For any group G and H G, the following statements hold.

(1) utww(G) max (utww(H), utww(G/H)).

(2) If H has finite uniform twin-width and G/H has finite twin-width, then G has finite twin-width.

(3) If H has finite twin-width and G/H is finite, G has finite twin-width.

Before proving it, we list some direct, useful corollaries, with more natural statements. Proof of Lemma 6.5. For x ∈ G, let

Corollary 6.6. If G is an extension of Q by H, i.e. H ⊳ G and Q ∼ = G/H utww(G) max(utww(H), utww(Q)). Corollary 6.7. If G ⋊ H is any semi-direct product, then utww(G ⋊ H) = max(utww(G), utww(H)).
x def = Hx be its equivalence class in G/H. We choose a transversal T ⊂ G of G/H, meaning that each class of G/H can be uniquely written as t for some t ∈ T . Suppose given total orders < H , < G/H on H and G/H witnessing their twin-width or uniform twin-width. We define a total order < on G as follows.

• The order between cosets is defined by

x < G/H ȳ =⇒ x < y.
• For t ∈ T , the order inside the coset t is defined by

∀x, y ∈ t, x < y ⇐⇒ xt -1 < H yt -1 .
For a ∈ G, let M G a be the matrix of a acting on G by right product with regards to <. Proof. Let t 1 , t 2 ∈ T be such that t 1 at -1 2 ∈ H, or equivalently, right multiplication by a maps the coset t1 = Ht 1 to t2 = Ht 2 . In that case, define P t 1 ,t 2 a to be the matrix of this map, where Ht 1 and Ht 2 are ordered as in G. It is easy to verify that M G a is obtained from M G/H a by substituting the '1' at position ( t1 , t2 ) by P t 1 ,t 2 a for all such choices of t 1 , t 2 , see Figure 6. Thus, by Lemma 3.5, it suffices to prove stww(P ) k follows from the hypotheses.

We now prove the three points of the lemma using the claim.

(1) is immediate.

(2) Given a uniform bound on stww(M H r ) for all r ∈ H, and a bound on stww(M G/H a ), the claim gives a bound on stww(M G a ). Remark that since the bound on stww(M H r ) is used for r = t 1 at -1 2 for all appropriate choices of t 1 , t 2 , the uniform bound is a priori required.

(3) If G/H is finite however, there are only finitely many r = t 1 at -1 2 for which the bound on stww(M H r ) is used (for a fixed), hence the uniform bound in the previous argument is no longer required.

With the previous results, we can give interesting examples of groups with finite twin-width. The class of solvable groups can be defined inductively as follows.

• The trivial group is solvable.

• If H ⊳ G, H is solvable, and G/H is abelian, then G is solvable. Solvable groups notably contain nilpotent groups. Proposition 6.10. Solvable groups have uniform twin-width 2.

Proof. Immediate by Proposition 6.4 and Corollary 6.6.

If Γ is a group finitely generated by S, its growth function is

g (Γ,S) (r) def = |B(1 Γ , r)|,
where B(1 Γ , r) is the ball of radius r centered on the identity element in Cay(Γ, S). This function depends on the choice of S, but whether or not it is a polynomial, or exponential function, is independent of S. This defines the classes of groups with polynomial or exponential growth.

By a celebrated result of Gromov, groups of polynomial growth are virtually nilpotent. Theorem 6.11 (Gromov [16]). If G is a group of polynomial growth, then G admits a nilpotent subgroup H of finite index. Proposition 6.12. Groups of polynomial growth have finite uniform twinwidth.

Proof. Immediate by Theorem 6.11, Proposition 6.10, and Corollary 6.8.

When H ⊳ G, Lemma 6.5 gives an upper bound on utww(G) by utww(H) and utww(G/H). There is also a trivial lower bound utww(G) utww(H). However utww(G/H) gives no lower bound on utww(G) in general: it can be that utww(G) = 2 and G/H has infinite twin-width, namely when G is a free group and G/H, a finitely generated group with infinite twin-width. We can however give a result when H is finite. Lemma 6.13. Let G be a group and N ⊳ G normal subgroup with |N | = t < ∞. Then G has finite twin-width if and only if G/N does. Furthermore utww(G) max(utww(G/N ), t), and

utww(G/N ) 2 t O(utww(G)•t) .
Proof. Using Corollary 6.6 and the trivial bound utww(N ) t, if G/N has finite twin-width then so does G, and utww(G) max(utww(G/N ), t).

For the converse, consider a total order < on G witnessing its twin-width. For a ∈ G/N , choose a representative ι(a) ∈ a. These are used to order G/N according to <, by

∀a, b ∈ G/N, a < G/N b ⇐⇒ ι(a) < ι(b). For x ∈ G, let M G
x be the matrix of x acting on (G, <) by right product, and similarly in G/N . Fix some a ∈ G/N . We want a bound on stww(M

G/N a

). Define the matrix S with (G/N, <) as row and column indices by

∀b 1 , b 2 ∈ G/N, S(b 1 , b 2 ) = 1 ⇐⇒ ι(b 1 ) -1 ι(b 2 ) ∈ a.

It can be seen as the superposition of M G

x for x ∈ a, restricted to the submatrix with ι(G/N ) as indices.

If b 1 a = b 2 , then ι(b 1 ) -1 ι(b 2 ) ∈ a, which in matrices means that M G/N a (b 1 , b 2 ) = 1 implies S(b 1 , b 2 ) = 1. It follows that stww(M G/N a
) stww(S).

Suppose now that utww(G)

k is witnessed by the order <, meaning that for x ∈ G, stww(M G x ) k. Using Theorem 3.2 and Lemma 3.7, and that S is contained in the superposition of t matrices M G x , we obtain

stww(M G/N a ) stww(S) 2 t O(tk) .
If G merely has finite twin-width witnessed by <, there still is a bound on stww(M G x ) for x ∈ a with a fixed, because a is finite. The same arguments show that stww(M G/N a

) is finite, hence G/N has finite twin-width. 6.3. Infinite products and wreath products. Given (G i ) i∈I a family of groups, their direct product is denoted by i∈I G i . Their direct sum i∈I G i is the subgroup of the direct product consisting of finitely supported tuples, i.e. the (x i ) i∈I with x i ∈ G i such that all but finitely many x i are the neutral element. When I is finite, the two notions coincide. Lemma 6.5 of course implies that finite products preserve twin-width and uniform twin-width. This can be generalised to infinite direct sum, and for uniform twin-width only, to infinite direct products. Lemma 6.14. Given (G i ) i∈I a possibly infinite family of groups, consider S = i∈I G i their direct sum, and P = i∈I G i their direct product. Then S has finite twin-width if and only if all G i do, and

utww(S) = utww(P ) = sup i∈I utww(G i ).
Proof. Choose some well-order on I, a total order < i on each G i witnessing its twin-width, and order S and P lexicographically. Assuming that utww(G i ) k is witnessed by < i , Lemma 3.6 immediately gives utww(P ) k, and a fortiori utww(S) k. This proves the equalities on uniform twin-width.

For the claim on non-uniform twin-width, assume that all G i have finite twin-width witnessed by < i , and let x = (x i ) i∈I ∈ S. Again the matrix of x acting on (S, <) is the tensor product of the matrices of x i acting on (G i , < i ). Since x is finitely supported, all but finitely many of these matrices are identity, while the remaining ones have finite twin-width. Thus there is a universal bound on the twin-width of these matrices, and we conclude using Lemma 3.6 once again.

Given any groups G, H, one can define the (complete) wreath product

G ≀ H def = G H ⋊ H
where H acts by permuting indices by right product, i.e. for h, h ′ ∈ H and x ∈ G H , the action of h is

(x • h)(h ′ ) def = x(h ′ h).
One may also consider the restricted wreath product, with a direct sum replacing the direct product, and the same action of H.

G ≀ r H def = h∈H G ⋊ H.
It is a subgroup of the complete wreath product. Lemma 6.15. utww(G ≀ H) = max(utww(G), utww(H)).

Proof. By Lemma 6.14 and Corollary 6.7.

Interesting groups can be constructed through wreath products, the most common example being the lamplighter group (Z/2Z) ≀ r Z, which therefore has uniform twin-width 2.

6.4. Group actions. The twin-width of a group is defined through its selfaction by product. In this section, we consider the twin-width of other actions, and show a relation to the twin-width of the group. Lemma 6.16. Let (X, < X ) be a well-ordered set. Then there exists a total order < S X on the permutation group S X such that for σ ∈ S X stww S X (σ) stww X (σ)

where the right-hand side is the twin-width of σ acting on (X, < X ), whereas the left-hand side is the twin-width of σ acting on (S X , < S X ) by product. Proof. To respect the convention that twin-width is defined with regards to right product, we will use postfix notations for S X , i.e. for σ, τ ∈ S X and x ∈ X, we write x • σ = σ(x) and στ = τ • σ.

We order X X lexicographically, i.e. for any f = g : X → X, define

m f,g = min {x ∈ X | x • f = x • g} and f < X X g ⇐⇒ m f,g • f < X m f,g • g.
The group S X acts on X X by post-composition, that is

(f • σ)(x) = f (x) • σ.
We define < S X by restricting the former order from X X to S X , while the restriction of this action is simply right product. For σ ∈ S X , let M σ be the matrix of σ acting on (X, < X ), let M X σ be the matrix of σ acting on (X X , < X X ) by post-composition, and let M S X σ be the matrix of σ acting on (S X , < S X ) by right product. Then M X σ is a tensor product of M σ with itself, hence by Lemma 3.6, we have stww(

M X σ ) = stww(M σ ). Furthermore M S X σ is clearly a submatrix of M X σ , thus stww S X (σ) = stww(M S X σ ) stww(M X σ ) = stww(M σ ) = stww X (σ).
Corollary 6.17. Let (X, < X ) be a well-ordered set, and G group acting faithfully on X on the right. If this action has finite twin-width with regards to < X , then G has finite twin-width. Furthermore if this action has uniform twin-width k with regards to < X , then utww(G) k.

Proof. Through the faithful action, G is a subgroup of S X .

Let T be the infinite rooted binary tree. Let Aut(T ) be the group of automorphisms of T , i.e. bijections on nodes of T which preserve the root and the parent relation. The group Aut(T ) is uncountable, but it has some interesting finitely generated subgroups, notably the Grigorchuk group [START_REF] Ivanovich | Burnside problem on periodic groups[END_REF]. Proposition 6.18. The group Aut(T ) has uniform twin-width 2.

Proof. Let < be the breadth-first search order on T , which orders first by increasing depth, then left-to-right at each level. This is a well-order, hence by Corollary 6.17 it suffices to prove that the action of Aut(T ) on T with regards to < has uniform twin-width 2.

Let f ∈ Aut(T ), and for d ∈ N let f d be the action of f restricted to nodes of depth d. Then the bijection matrix M f d is obtained by substituting the 2-by-2 diagonal and anti-diagonal matrices inside M f d-1 . It follows by Lemma 3.5 that stww(M f d ) = 2 for all d. (These are separable permutation matrices, see [START_REF] Guillemot | Finding small patterns in permutations in linear time[END_REF]Section 3.2].) Finally, the matrix of f can be seen as the N × N diagonal matrix, with coefficient (d, d) substituted by M f d , hence it has twin-width 2 by Lemma 3.5 again. 6.5. Uniform and non-uniform twin-width. Any group with finite uniform twin-width also has finite twin-width. We conjecture that the converse does not hold, and we think the following is a good candidate for a counterexample.

Let S Z be the group of permutations on Z, and let S f Z be the subgroup consisting of finitely supported permutations. Furthermore, let T = {x → x + c | c ∈ Z} the subgroup of translations. While S f Z is not finitely generated, S f Z ⋊T is. The latter is sometimes called lampshuffler group. Consider the well-order 0, 1, -1, 2, -2, . . . on Z. The transposition of 0 and 1 and the translation by 1 are two permutations of Z which generate S f Z ⋊T , and whose action on Z clearly has finite twin-width. Thus, by Lemma 3.11, the action of the lampshuffler on Z has finite twin-width, and by Corollary 6.17, so does the lampshuffler group itself.

We conjecture that the lampshuffler has infinite uniform twin-width, and thus separates uniform and non-uniform twin-width. A justification for this conjecture is that the lampshuffler having finite uniform twin-width would imply a universal bound on the uniform twin-width of finite groups, and more generally of elementary amenable groups (the groups obtained from finite groups and abelian groups by taking subgroups, quotients, extensions, and direct limits). This would be surprising. Proposition 6.19. The following are equivalent for any k ∈ N.

(1) For all finite group G, utww(G) k.

(2) utww(S f Z ⋊T ) k.

(3) For all elementary amenable group G, utww(G) k.

Proof. The lampshuffler S f

Z ⋊T is elementary amenable and contains all finite groups, hence (3) implies (2) which implies [START_REF] Bilu | Lifts, discrepancy and nearly optimal spectral gap[END_REF]. Suppose now that all finite groups have uniform twin-width at most k, and recall that abelian groups have uniform twin-width 2. Remark that k 2, because only the trivial group has twin-width 1. It is known that all elementary amenable groups can be obtained from finite groups and abelian groups using only extensions and direct limits [START_REF] Chou | Elementary amenable groups[END_REF]. It follows by Corollary 6.6 and Lemma 6.2 that all elementary amenable groups have twin-width at most k.

One could replace S f

Z ⋊T with just S f Z in the result: they have the same uniform twin-width by Corollary 6.7.

Remark that the previous result means that if all elementary amenable groups have finite uniform twin-width, then there is in fact a universal bound on their uniform twin-width, because the lampshuffler is elementary amenable.

Constructing groups with infinite twin-width

This section constructs a finitely generated group with infinite twin-width. 7.1. Embedding graphs of high twin-width. The construction embeds an appropriate sequence of graphs with bounded degree and unbounded twinwidth in a Cayley graph. The existence of such graphs is given by counting arguments (see Theorem 1.2). The embedding into a group uses the following result of Osajda, based on graphical small cancellation theory.

∆(G n ) D, (2) girth
(G n ) girth(G n-1 ) + 6, and

(3) diam(G n )/girth(G n ) A. Then there exists a group Γ finitely generated by S such that every G n isometrically embeds in Cay(Γ, S).

To obtain a finitely generated group of infinite twin-width, it suffices to construct a sequence of graphs satisfying these hypotheses, and which furthermore has unbounded twin-width. Precisely, the sequence we construct satisfies the following4 :

(1) Each G n has maximum degree at most 6, (

) diam(G n ) 3 log |V (G n )|, and 2
(G n ) > 1 4 log |V (G n )|. (3) girth
For n ∈ N, we write [n] = {1, . . . , n}. For n even, let C 1 (n) be the class of edge-labeled graphs on vertex set [n] which are formed by the union of three perfect matchings with labels 1, 2, and 3 (these graphs may have multiple edges). This class is not small. Lemma 7.2. For any constant c and any sufficiently large even n,

|C 1 (n)| > n! • c n .
Proof. The class C 1 (n) contains all possible choices of 3 perfect matchings from {1, . . . , n/2} to {n/2 + 1, . . . , n}. There are (n/2)! 3 such choices, i.e. at least n! 3/2 up to some exponential factors, which is asymptotically larger than n! • c n .

Fix n ∈ N even and define g def = log(n)/4. Define C 2 (n) the class of graphs on vertex set [n] with degree at most 6, diameter at most 3 log n and girth at least g. Let us show that at least half of C 1 (n) can be obtained from graphs of C 2 (n) by editing (adding or removing) at most n 7/8 edges and adding labels 1, 2, 3 to edges. Lemma 7.3. If G is a graph chosen uniformly at random in C 1 (n), then the expected number of cycles in G of length at most g is at most 2 • 6 g . Proof. Let C be a potential cycle of length ℓ g properly edge-colored with 1, 2, 3; that is, a sequence v 1 , . . . , v ℓ of vertices in [n] where each potential edge v i v i+1 (with indices modulo ℓ) is given a label in 1, 2, 3, and such that consecutive edges have distinct labels. Let us bound the probability that C appears as a cycle with the assigned colors in G.

When choosing a random perfect matching M on n vertices (n even), the probability that a given pair of vertices belongs to M is n 2 / n 2 = 1 n-1 . If these probabilities were independent, C would appear in G with probability exactly (n -1) -ℓ . But the fact that each color class of G forms a matching introduces a small dependency: Conditioned by the fact that t edges of a random perfect matching M are already known, the probability that a given pair of not yet matched vertices appears in M is 1/(n -2t -1). Now if these already known edges are part of C, then t ℓ g ≪ n, hence this probability is upper bounded by 2/n. Thus the probability that C appears in G is at most (2/n) ℓ . Therefore the expected total number of cycles of length at most g in G is at most

g i=2 3 i • n i • (2/n) i 2 • 6 g .
Lemma 7.4. For any even n, for at least half of the graphs

G = (V, E) in C 1 (n), there exists G ′ = (V, E ′ ) in C 2 (n) such that |E△E ′ | = O(n 7/8 ),
where △ denotes the symmetric difference.

Proof. By Lemma 7.3 and Markov's inequality, at least half of the graphs G 1 in C 1 (n) have at most 4•6 g cycles of length at most g. Let G 1 be such a graph, and choose F ⊂ E(G 1 ) of size at most 4 • 6 g intersecting every cycle of length at most g in G 1 (simply choose an edge in each such cycle). Let G 2 be the subgraph of G 1 obtained by deleting the edges of F . By construction, G 2 has girth more than g. We will now add edges to G 2 to ensure its diameter is at most 3 log n without creating new short cycles.

Let Z be the set of endpoints of edges in F . Thus |Z| 8 • 6 g . Let N be the union of closed balls of radius g/2 centered on vertices of Z. Since G 2 has maximum degree 3, for any fixed vertex x, the ball of radius d around x in G 2 contains at most 3

• 2 d vertices. It follows that (5) |N | 8 • 6 g • 3 • 2 g/2 = 24 • (6 √ 2) g 24 • n log(6 √ 2)/4 .
Observe that log(6 √ 2)/4 7/8, hence

|N | 24 • n 7/8 . (6)
Choose X an inclusion-wise maximal subset of V (G 2 ) such that vertices in X pairwise have distance at least log n in G 2 . Define X 1 = X ∩ N , and X 2 = X \ N . Let v ∈ X 2 , and let B v be the closed ball of radius g/2 in G 2 . Since v is at distance more than g/2 from Z, no edge of G 1 was removed inside this ball, hence all vertices of B v have degree 3. Furthermore, because G 2 has girth more than g, G 2 restricted to B v is a tree, except possibly for edges between vertices at distance g/2 from v which we may ignore. This implies ( 7)

|B v | 2 g/2 = n 1/8 .
Finally, any distinct v, v ′ ∈ X 2 are at distance at least log n, which is more than g. Thus the balls B v and B v ′ are disjoint. It follows from ( 7) that ( 8)

|X 2 | |V (G 2 )| n 1/8 = n 7/8 . Using that X = X 1 ∪ X 2 , X 1 ⊂ N ,
and ( 6) and ( 8), we obtain [START_REF] Cibulka | Füredi-Hajnal limits are typically subexponential[END_REF] |X| = O(n 7/8 ).

Finally, let G 3 be a graph obtained by adding to G 2 a balanced ternary tree T with vertex set X. Thus, vertices in X are pairwise at distance at most log n in G 3 . Furthermore, by maximality of X, all vertices of G 2 are at distance at most log n of X. It follows that the diameter of G 3 is at most 3 log n. Finally, G 3 still has girth at least g, because T only connects vertices of X, which are far apart in G 2 . Clearly the degree of vertices in G 3 does not exceed 6. Thus G 3 ∈ C 2 (n).

To summarize, we transform G 1 into G 3 by deleting |F | 4 • 6 g edges, and then adding |X| edges, which gives O(n 7/8 ) edge editions in total.

Lemma 7.5. The class C 2 is not small. Precisely, for any constant c and any sufficiently large even n,

|C 2 (n)| n! • c n .
Proof. Fix c, consider n even sufficiently large, and suppose for a contradiction that |C 2 (n)| n! • c n . For any graph G on n vertices, the number of graphs which can be obtained from G by editing up to n 7/8 edges is at most [START_REF] Ding | Some results on tree decomposition of graphs[END_REF] n 2 n 7/8 n 2n 7/8 2 n , asymptotically.

Hence the total number of cubic graphs and edges labeled 1, 2, 3 obtained by n 7/8 editions from any graph in C 2 (n) is asymptotically at most (11)

2 n • 3 3n/2 • n! • c n n! • c n 2
for some constant c 2 . By Lemma 7.

′ | < λ • girth(G k ′ ),
where λ > 0 is some fixed constant (the small cancellation parameter). Said shortly: Any two paths with the same labelling must be short, relative to the girth.

The proof makes large use of Lovász Local Lemma. Assuming some appropriate labellings of G 0 , . . . , G k-1 have been chosen inductively, one proves that a random labelling of G k is 'good' with non-zero probability. Crucially, this is an incremental process: to choose the labelling of G k , one only needs to consider G 0 , . . . , G k . It will always be possible to later extend this sequence with an appropriate labelling of G k+1 . This readily gives a naive algorithm, which enumerates all labellings of G k and chooses the first 'good' one, before continuing with G k+1 . Effective algorithms for Lovász Local Lemma such as [START_REF] Moser | A constructive proof of the general Lovász local lemma[END_REF] may be helpful to improve the complexity. 7.2.3. Deciding the word problem. The former labelling of (G k ) k∈N uses labels in S ⊎ S -1 , where S is some finite set, and S -1 denotes the set of formal inverses of S. The group constructed by Theorem 7.1 is then Γ = S; R where the set R of relators contains all words on S ⊎ S -1 read along some cycle of some G k . This set R is recursive: given some word w over S ⊎S -1 , to decide if w ∈ R, one must test if w appears as the labelling of some cycle of some G k . This can only happen if girth(G k ) |w|. Since girth(G k ) increases at least linearly with k, it suffices to check a finite number of graphs in the sequence. This proves the first half of Theorem 7.6.

Decidability of the word problem uses a classical result of small cancellation theory, stated below for the case of finite graphical presentations. Lemma 7.9 (Greendlinger's lemma [START_REF] Ollivier | On a small cancellation theorem of Gromov[END_REF]). Let G be a finite graph equipped with an edge labelling on S ⊎ S -1 satisfying the small cancellation condition. Let R be the set of words read along the cycles of G, and Γ = S; R . If w is a word over S ⊎S -1 which represents the identity of Γ, then some relator r ∈ R can be applied to w to reduce it to w ′ , with |w ′ | < |w|.

Although the above is stated for a finite graph, it generalises to a sequence of finite graphs. Suppose a word w over S ⊎ S -1 represents the identity of Γ. Then there is finite sequence of relators in R which can be applied to w to reduce it to the empty word. These relators are found in finitely many graphs in the sequence (G k ) k∈N , say G 0 , . . . , G s . Then w is also equal to 1 in the group S; R ′ where the relators R ′ are the ones read along some cycle of G 0 ∪ • • • ∪ G s . We conclude by applying Lemma 7.9 to S; R ′ . Where Greendlinger's lemma applies, the word problem can be decided using Dehn's algorithm: given a word w on S ∪ S -1 , try to rewrite it into a strictly smaller word by applying some relator of R, and repeat. If this fails before reaching the empty word, Greendlinger's lemma proves that the word is not equivalent to the neutral element in Γ. This algorithm works for Γ despite the set of relators R being infinite. Indeed, given w of length k, only relators of length less than 2k need to be considered in Dehn's algorithm. There are only finitely many such relators, and they can be enumerated. This concludes the proof of Theorem 7.6

Remarks on queue number

This final section draws some remarks on the relation between twin-width and queue number in the context of groups. Many results of this paper hold when replacing twin-width with queue number. We point out the proofs which fail for queue number, but without counterexamples: separating bounded twin-width and bounded queue number on sparse graphs remains an open question. 8.1. Definition. Consider a graph G with a total order < on V (G). Two edges xy and uv are said to be nested if x < u < v < y, up to symmetries. The graph G is said to be a queue with regards to < if it has no nested edges, and a strict queue if furthermore it is a matching (no two edges share an endpoint). A (strict) t-queue-layout of G is a choice of order < on V (G) and a partition E(G) = t i=1 E i of its edges such that for each i, the graph formed by the edges E i is a (strict) queue with regards to <, see Figure 7. The (strict) queue number of G, denoted qn(G) (resp. sqn(G)) is the smallest t such that G admits a (strict) t-queue-layout. Remark that the strict queue number is at least the maximum degree. Furthermore, if G has maximum degree ∆, given a t-queue-layout, refining the partition of edges with a proper edge coloring gives a strict (∆+1)t-queue layout using Vizing's theorem. Thus [START_REF] Eppstein | Three-dimensional graph products with unbounded stack-number[END_REF] qn(G) sqn(G) (∆ + 1) qn(G),

i.e. the two numbers are equivalent for graphs of bounded degree up to a constant factor. We will focus on the strict queue number.

8.2. Matrix characterisation. Say that an X × Y matrix M is increasing if it is the matrix of an increasing partial map, i.e. whenever there are 1coefficients at positions (x 1 , y 1 ) and (x 2 , y 2 ), either x 1 < x 2 and y 1 < y 2 , or x 2 < x 1 and y 2 < y 1 . In particular, each row and column contains at most a single '1'. Call strict queue number of M the minimum k such that M is equal to the superposition of k increasing matrices. If G is a graph and < an order on V (G) witnessing the strict queue number of G, then one verifies [START_REF] Fox | Stanley-Wilf limits are typically exponential[END_REF] sqn(G) sqn(A < (G)) 2 sqn(G).

The first inequality is simple, and the second is obtained by using up to sqn(G) increasing matrices to cover the 1-entries above the diagonal, and as many for the 1-entries below the diagonal. Hence the strict queue number of G is within a factor 2 of the strict queue number of its adjacency matrix, assuming an optimal choice of order on V (G).

8.3. Queue number of groups. If one considers the matrix product, with addition interpreted as logical 'or' and multiplication as logical 'and', it is clear that a product of increasing matrices is itself increasing. Furthermore, the adjacency matrix of G (k) is equal to (M +I) k -I where M is the adjacency matrix of G and I is the identity. Matrix product distributes over matrix superposition, thus assuming that sqn(M ) t, we have that (M + I) is superposition of t + 1 increasing matrices, and after distributing (M + I) k is superposition of at most (t+1) k increasing matrices. Thus we obtain a result similar to Lemma 3.10: sqn(G (k) ) is bounded by a function of sqn(G) and k. With a few other arguments, one can reproduce the proof of Lemma 4.1 to prove that regular embeddings preserve finite strict queue number, which is therefore a group invariant. All examples of section 4 can easily be shown to have finite queue number (finitely generated abelian groups, finite Cartesian products of groups with finite queue number, hyperbolic groups).

The characterisation of groups with finite queue number through matrices and the generalisation to infinitely generated groups work without any issue. The uniform queue number of a group G is defined as uqn(G) with M < x the matrix of x acting on (G, <). Groups with uniform queue number 1 are exactly right-orderable groups. As in Lemma 6.2, direct limits preserve uniform queue number. 8.4. Group constructions. Cartesian products-and more generally group extensions-is where the first difference with twin-width appears. Twinwidth on permutation matrices is remarkable in that it is exactly preserved by substitution, in the sense that the twin-width of the resulting matrix is the maximum of the twin-width of the input matrices (see Lemma 3.5). This fails for queue number: if M, N are permutation matrices and M [N ] is obtained by substituting N into every 1-coefficient of M , then [START_REF] Joseph | The pagenumber of k-trees is O(k)[END_REF] sqn(M [N ]) = sqn(M ) sqn(N ).

Thus, while Cartesian products (or group extensions) still preserve having finite uniform queue number, they do not a priori preserve the exact bound. Precisely, the lexicographic ordering used in Lemma 6.5 gives the bound uqn(G × H) uqn(G) uqn(H) by [START_REF] Joseph | The pagenumber of k-trees is O(k)[END_REF], and this bound is tight for this specific choice of order. However, there might be a better choice of order on G × H giving uqn(G × H) = max(uqn(G), uqn(H)) in some cases.

For example, all finitely generated abelian groups have finite uniform queue number, but it is unclear whether there is a universal bound on the latter. In turn, infinitely generated abelian groups (and thus solvable groups) might have infinite uniform queue number.

Figure 3 .

 3 Figure 3. A matrix division inducing a 4-grid.

Theorem 3 . 2 (

 32 Variant of[START_REF] Bonnet | Twinwidth I: tractable FO model checking[END_REF] Theorem 10]). Fix d ∈ N. There exist functions f, g : N → N, with f (n) = 2 O(n) and g(n) ∼ 2n, such that for any binary matrix M with degree at most d, stww(M ) f (gn(M )) , and gn(M ) g (stww(M )) .

  Lemma 3.3 ([3, Proposition 8.1]). For a graph G and k ∈ N, gn(G) k if and only if for all H finite induced subgraph, gn(H) k.

Theorem 3 . 4 (

 34 Variant of[START_REF] Bonnet | Twinwidth I: tractable FO model checking[END_REF] Theorem 14]). Fix d ∈ N. There exist functions f, g : N → N, with f (n) = 2 O(n) and g(n) ∼ 2n, such that for any graph G with degree at most d, stww(G) f (gn(G)) , and gn(G) g (stww(G)) .

3. 2 .

 2 Some stability results.

3. 2 . 1 .

 21 Substitutions in bijection matrices. Let A, B be ordered sets, and (X a ) a∈A , (Y b ) b∈B families of non-empty ordered sets. Define the sums X def = a∈A X a , and Y def = b∈B Y b ,

Figure 4 .

 4 Lemma 3.5. Twin-width is invariant by substitution in bijection matrices stww(M f [a:=ga] a∈A ) = max stww(M f ), max a∈A stww(M ga ) .

Figure 5 .

 5 Figure 5. A graph G with a partition P. In both G(2) /P and (G/P)(2) , parts A and B are adjacent because of the path a 1 , d, b. In (G/P)(2) only, A and C are adjacent thanks to the path a 1 , d, e, c, which can 'jump' from d to e since they are in the same part of P.

Corollary 6 . 3 .

 63 Let G be a group and let H be the collection of finitely generated subgroups of G. Then utww(G) = sup H∈H utww(H).

Corollary 6 . 8 .

 68 If G is a group with H G subgroup of finite index [G : H] = k, then G has finite twin-width if and only if H does, and utww(H) utww(G) max(utww(H), k).

Theorem 7 . 1 (

 71 [START_REF] Osajda | Small cancellation labellings of some infinite graphs and applications[END_REF] Theorem 3.2]). Consider constants A > 0 and D ∈ N, and let (G n ) n∈N be a sequence of connected graphs such that[START_REF] Bilu | Lifts, discrepancy and nearly optimal spectral gap[END_REF]

Figure 7 .

 7 Figure 7. A strict queue; a queue; and a 2-queue-layout of the cube, partitioned in solid and dashed edges.

  and only if the corresponding zone X i × Y j of M is non-zero (i.e. contains at least a '1'). 2.3. Groups. Unless stated otherwise, we consider Cayley graphs, group actions, etc. on the right. If Γ is a group and S ⊂ Γ a finite generating set, its Cayley graph is Cay

  Similarly, M Example of shape of M G a . Here, s i , t i are in T with s1 < G/H t1 , t2 < G/H s2 , and t 1 at -1 2 , s 1 as -1 Furthermore, x 1 < H x 2 and y 1 < H y 2 are in H, and satisfy (x i t 1 )a = y i t 2 , or equivalently x i r = y i with r = t 1 at -1 2 . The general shape of M G a (left matrix) corresponds to M

		Hs 1	Ht 1		x 1 t 1	x 2 t 1
				y 1 t 2	1
	Ht 2		P t 1 ,t 2 a
				y 2 t 2	1
	Hs 2	P s 1 ,s 2 a
	Figure 6. G/H a while the block P t 1 ,t 2	,
			G/H a	is the matrix of a acting on (G/H, < G/H ),
	and for b ∈ H, M H

b is the matrix of b acting on (H, < H ). Fix some a ∈ G. Claim 6.9. Suppose that stww(M

G/H a )

k, and that for any

t 1 , t 2 ∈ T , for r def = t 1 at -1 2 ∈ H, we have stww(M H r ) k. Then stww(M G a ) k.

2 ∈ H. a (right matrix) is equal to M H r .

  t 1 ,t 2 (resp. t 2 ) is an increasing bijection from H to Ht 1 (resp. Ht 2 ), i.e. from the set of column indices (resp. row indices) of M H r to that of P t 1 ,t 2

	Define r Indeed, right product by t 1 Thus P t 1 ,t 2 def = t 1 at -1 2 ∈ H. We claim that P t 1 ,t 2 a	is isomorphic to M H r .

a

) k. a . Furthermore, these bijections transform right product by a into right product by r, in that for all x ∈ H (4)

(xt 1 )a = x(t 1 at -1 2 )t 2 = (xr)t 2 .

a ∼ = M H r , and stww(P t 1 ,t 2 a

  4, the cardinality of C 1 (n) is at most double the previous value, a contradiction of Lemma 7.2. This algorithm chooses G k in expected time polynomial in its size n k . However n k needs to be at least exponential in k, since we want G k to have girth at least linear in k, but at most logarithmic in its size. 7.2.2. Computing the small cancellation labelling. Osajda ([28, Section 2]) equips the sequence (G k ) k∈N with an edge labelling satisfying the small cancellation condition: if p, p ′ are two distinct paths in G k , G k ′ respectively, with the same length and edge labelling, then |p| < λ • girth(G k ), and |p

	Theorem 1.1. There is a finitely generated group with infinite twin-width.
	Proof. By Lemma 7.5 and Theorem 1.2, for any k ∈ N and for any suffi-ciently large n

k , C 2 (n k ) contains graphs of twin-width more than k. Thus, one can construct a sequence (G k ) k∈N of graphs such that tww(G k ) > k and G k ∈ C 2 (n k ), for any sequence (n k ) k∈N of even integers growing sufficiently fast. Since girth(G k ) log(n k )/4, an appropriate choice of n k ensures

  Laboratoire de l'Informatique du Parallélisme, ENS de Lyon, 46 allée d'Italie, 69364 Lyon CEDEX 07, France Email address: edouard.bonnet@ens-lyon.fr Laboratoire de l'Informatique du Parallélisme, ENS de Lyon, 46 allée d'Italie, 69364 Lyon CEDEX 07, France Email address: colin.geniet@ens-lyon.fr Institut de Mathématiques de Jussieu-Paris Rive Gauche, Place Aurélie Nemours, 75013 Paris, France Email address: romain.tessera@imj-prg.fr Laboratoire de l'Informatique du Parallélisme, ENS de Lyon, 46 allée d'Italie, 69364 Lyon CEDEX 07, France Email address: stephan.thomasse@ens-lyon.fr

Logarithms in this section are in base 2.

and fourth authors were partially supported by the ANR grant TWIN-WIDTH (ANR-21-CE48-0014-01).

that girth(G k ) girth(G k-1 ) + 6. Then (G k ) k∈N satisfies the hypotheses of Theorem 7.1, hence there exists a group Γ finitely generated by S such that every G k isometrically embeds in Cay(Γ, S). This group has infinite twinwidth.

7.2. Computability considerations. In this section, we argue that the proof of Theorem 1.1 is effective, and in particular that it can be turned into an algorithm to decide the word problem in the resulting group.

Theorem 7.6. There exists a group with infinite twin-width given by a presentation S; R , with a finite set S of generators and a recursive set R of relators. Furthermore, this group has a decidable word problem.

Using Higman embedding theorem [START_REF] Higman | Subgroups of finitely presented groups[END_REF], we obtain the following.

Corollary 7.7. There is a finitely presented group with infinite twin-width.

Note that this finitely presented group is a supergroup of the one constructed in Theorem 7.6, and might not have a decidable word problem.

To prove Theorem 7.6, we split the proof of Theorem 1.1 in three steps, and prove that each of them is effective.

(1) Constructing the sequence of graphs (G k ) k∈N , with appropriate conditions on degree, girth, diameter, and twin-width (section 7.1). ( 2) Adding labels to this sequence satisfying the small cancellation conditions. This is the core of Osajda's proof, see [START_REF] Osajda | Small cancellation labellings of some infinite graphs and applications[END_REF]Section 2]. (3) Obtaining a group from this small cancellation graph labelling. This construction, attributed to Gromov [START_REF] Gromov | Random walk in random groups[END_REF], is based on the well-known techniques of small cancellation theory (see e.g. [22, Chapter V]).

7.2.1.

Computing the sequence of graphs.

Lemma 7.8. There exists a computable sequence of graphs (G k ) k∈N , satisfying the hypotheses of Theorem 7.1, and with unbounded twin-width.

Proof. By Lemma 7.5 and Theorem 1.2, one can find such a sequence by choosing a G k ∈ C 2 (n k ) appropriately, for some n k function of k. It is easy to obtain an explicit formula for n k from the proofs of Lemmas 7.3 to 7.5. This yields a naive algorithm: Enumerate all graphs of size n k until finding one in C 2 (n k ) with sufficiently large twin-width. However, the proofs give a natural and much more efficient randomized algorithm. One chooses a graph uniformly at random in C 1 (n k ). Edge editions are performed according to Lemma 7.4, and the process is aborted should it require more than 4 • 6 g edge deletions-which by Lemma 7.3 happens with probability less than 1/2. In case of success, the resulting graph G k is in C 2 (n k ). Although the distribution of G k over C 2 (n k ) is not uniform, the proof of Lemma 7.5 can be adapted to show that for any constant c and any subset X ⊂ C 2 (n k ) of size |X| n! • c n , the probability that G k is in X tends to 0 as n k grows. Applying this to the subset X of graphs with twin-width at most t for any fixed t, we obtain by Theorem 1.2 that the sequence (G k ) k∈N has unbounded twin-width with probability 1. Thus, this probabilistic algorithm does not even need to compute the twin-width of any graph.

Summarizing, proofs of finite twin-width from this paper also give finite queue number in the following cases.

(1) Hyperbolic groups have finite queue number.

(2) Right-orderable groups have uniform queue number 1, and this is a characterisation. (3) Finitely generated abelian groups have finite uniform queue number, but a priori without a universal bound. (4) Polycyclic groups, which are defined like solvable groups except requiring that the iterated quotients be finitely generated and abelian, have finite uniform queue number. (5) Groups of polynomial growth have finite uniform queue number, since they are virtually nilpotent, and nilpotent groups are polycyclic.

On the other hand, we conjecture that arbitrary abelian groups, and a fortiori solvable groups, can have infinite queue number (uniform and non-uniform).

As a simple example, we do not know whether an infinite countable product of Z/2Z with itself has finite queue number. We also conjecture that the group of tree automorphisms considered in Proposition 6.18 has infinite queue number. This group is related to the Bilu-Linial expanders [START_REF] Bilu | Lifts, discrepancy and nearly optimal spectral gap[END_REF], which are known to have twin-width at most 6 [3, Section 5], and are conjectured to have unbounded queue number.

Indeed, these expanders can be described as follows. Let G n be the group of permutations on 2 n elements obtained by restricting automorphisms of the infinite binary tree T to nodes at depth n in T , ordered left to right. Equivalently, permutations in G n are the ones obtained from a permutation σ ∈ G n-1 by substituting each '1'-coefficient of σ by either the diagonal or antidiagonal 2-by-2 matrix, the choice being done independently for all '1'-coefficients. Then Bilu-Linial expanders have a partition of vertices into V 1 , V 2 , V 3 , V 4 of size 2 n each, and a choice of orders < i on V i such that the adjacency matrix of (V i , < i ) versus (V j , < j ) is the matrix of a permutation in G n . Precisely, a random choice of permutations in G n in this description yields an expander with high probability, while Bilu and Linial give a derandomized construction.

From this description, it is simple to see that if the action of Aut(T ) on T has finite uniform queue number, then Bilu-Linial expanders have bounded queue number. The converse, and the relation with the queue number of Aut(T ) are not clear, but it is likely that an answer to either question would give significant insight for the other.