# Twin-width VII: Groups

Édouard Bonnet  ,  Colin Geniet  ,  Romain Tessera  and  Stéphan Thomassé
Laboratoire de l’Informatique du Parallélisme, ENS de Lyon, 46 allée d’Italie,
69364 Lyon CEDEX 07, France<EMAIL_ADDRESS>Laboratoire de
l’Informatique du Parallélisme, ENS de Lyon, 46 allée d’Italie, 69364 Lyon
CEDEX 07, France<EMAIL_ADDRESS>Institut de Mathématiques de
Jussieu-Paris Rive Gauche, Place Aurélie Nemours, 75013 Paris, France
<EMAIL_ADDRESS>Laboratoire de l’Informatique du Parallélisme, ENS
de Lyon, 46 allée d’Italie, 69364 Lyon CEDEX 07, France  stephan.thomasse@ens-
lyon.fr

###### Abstract.

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 quasi-isometry. 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)}\cdot n!$ graphs on vertex set
$\\{1,\dots,n\\}$, settling a question asked in a previous work.

###### Key words and phrases:

Twin-width, Cayley graphs, coarse embeddings, excluded permutations, small
classes, small cancellation

###### 2020 Mathematics Subject Classification:

Primary 05C25; Secondary 20F65, 05C30

The first, second, and fourth authors were partially supported by the ANR
grant TWIN-WIDTH (ANR-21-CE48-0014-01)

##  1\. Introduction

Twin-width is an invariant of graphs and matrices introduced in [6], with
applications in algorithmics, logic, enumerative combinatorics [3, 4, 5].
Finite twin-width is known to be a group invariant of Cayley graphs [3,
Section 7]. Our main result is the construction of groups with infinite twin-
width, using an embedding theorem of Osajda [28]. theoreminfinitetww There is
a finitely generated group with infinite twin-width. This disproves the ‘small
conjecture’ proposed in [3], related to the Stanley-Wilf conjecture proved by
Marcus and Tardos [24], 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 twin-width
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\times n$ 0–1 matrix with more than
$c_{k}n$ 1-entries contains all $k\times k$ permutation matrices as
submatrices, for an appropriate $c_{k}$ function of $k$ only [24]. A major
corollary is the Stanley-Wilf conjecture: For any fixed permutation $\sigma$,
the class of permutations avoiding $\sigma$ as pattern has single-exponential
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 [19]:
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 $\mathcal{C}$ closed under
taking submatrices has growth at most single-exponential or at least
factorial. This was established in [5], 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 [6]. 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!\cdot c^{n}$ graphs on vertices $1,\dots,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 [26]. These
examples are generalised by the following.

######  Theorem 1.1 ([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.2 (Small conjecture [3]).

A class of graphs closed under induced subgraphs is small if and only if it
has bounded twin-width.

We disprove 1.2 using an approach suggested in [3]: if $G$ is a Cayley graph
of some group $\Gamma$, then the class of finite subgraphs of $G$ is small [3,
Lemma 8.1]. If $\Gamma$ is a group with infinite twin-width, then this class
furthermore has unbounded twin-width, hence is a counterexample to 1.2. Thus
section 1 gives:

######  Corollary 1.3.

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 [3, Lemma 8.2], which proved that
finite twin-width is a group invariant of Cayley graphs: given a group
$\Gamma$, all Cayley graphs of $\Gamma$ 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 [7].

Groups with finite twin-width have a remarkable second characterisation: a
group $\Gamma$ has finite twin-width if and only if there is a total order $<$
on $\Gamma$ such that for any $x\in\Gamma$, the action of $x$ on $(\Gamma,<)$
by product is a permutation with finite _width_ (in the sense of Guillemot and
Marx [19]), or equivalently a permutation which avoids some pattern. For
example, if $<$ is a right-invariant order on $\Gamma$, 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 $\Gamma$, 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.4 (Lemmas 6.5, 6.14, 6.2, 6.15 and 6.13 in the text).

The following constructions preserve finiteness of uniform twin-width:

  1. (1)

Group extensions (and thus Cartesian or semidirect products);

  2. (2)

Infinite direct products and direct sums;

  3. (3)

Direct limits;

  4. (4)

Taking supergroups with finite index;

  5. (5)

Quotienting by finite subgroups;

  6. (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 twin-width,
i.e. there are groups with finite twin-width and infinite uniform twin-width.
A candidate is the group of finitely supported permutations on $\mathbb{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.1—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 [1] 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 $\Gamma$ is a group with infinite twin-width, the class of subgraphs of
some Cayley graph of $\Gamma$ has bounded degree and unbounded twin-width,
which could solve the aforementioned problem. Unfortunately, the group
constructed in section 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 [21]. 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 [10], 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 [14, 11], 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 [12]. This is the first known explicit construction of
bounded degree graphs with unbounded stack number (probabilistic constructions
were previously known [23]). 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 $\mathbb{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 section 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.4 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 [6], 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) twin-
width 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 twin-width.
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.

##  2\. 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)\subset V(G)$ and
$E(H)\subset E(G)$. It is an _induced subgraph_ if $V(H)\subset 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\in V(G)$, its degree $d(v)$ is the number of edges incident to $v$. We
denote by $\Delta(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 $\textsf{diam}(G)$, is the
maximum distance between two vertices of $G$. The _girth_ of a graph $G$,
denoted $\textsf{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\times Y$ binary matrix
is a map $M:X\times Y\to\\{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^{\prime}\times
Y^{\prime}$ for some $X^{\prime}\subset X,Y^{\prime}\subset 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\to 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,<)\times(V,<)$ matrix such that $A_{<}(G)(x,y)=1$ if and
only if $x,y$ are adjacent in $G$.

####  2.2.1. Divisions of matrices

If $M$ is an $X\times Y$ matrix, a $k\times l$_-division_ of $M$ consists of
partitions of rows and columns into intervals; i.e. it is given by
$\mathcal{X}=\\{X_{1},\dots,X_{k}\\}$ partition of $X$,
$\mathcal{Y}=\\{Y_{1},\dots,Y_{l}\\}$ partition of $Y$, such that every
$X_{i}$ or $Y_{j}$ is an interval, and with $X_{1}<_{X}\dots<_{X}X_{k}$ and
$Y_{1}<_{Y}\dots<_{Y}Y_{l}$. The _zone_ $(i,j)$ of the division
$(\mathcal{X},\mathcal{Y})$ is the submatrix $M$ restricted to $X_{i}\times
Y_{j}$. The _quotient_ matrix $M/(\mathcal{X},\mathcal{Y})$ is the
$\mathcal{X}\times\mathcal{Y}$ matrix with a ‘1’ at position $X_{i},Y_{j}$ if
and only if the corresponding zone $X_{i}\times 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 $\Gamma$ is a group and $S\subset\Gamma$ a finite generating set,
its Cayley graph is

$\text{Cay}(\Gamma,S)\stackrel{{\scriptstyle\text{def}}}{{=}}\left(\Gamma,\textstyle\left\\{xy\
|\ x^{-1}y\in S\cup S^{-1}\right\\}\right).$

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\uplus S^{-1}$, where $S^{-1}$ denotes
formal inverses of elements of $S$. The group associated to this presentation,
denoted $\left\langle S;R\right\rangle$, is the free group over $S$ quotiented
by the normal subgroup generated by $R$. A group $G$ is said to admit
$\left\langle S;R\right\rangle$ as presentation if it is isomorphic to
$\left\langle S;R\right\rangle$. A group is finitely presented if it admits a
presentation with finite sets of generators and of relators.

For a group $\Gamma$ finitely generated by $S$, the word problem is the
following decision problem: given $w$ a word over $S\cup S^{-1}$, is $w$
interpreted as an element of $\Gamma$ 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$.

###  2.4. 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
$\lambda\geqslant 0$, a map $f:X\to Y$ between metric spaces is a  _$\lambda$
-quasi-isometric embedding_ if for all $x,x^{\prime}\in X$,

$\lambda^{-1}d_{X}(x,x^{\prime})-\lambda\leqslant
d_{Y}\left(f(x),f(x^{\prime})\right)\leqslant\lambda
d_{X}(x,x^{\prime})+\lambda$

Thus quasi-isometric embeddings are maps which preserve distances up to affine
lower and upper bound. The map $f$ is a _$\lambda$ -quasi-isometry_ if it is
also $\lambda$-cobounded, i.e. every $y\in Y$ is at distance at most $\lambda$
of $f(X)$. The spaces $X$ and $Y$ are said to be quasi-isometric if there is a
$\lambda$-quasi-isometry $X\to Y$ for some $\lambda$. 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 $\Gamma$ and $S,S^{\prime}$ two finite generating sets of
$\Gamma$, it is easy to verify that $\text{Cay}(\Gamma,S)$ and
$\text{Cay}(\Gamma,S^{\prime})$ 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\to Y$
is a $\lambda$-regular embedding if it is $\lambda$-Lipschitz and for all
$y\in Y$, $|{f^{-1}(y)}|\leqslant\lambda$. If all balls of $X$ have
cardinality bounded by a function of their radius, then any quasi-isometric
embedding $X\to 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\in I}$ be a family of substructures of $S$. The family
$(S_{i})_{i\in I}$ is _directed_ if for all $i,j\in I$, there exists $k\in I$
with $S_{i}\cup S_{j}\subseteq S_{k}$. The structure $S$ is said to be direct
limit of $(S_{i})_{i\in I}$ if $(S_{i})_{i\in I}$ is directed and
$S=\bigcup_{i\in 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 $\mathbb{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\in I}$, and for each $i\in I$ let
$<_{i}$ be a total order on $S_{i}$. Then there exists a total order $<$ on
$S$ such that for any finite $X\subset S$, there is some $i\in I$ with
$X\subseteq S_{i}$ and such that $<$ and $<_{i}$ coincide on $X$.

###### Proof.

Order $I$ by $i\leqslant j$ if $S_{i}\subseteq S_{j}$. For $i\in I$, define
its upward closure $\uparrow\\!i=\textstyle\left\\{j\ |\ j\geqslant
i\right\\}$. Consider the family of non-empty and eventually upward-closed
subsets

$\mathcal{F}\stackrel{{\scriptstyle\text{def}}}{{=}}\textstyle\left\\{J\subseteq
I\ |\ \exists i\in I,~{}\uparrow\\!i\subseteq J\right\\}.$

If $A\in\mathcal{F}$ and $A\subset B$, then clearly $B\in\mathcal{F}$.
Furthermore, given $A_{1},A_{2}\in\mathcal{F}$, consider $i_{1},i_{2}$ such
that $\uparrow\\!i_{j}\subseteq A_{j}$. Since $(S_{i})_{i\in I}$ is directed,
there exists $k\in I$ such that $i_{1},i_{2}\leqslant k$. Then
$\uparrow\\!k\subseteq A_{1}\cap A_{2}$, and thus $A_{1}\cap
A_{2}\in\mathcal{F}$. This proves that $\mathcal{F}$ is a proper filter, hence
there is an ultrafilter $\mathcal{U}$ containing $\mathcal{F}$.

For $x\neq y\in S$, consider the indices which order $x$ before $y$.

$I_{xy}\stackrel{{\scriptstyle\text{def}}}{{=}}\textstyle\left\\{i\in I\ |\
x<_{i}y\right\\}$

The limit order on $S$ in then defined as $x<y$ if and only if
$I_{xy}\in\mathcal{U}$. Since $S$ is direct limit of $(S_{i})_{i\in I}$, for
any $x,y\in S$, there is some $i\in I$ such that $x,y\in S_{i}$. Assuming
$x\neq y$, it is clear that $\uparrow\\!i\subseteq I_{xy}\cup I_{yx}$: for any
$j\geqslant i$, $x$ and $y$ must be comparable by $<_{j}$. Since $\mathcal{U}$
is an ultrafilter, it follows that either $I_{xy}\in\mathcal{U}$ or
$I_{yx}\in\mathcal{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\subseteq S$ any finite subset, there is some $i\in I$ with
$X\subseteq S_{i}$. Define

$A\stackrel{{\scriptstyle\text{def}}}{{=}}(\uparrow\\!i)\cap\bigcap_{\begin{subarray}{c}x,y\in
X\\\ x<y\end{subarray}}I_{xy}$

Then $A$ is a finite intersection of elements of $\mathcal{U}$, hence
$A\in\mathcal{U}$ and in particular it is non-empty. Choose $j\in A$. Then
$j\geqslant i$, hence $X\subseteq S_{j}$. Furthermore for any $x<y$ in $X$, we
have $j\in 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. ∎

##  3\. Twin-Width of graphs and matrices

This section recalls the definition of twin-width [6], 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 [19]. The reader may refer to [6] for the general
definition. See also [3, Section 7] for a discussion on twin-width for sparse
graphs beyond bounded degree.

###  3.1. Definitions and characterisations

####  3.1.1. Twin-width of graphs

Let $G=(V,E)$ be a finite graph and $\mathcal{P}$ be a partition of $V(G)$.
The _quotient graph_ $G/\mathcal{P}$ has vertex set $\mathcal{P}$, and its
edges are all $XY$ with $X,Y\in\mathcal{P}$ such that there exists an edge
$xy$ of $G$ with $x\in X$ and $y\in Y$. A _partition sequence_ is a sequence
$\mathcal{P}_{n},\dots,\mathcal{P}_{1}$ of partitions of $V(G)$ such that
$\mathcal{P}_{n}=\textstyle\left\\{\\{v\\}\ |\ v\in V\right\\}$ is the
partition into singletons, $\mathcal{P}_{1}=\\{V\\}$ is the trivial partition,
and each $\mathcal{P}_{i-1}$ is obtained by merging two parts of
$\mathcal{P}_{i}$. The _width_ of this partition sequence is the maximum
degree of the quotient graphs, i.e. $\max_{i=1}^{n}\Delta(G/\mathcal{P}_{i})$.
The _strict twin-width_ of $G$, denoted $\operatorname{stww}(G)$, is the
minimum width of a partition sequence starting with $G$.

For a partition sequence $\mathcal{P}_{n},\dots,\mathcal{P}_{1}$, one may also
see the quotients graphs $G/\mathcal{P}_{n},\dots,G/\mathcal{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.

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.

Remark that $\operatorname{stww}(G)$ is at least $\Delta(G)$. Strict twin-
width is also non-increasing when taking subgraphs.111Non-strict twin-width is
only stable under taking _induced_ subgraphs, and has no relation to
$\Delta(G)$.  Strict twin-width has the following relation to the general
notion of twin-width, denoted $\operatorname{tww}(G)$, as defined in [6].

(1)
$\max\left(\Delta(G),\operatorname{tww}(G)\right)\leqslant\operatorname{stww}(G)\leqslant\Delta(G)+\operatorname{tww}(G)$

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.

$\operatorname{stww}(G)\stackrel{{\scriptstyle\text{def}}}{{=}}\sup\textstyle\left\\{\operatorname{stww}(H)\
|\ \text{$H$ finite induced subgraph of $G$}\right\\}.$

The graph $G$ has _finite strict twin-width_ if
$\operatorname{stww}(G)<\infty$.

####  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
$(\mathcal{X}_{n},\mathcal{Y}_{n}),\dots,(\mathcal{X}_{1},\mathcal{Y}_{1})$ of
divisions of $M$ such that $(\mathcal{X}_{n},\mathcal{Y}_{n})$ is the division
into singletons, $(\mathcal{X}_{1},\mathcal{Y}_{1})=(\\{X\\},\\{Y\\})$ is the
trivial division, and $(\mathcal{X}_{i-1},\mathcal{Y}_{i-1})$ is obtained from
$(\mathcal{X}_{i},\mathcal{Y}_{i})$ by merging two parts either in
$\mathcal{X}_{i}$ or in $\mathcal{Y}_{i}$. The _width_ of this division
sequence is the maximum degree of any column or row in any quotient matrix
$M/(\mathcal{X}_{i},\mathcal{Y}_{i})$, see Figure 2. The strict twin-width of
$M$, denoted by $\operatorname{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.

1111111111111111111 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.

####  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\times 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
$\operatorname{gn}(M)$, is the supremum of sizes of grids in $M$.

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

######  Remark 3.1.

Let $M$ be an $X\times Y$ matrix. Then $M$ contains a $k$-grid if and only if
there exist $x_{i,j}\in X$, $y_{i,j}\in Y$ for $1\leqslant i,j\leqslant k$
such that

  1. (1)

For all indices $i,j$, $M(x_{i,j},y_{i,j})=1$

  2. (2)

For all indices $i,i^{\prime},j,j^{\prime}$, if $i<i^{\prime}$ then
$x_{i,j}<_{X}x_{i^{\prime},j^{\prime}}$, and if $j<j^{\prime}$ then
$y_{i,j}<_{Y}y_{i^{\prime},j^{\prime}}$.

Thus, $M$ has a $k$-grid if and only if it has a $k^{2}\times 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.

######  Theorem 3.2 (Variant of [6, Theorem 10]).

Fix $d\in\mathbb{N}$. There exist functions $f,g:\mathbb{N}\to\mathbb{N}$,
with $f(n)=2^{O(n)}$ and $g(n)\sim 2n$, such that for any binary matrix $M$
with degree at most $d$,

$\displaystyle\operatorname{stww}(M)$ $\displaystyle\leqslant
f\left(\operatorname{gn}(M)\right),~{}\text{and}$
$\displaystyle\operatorname{gn}(M)$ $\displaystyle\leqslant
g\left(\operatorname{stww}(M)\right).$

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.222 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 [13, 9] of Marcus Tardos
Theorem [24], at the core of this proof.  It is also a simplified version of
[6, Theorem 10].333 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.

For infinite matrices, the theorem should of course be understood as stating
‘$\operatorname{stww}(M)$ is finite if and only if $\operatorname{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 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 $\operatorname{gn}(G)$, is the minimum of
$\operatorname{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.

######  Lemma 3.3 ([3, Proposition 8.1]).

For a graph $G$ and $k\in\mathbb{N}$, $\operatorname{gn}(G)\leqslant k$ if and
only if for all $H$ finite induced subgraph, $\operatorname{gn}(H)\leqslant
k$.

###### 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\subset 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.

######  Theorem 3.4 (Variant of [6, Theorem 14]).

Fix $d\in\mathbb{N}$. There exist functions $f,g:\mathbb{N}\to\mathbb{N}$,
with $f(n)=2^{O(n)}$ and $g(n)\sim 2n$, such that for any graph $G$ with
degree at most $d$,

$\displaystyle\operatorname{stww}(G)\leqslant
f\left(\operatorname{gn}(G)\right),~{}\text{and}$
$\displaystyle\operatorname{gn}(G)\leqslant
g\left(\operatorname{stww}(G)\right).$

###### 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 [6, Theorem 14]). Lemma 3.3 is used to prove the
infinite case. ∎

###  3.2. Some stability results

####  3.2.1. Substitutions in bijection matrices

Let $A,B$ be ordered sets, and $(X_{a})_{a\in A}$, $(Y_{b})_{b\in B}$ families
of non-empty ordered sets. Define the sums

$X\stackrel{{\scriptstyle\text{def}}}{{=}}\biguplus_{a\in
A}X_{a},~{}\text{and}~{}Y\stackrel{{\scriptstyle\text{def}}}{{=}}\biguplus_{b\in
B}Y_{b},$

ordered in the natural way, i.e. $a<a^{\prime}$ in $A$ implies
$X_{a}<X_{a^{\prime}}$ in $X$, while the order inside each $X_{a}$ is
preserved, and similarly for $Y$.

Let $f:A\to B$ be a bijection, and for each $a\in A$ let $g_{a}:X_{a}\to
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\in A}:X\to Y$ obtained by combining the
$g_{a}$ along $f$, i.e.

$\text{for $x\in A$, $y\in X_{x}$}\quad f[a:=g_{a}]_{a\in
A}(x,y)\stackrel{{\scriptstyle\text{def}}}{{=}}(f(x),g_{x}(y)).$

In terms of matrices, we also write $M_{f}[(a,f(a)):=M_{g_{a}}]$ for
$M_{f[a:=g_{a}]}$, and call it the substitution of $(a,f(a))$ by $M_{g_{a}}$
in $M_{f}$.

A common special case of the above is when the maps $g_{a}$ are all isomorphic
to some $g:C\to D$. Then $X=A\times C$, $Y=B\times D$ are ordered
lexicographically, and $f[a:=g]_{a\in A}$ is the product map $(f,g)$, while
$M_{(f,g)}=M_{f}\otimes M_{g}$ is a tensor product, see Figure 4.

1111$\otimes$11$=$11111111 Figure 4. The tensor product corresponds to
substituting each 1-coefficient of the left matrix by the right matrix.

######  Lemma 3.5.

Twin-width is invariant by substitution in bijection matrices

$\operatorname{stww}(M_{f[a:=g_{a}]_{a\in
A}})=\max\left(\operatorname{stww}(M_{f}),\max_{a\in
A}\operatorname{stww}(M_{g_{a}})\right).$

###### Proof.

In the finite case, this is [19, Proposition 3.4]: in $M_{f[a:=g_{a}]}$, one
begins by regrouping each block $M_{g_{a}}$ in a single part using a division
sequence for $M_{g_{a}}$. After this, the remaining quotient matrix is exactly
$M_{f}$.

The infinite case reduces to the finite one by remarking that any finite
submatrix of $M_{f[a:=g_{a}]}$ is obtained by substituting finite submatrices
of some $M_{g_{a}}$ 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\in I$
consider $(X_{i},<_{X_{i}})$, $(Y_{i},<_{Y_{i}})$ two totally ordered sets,
and $f_{i}:X_{i}\to Y_{i}$ a bijection. Consider the products
$X\stackrel{{\scriptstyle\text{def}}}{{=}}\prod_{i\in I}X_{i}$,
$Y\stackrel{{\scriptstyle\text{def}}}{{=}}\prod_{i\in I}Y_{i}$. They are
totally ordered by lexicographic order, i.e. for $x\neq x^{\prime}$

$x<_{X}x^{\prime}\quad\iff\quad x_{i}<_{X_{i}}x^{\prime}_{i}\qquad\text{where
}i\stackrel{{\scriptstyle\text{def}}}{{=}}\min_{j\in I}x_{j}\neq
x^{\prime}_{j}.$

Let $f:X\to Y$ be the product of all $f_{i}$. Then

$\operatorname{stww}(M_{f})=\sup_{i\in I}\operatorname{stww}(M_{f_{i}}).$

###### Proof.

Let $M^{\prime}$ be a finite submatrix of $M_{f}$ on rows $X^{\prime}$ and
columns $Y^{\prime}$. It suffices to bound $\operatorname{stww}(M^{\prime})$
by the right-hand side of the lemma. For each pair of distinct elements of
$X^{\prime}$ or $Y^{\prime}$, 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}=\prod_{j\in J}X_{j}$ and $Y_{J}=\prod_{j\in J}Y_{j}$, equipped
with the projections $\pi_{X}:X\to X_{J}$ and $\pi_{Y}:Y\to Y_{J}$. Consider
the bijection $f_{J}:X_{J}\to Y_{J}$ obtained by product of $(f_{j})_{j\in
J}$. By construction, $\pi_{X}$ is injective from $X^{\prime}$ to $X_{J}$, and
similarly for $\pi_{Y}$. Furthermore, it is clear that if $y=f(x)$, then
$\pi_{Y}(y)=f_{J}(\pi_{X}(x))$. Finally, if $X_{J}$ and $Y_{J}$ are again
ordered lexicographically, $\pi_{X}$ and $\pi_{Y}$ are non-decreasing. From
this it follows that
$\operatorname{stww}(M^{\prime})\leqslant\operatorname{stww}(M_{f_{J}})$, and
since $M_{f_{J}}$ is a finite tensor product of $(M_{f_{j}})_{j\in J}$, we
have $\operatorname{stww}(M_{f_{J}})\leqslant\sup_{i\in
I}\operatorname{stww}(M_{f_{i}})$ as desired. ∎

####  3.2.2. Superposition

Given $M,N$ two $X\times Y$ matrices, define their superposition $M\lor N$ as
the $X\times Y$ matrix with

$(M\lor
N)(x,y)\stackrel{{\scriptstyle\text{def}}}{{=}}\max\left(M(x,y),N(x,y)\right).$

A variant of the next lemma was recently observed [2, Lemma 18].

######  Lemma 3.7.

If $M_{1},\dots,M_{r}$ are $X\times Y$ matrices with
$\operatorname{gn}(M_{i})<k$, then

$\operatorname{gn}\left(\textstyle{\bigvee_{i=1}^{r}M_{i}}\right)<r^{rk}.$

###### Proof.

A classical Ramsey theory argument gives the following.

######  Claim 3.8.

For any $k\in\mathbb{N}$, fix $\ell=r^{rk}$. Then for any $\ell\times\ell$
matrix $M$ whose coefficients are colors in $\\{1,\dots,r\\}$, there exists a
$k\times k$ submatrix of $M$ consisting of only one color.

Now assume that $\bigvee_{i=1}^{r}M_{i}$ contains a $\ell$-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\times k$ submatrix with a single color $i$,
which induces a $k$-grid in $M_{i}$. ∎

####  3.2.3. Bounded quotients

######  Lemma 3.9.

Let $G$ be a graph and $\mathcal{P}$ a partition of $V(G)$ such that every
part $P\in\mathcal{P}$ has size $|{P}|\leqslant k$. Then

$\operatorname{stww}(G)\leqslant k\operatorname{stww}(G/\mathcal{P}).$

###### Proof.

Given a partition sequence for $G/\mathcal{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 $\mathcal{P}$ in an arbitrary manner. During this
process, the quotient graphs are of the form $G/\mathcal{P}^{\prime}$, where
every part of $\mathcal{P}^{\prime}$ is contained in some part of
$\mathcal{P}$. Since every $P\in\mathcal{P}$ has size at most $k$, it contains
at most $k$ distinct parts of $\mathcal{P}^{\prime}$, which clearly implies
that $\Delta(G/\mathcal{P}^{\prime})\leqslant k\Delta(G/\mathcal{P})$. It
follows that

$\operatorname{stww}(G)\leqslant\max\left(\operatorname{stww}(G/\mathcal{P}),k\Delta(G/\mathcal{P})\right).$

and the right-hand side is bounded by $k\operatorname{stww}(G/\mathcal{P})$. ∎

####  3.2.4. First-order interpretations

If $\mathcal{C}$ is a class of finite graphs of bounded twin-width, then any
first-order transduction of $\mathcal{C}$ also has bounded twin-width [6,
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\neq y$ are adjacent in
$G^{(k)}$ if and only if $d_{G}(x,y)\leqslant k$. Remark that

(2) $\Delta(G^{(k)})\leqslant(\Delta(G))^{k}.$

######  Lemma 3.10.

For any $k\in\mathbb{N}$, and any graph $G$,

$\operatorname{stww}(G^{(k)})\leqslant\operatorname{stww}(G)^{k}.$

###### Proof.

We prove the finite case. If $\mathcal{P}$ is a partition of $V(G)$, one
verifies that

(3) $G^{(k)}/\mathcal{P}\quad\text{is a subgraph
of}\quad(G/\mathcal{P})^{(k)}.$

Indeed, for $X,Y\in\mathcal{P}$, there is an edge $XY$ in
$G^{(k)}/\mathcal{P}$ if and only if there are $x\in X$, $y\in 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/\mathcal{P}$, see Figure 5.

$a_{1}$$a_{2}$$d$$e$$B$$b$$C$$c$$A$ Figure 5. A graph $G$ with a partition
$\mathcal{P}$. In both $G^{(2)}/\mathcal{P}$ and $(G/\mathcal{P})^{(2)}$,
parts $A$ and $B$ are adjacent because of the path $a_{1},d,b$. In
$(G/\mathcal{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 $\mathcal{P}$.

Now if $\mathcal{P}_{n},\dots,\mathcal{P}_{1}$ is a partition sequence of
width $t$ for $G$, then $(G/\mathcal{P}_{i})^{(k)}$ has degree bounded by
$t^{k}$ by Eq. 2, hence so does $G^{(k)}/\mathcal{P}_{i}$. Thus
$\mathcal{P}_{n},\dots,\mathcal{P}_{1}$ is also a partition sequence of width
at most $t^{k}$ for $G^{(k)}$. ∎

######  Lemma 3.11.

If $\sigma:X\to Y$, $\tau:Y\to Z$ are bijections between totally ordered sets
with $\operatorname{stww}(M_{\sigma}),\operatorname{stww}(M_{\tau})\leqslant
t$, then

$\operatorname{stww}(M_{\tau\circ\sigma})=2^{O(t)}.$

###### Proof.

By Theorem 3.2, assume that
$\operatorname{gn}(M_{\sigma}),\operatorname{gn}(M_{\tau})\leqslant
t^{\prime}$ with $t^{\prime}=O(t)$. We order $X\uplus Z$ with $X<Z$, and
consider the $(X\uplus Z)\times Y$ matrix $M$ consisting of $M_{\sigma}$ and
$M_{\tau^{-1}}$ put side by side (remark that $M_{\tau^{-1}}$ is the transpose
of $M_{\tau}$). Clearly, $\operatorname{gn}(M)\leqslant 2t^{\prime}+1$, hence
by Theorem 3.2, there is a division sequence
$(\mathcal{R}_{n},\mathcal{C}_{n}),\dots,(\mathcal{R}_{1},\mathcal{C}_{1})$ of
$M$ of width $2^{O(t)}$.

Let us construct a division sequence
$(\mathcal{X}_{n},\mathcal{Z}_{n}),\dots,(\mathcal{X}_{1},\mathcal{Z}_{1})$
for $M_{\tau\circ\sigma}$. The partition $\mathcal{X}_{i}$ of $X$ into
intervals is obtained by restricting $\mathcal{R}_{i}$ to $X$, i.e.

$\mathcal{X}_{i}\stackrel{{\scriptstyle\text{def}}}{{=}}\textstyle\left\\{R\cap
X\ |\ R\in\mathcal{R}_{i}\land R\cap X\neq\emptyset\right\\}.$

The partition $\mathcal{Z}_{i}$ of $Z$ is defined similarly. It is easy to
verify that for any $i$, either
$(\mathcal{X}_{i},\mathcal{Z}_{i})=(\mathcal{X}_{i+1},\mathcal{Z}_{i+1})$, or
$(\mathcal{X}_{i},\mathcal{Z}_{i})$ is obtained by merging two parts in either
$\mathcal{X}_{i+1}$ or $\mathcal{Z}_{i+1}$. Hence, up to some trivial cleanup,
this is a division sequence for $M_{\tau\circ\sigma}$.

We need to bound the degree of the quotient matrices
$M_{\tau\circ\sigma}/(\mathcal{X}_{i},\mathcal{Z}_{i})$. Let
$X^{\prime}\in\mathcal{X}_{i}$ be a part, obtained as $X^{\prime}=X\cap R$ for
some $R\in\mathcal{R}_{i}$. Say that $Y^{\prime}\in\mathcal{C}_{i}$ is a
neighbour of $X^{\prime}$ if there exists $x\in X^{\prime}$ with $f(x)\in
Y^{\prime}$. The number of neighbours of $X^{\prime}$ in $\mathcal{C}_{i}$ is
bounded by the degree of $R$ in $M/(\mathcal{R}_{i},\mathcal{C}_{i})$.
Similarly, for $Y^{\prime}\in\mathcal{C}_{i}$, say that
$Z^{\prime}\in\mathcal{Z}_{i}$ is a neighbour of $Y^{\prime}$ if there exists
$y\in Y^{\prime}$ with $g(y)\in Z^{\prime}$. Again, the number of neighbours
of $Y^{\prime}$ in $\mathcal{Z}_{i}$ is bounded by the degree of $Y^{\prime}$
in $M/(\mathcal{R}_{i},\mathcal{C}_{i})$. Now, if
$Z^{\prime}\in\mathcal{Z}_{i}$ is such that there exists $x\in X^{\prime}$
with $g(f(x))\in Z^{\prime}$, then $Z^{\prime}$ is a neighbour in
$\mathcal{Z}_{i}$ of a neighbour in $\mathcal{C}_{i}$ of $X^{\prime}$. It
follows that the degree of $X^{\prime}$ in
$M_{\tau\circ\sigma}/(\mathcal{X}_{i},\mathcal{Z}_{i})$ is bounded by the
square of the maximum degree in $M/(\mathcal{R}_{i},\mathcal{C}_{i})$, which
is still $2^{O(t)}$. The same holds for the degree of a part
$Z^{\prime}\in\mathcal{Z}_{i}$.

Thus we have constructed a division sequence for $M_{\tau\circ\sigma}$ 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.

##  4\. 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\to G$ is a $\lambda$-regular embedding, then

$\operatorname{stww}(H)\leqslant\lambda\operatorname{stww}(G)^{\lambda}.$

###### Proof.

Let $\mathcal{P}=\textstyle\left\\{f^{-1}(v)\ |\ v\in V(G)\right\\}$ be the
preimage partition of $V(H)$. Since $f$ is $\lambda$-regular, parts of
$\mathcal{P}$ have size at most $\lambda$. One can see $f$ as a map
$f:H/\mathcal{P}\to G$, which is injective and $\lambda$-Lipschitz. This
implies that $H/\mathcal{P}$ is isomorphic to a subgraph of $G^{(\lambda)}$.
Then, by Lemmas 3.9 and 3.10,

$\operatorname{stww}(H)\leqslant\lambda\operatorname{stww}(H/\mathcal{P})\leqslant\lambda\operatorname{stww}(G)^{\lambda}.$

∎

Since quasi-isometries between graphs of bounded degree are regular
embeddings, it follows that having finite twin-width is invariant under quasi-
isometry for graphs of bounded degree. In particular, whether or not a Cayley
graph $\text{Cay}(\Gamma,S)$ has finite twin-width depends only on the group
$\Gamma$, 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. (1)

Finite groups trivially have finite twin-width.

  2. (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. (3)

A cartesian product of groups corresponds to the cartesian product of Cayley
graphs, which is known to preserve finite strict twin-width (see [3, Theorem
7.2]).

  4. (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 [17] 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 [7]. Since trees of bounded degree have
finite twin-width, and Cartesian products preserve it, we obtain the
following.

######  Proposition 4.2.

Gromov-hyperbolic groups and graphs of bounded degree have finite twin-width.

##  5\. 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 $\Gamma$ be a group acting on $X$ by
$\phi:\Gamma\to\operatorname{\mathfrak{S}}_{X}$, where
$\operatorname{\mathfrak{S}}_{X}$ is the group of permutations on $X$. Given a
total order $<$ on $X$ and $g\in\Gamma$, the (strict) twin-width of $g$ acting
on $(X,<)$ is

$\operatorname{stww}_{(X,<)}(\phi(g))\stackrel{{\scriptstyle\text{def}}}{{=}}\operatorname{stww}\left(M_{\phi(g)}\right),$

where the $X\times X$ bijection matrix $M_{\phi(g)}$ is ordered according to
$<$.

The action of $\Gamma$ through $\phi$ is said to have finite twin-width with
regards to $<$ if $\operatorname{stww}_{(X,<)}(\phi(g))$ is finite for every
$g\in\Gamma$—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 $\Gamma$, the following are equivalent.

  1. (1)

Some (equivalently, every) Cayley graph of $\Gamma$ has finite twin-width
(equivalently, finite grid number).

  2. (2)

The action of $\Gamma$ 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\in\Gamma$ and $<$ a total order on $\Gamma$,
we denote by $M^{<}_{x}$ the matrix of the action of $x$ on $(\Gamma,<)$ by
right product.

Suppose that the action of $\Gamma$ on itself has finite grid number,
witnessed by some total order $<$ on $\Gamma$. Let us prove that
$\text{Cay}(\Gamma,S)$ has finite grid number for an arbitrary finite
generating set $S$. Let $M$ be the adjacency matrix of $\text{Cay}(\Gamma,S)$
with regards to $<$. Then $M$ is the superposition

$M=\operatorname*{\bigvee}_{s\in S\cup S^{-1}}M^{<}_{s}$

Any single $M^{<}_{x}$ has finite grid number by hypothesis, and $S\cup
S^{-1}$ is finite, thus it follows from Lemma 3.7 that $M$ has finite grid
number.

Conversely, assume that $\text{Cay}(\Gamma,S)$ has finite grid number for some
finite generating set $S$. This is witnessed by a total order $<$ on $\Gamma$
such that the adjacency matrix $M$ of $\text{Cay}(\Gamma,S)$ with regards to
$<$ has finite twin-width. For any $s\in S\cup 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\in\Gamma$ is now an arbitrary element, $x$ can be decomposed as some
product $x=s_{1}\dots s_{n}$ with $s_{i}\in S\cup S^{-1}$, and the action of
$x$ is the composition of the actions of $s_{1},\dots,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 $\Gamma$ 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.

###  5.2. Uniform twin-width

There is a natural strengthening of the former characterisation. Consider an
action of $\Gamma$ on $X$ given by
$\phi:\Gamma\to\operatorname{\mathfrak{S}}_{X}$. Given a total order $<$ on
$X$, the _uniform twin-width_ of $\phi$ with regards to $<$ is

$\operatorname{utww}_{(X,<)}(\phi)\stackrel{{\scriptstyle\text{def}}}{{=}}\sup_{g\in\Gamma}\operatorname{stww}_{(X,<)}(\phi(g)).$

Then, the uniform twin-width of $\phi$, denoted by
$\operatorname{utww}(\phi)$, is the minimum of
$\operatorname{utww}_{(X,<)}(\phi)$ over all choices of $<$ total order on
$X$. The uniform twin-width of a group $\Gamma$, denoted
$\operatorname{utww}(\Gamma)$, 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 twin-width implies finite
twin-width, while the converse is not a priori true.

###  5.3. Examples

Let us refine the examples of section 4. A _right-invariant_ order on a group
$\Gamma$ is a total order $<$ such that for all $x,y,z\in\Gamma$, $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 $\Gamma$,
then the action of any $x\in\Gamma$ 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.

$\operatorname{utww}(\Gamma_{1}\times\Gamma_{2})=\max(\operatorname{utww}(\Gamma_{1}),\operatorname{utww}(\Gamma_{2})).$

This is witnessed by a lexicographic order on $\Gamma_{1}\times\Gamma_{2}$.
Therefore all finitely generated abelian groups have uniform twin-width 2.

##  6\. 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\leqslant G$ is a subgroup, and $G$ has finite twin-
width, then so does $H$, and

$\operatorname{utww}(H)\leqslant\operatorname{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\in I}$, then

$\operatorname{utww}(G)=\sup_{i\in I}\operatorname{utww}(G_{i}).$

###### Proof.

For each $G_{i}$, let $<_{i}$ be an order witnessing that
$\operatorname{utww}(G_{i})\leqslant k$. By Lemma 2.1, there is an order $<$
on $G$ such that for any finite $X\subset G$, the orders $<$ and $<_{i}$
coincide on $X$ for some $i$.

For $x\in G$, let $M_{x}$ be the matrix of $x$ acting on $(G,<)$ by right
product. We want to show $\operatorname{stww}(M_{x})\leqslant k$, i.e. that
for every finite submatrix $M$ of $M_{x}$, $\operatorname{stww}(M)\leqslant
k$. Let $X$ contain the row and column indices of $M$, plus $x$. Since $X$ is
finite, there is some $i$ with $X\subset 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 $\operatorname{stww}(M)\leqslant k$,
which implies the result. ∎

######  Corollary 6.3.

Let $G$ be a group and let $\mathcal{H}$ be the collection of finitely
generated subgroups of $G$. Then

$\operatorname{utww}(G)=\sup_{H\in\mathcal{H}}\operatorname{utww}(H).$

###### Proof.

The group $G$ is direct limit of $\mathcal{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\leqslant G$. We write $G/H$ for the right quotient,
i.e. the set of right cosets $\textstyle\left\\{Hg\ |\ g\in G\right\\}$. 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\leqslant G$, the following statements hold.

  1. (1)

$\operatorname{utww}(G)\leqslant\max\left(\operatorname{utww}(H),\operatorname{utww}(G/H)\right)$.

  2. (2)

If $H$ has finite _uniform_ twin-width and $G/H$ has finite twin-width, then
$G$ has finite twin-width.

  3. (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.

######  Corollary 6.6.

If $G$ is an extension of $Q$ by $H$, i.e. $H\lhd G$ and $Q\cong G/H$

$\operatorname{utww}(G)\leqslant\max(\operatorname{utww}(H),\operatorname{utww}(Q)).$

######  Corollary 6.7.

If $G\rtimes H$ is any semi-direct product, then

$\operatorname{utww}(G\rtimes
H)=\max(\operatorname{utww}(G),\operatorname{utww}(H)).$

######  Corollary 6.8.

If $G$ is a group with $H\leqslant G$ a subgroup of finite index $[G:H]=k$,
then $G$ has finite twin-width if and only if $H$ does, and

$\operatorname{utww}(H)\leqslant\operatorname{utww}(G)\leqslant\max(\operatorname{utww}(H),k).$

###### Proof of Lemma 6.5.

For $x\in G$, let $\bar{x}\stackrel{{\scriptstyle\text{def}}}{{=}}Hx$ be its
equivalence class in $G/H$. We choose a transversal $T\subset G$ of $G/H$,
meaning that each class of $G/H$ can be uniquely written as $\bar{t}$ for some
$t\in 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

$\bar{x}<_{G/H}\bar{y}\quad\Longrightarrow\quad x<y.$

  * •

For $t\in T$, the order inside the coset $\bar{t}$ is defined by

$\forall x,y\in\bar{t},\quad x<y\quad\iff\quad xt^{-1}<_{H}yt^{-1}.$

For $a\in G$, let $M^{G}_{a}$ be the matrix of $a$ acting on $G$ by right
product with regards to $<$. Similarly, $M^{G/H}_{a}$ is the matrix of $a$
acting on $(G/H,<_{G/H})$, and for $b\in H$, $M^{H}_{b}$ is the matrix of $b$
acting on $(H,<_{H})$. Fix some $a\in G$.

######  Claim 6.9.

Suppose that $\operatorname{stww}(M^{G/H}_{a})\leqslant k$, and that for any
$t_{1},t_{2}\in T$, for
$r\stackrel{{\scriptstyle\text{def}}}{{=}}t_{1}at_{2}^{-1}\in H$, we have
$\operatorname{stww}(M^{H}_{r})\leqslant k$. Then

$\operatorname{stww}(M^{G}_{a})\leqslant k.$

###### Proof.

Let $t_{1},t_{2}\in T$ be such that $t_{1}at_{2}^{-1}\in H$, or equivalently,
right multiplication by $a$ maps the coset $\bar{t}_{1}=Ht_{1}$ to
$\bar{t}_{2}=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 $(\bar{t}_{1},\bar{t}_{2})$ 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 $\operatorname{stww}(P^{t_{1},t_{2}}_{a})\leqslant k$.

$Hs_{1}$$Ht_{1}$$Ht_{2}$$Hs_{2}$$P^{s_{1},s_{2}}_{a}$$P^{t_{1},t_{2}}_{a}$$x_{1}t_{1}$$x_{2}t_{1}$$y_{1}t_{2}$$y_{2}t_{2}$$1$$1$
Figure 6. Example of shape of $M^{G}_{a}$. Here, $s_{i},t_{i}$ are in $T$ with
$\bar{s}_{1}<_{G/H}\bar{t}_{1}$, $\bar{t}_{2}<_{G/H}\bar{s}_{2}$, and
$t_{1}at_{2}^{-1},s_{1}as_{2}^{-1}\in H$. 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_{2}^{-1}$. The general shape of
$M^{G}_{a}$ (left matrix) corresponds to $M^{G/H}_{a}$, while the block
$P^{t_{1},t_{2}}_{a}$ (right matrix) is equal to $M^{H}_{r}$.

Define $r\stackrel{{\scriptstyle\text{def}}}{{=}}t_{1}at_{2}^{-1}\in H$. We
claim that $P^{t_{1},t_{2}}_{a}$ is isomorphic to $M^{H}_{r}$. Indeed, right
product by $t_{1}$ (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}}_{a}$. Furthermore, these
bijections transform right product by $a$ into right product by $r$, in that
for all $x\in H$

(4) $(xt_{1})a=x(t_{1}at_{2}^{-1})t_{2}=(xr)t_{2}.$

Thus $P^{t_{1},t_{2}}_{a}\cong M^{H}_{r}$, and
$\operatorname{stww}(P^{t_{1},t_{2}}_{a})\leqslant k$ follows from the
hypotheses. ∎

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

  1. (1)

is immediate.

  2. (2)

Given a uniform bound on $\operatorname{stww}(M^{H}_{r})$ for all $r\in H$,
and a bound on $\operatorname{stww}(M^{G/H}_{a})$, the claim gives a bound on
$\operatorname{stww}(M^{G}_{a})$. Remark that since the bound on
$\operatorname{stww}(M^{H}_{r})$ is used for $r=t_{1}at_{2}^{-1}$ for all
appropriate choices of $t_{1},t_{2}$, the uniform bound is a priori required.

  3. (3)

If $G/H$ is finite however, there are only finitely many $r=t_{1}at_{2}^{-1}$
for which the bound on $\operatorname{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\lhd 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 Propositions 6.4 and 6.6. ∎

If $\Gamma$ is a group finitely generated by $S$, its _growth function_ is

$g_{(\Gamma,S)}(r)\stackrel{{\scriptstyle\text{def}}}{{=}}|{B(1_{\Gamma},r)}|,$

where $B(1_{\Gamma},r)$ is the ball of radius $r$ centered on the identity
element in $\text{Cay}(\Gamma,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 twin-width.

###### Proof.

Immediate by Theorems 6.11, 6.10 and 6.8. ∎

When $H\lhd G$, Lemma 6.5 gives an upper bound on $\operatorname{utww}(G)$ by
$\operatorname{utww}(H)$ and $\operatorname{utww}(G/H)$. There is also a
trivial lower bound $\operatorname{utww}(G)\geqslant\operatorname{utww}(H)$.
However $\operatorname{utww}(G/H)$ gives no lower bound on
$\operatorname{utww}(G)$ in general: it can be that $\operatorname{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\lhd G$ a normal subgroup with $|{N}|=t<\infty$. Then
$G$ has finite twin-width if and only if $G/N$ does. Furthermore

$\displaystyle\operatorname{utww}(G)$
$\displaystyle\leqslant\max(\operatorname{utww}(G/N),t),~{}\text{and}$
$\displaystyle\operatorname{utww}(G/N)$ $\displaystyle\leqslant
2^{t^{O(\operatorname{utww}(G)\cdot t)}}.$

###### Proof.

Using Corollary 6.6 and the trivial bound $\operatorname{utww}(N)\leqslant t$,
if $G/N$ has finite twin-width then so does $G$, and
$\operatorname{utww}(G)\leqslant\max(\operatorname{utww}(G/N),t)$.

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

$\forall a,b\in G/N,\quad a<_{G/N}b\iff\iota(a)<\iota(b).$

For $x\in G$, let $M^{G}_{x}$ be the matrix of $x$ acting on $(G,<)$ by right
product, and similarly in $G/N$. Fix some $a\in G/N$. We want a bound on
$\operatorname{stww}(M^{G/N}_{a})$.

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

$\forall b_{1},b_{2}\in G/N,\quad
S(b_{1},b_{2})=1\iff\iota(b_{1})^{-1}\iota(b_{2})\in a.$

It can be seen as the superposition of $M^{G}_{x}$ for $x\in a$, restricted to
the submatrix with $\iota(G/N)$ as indices. If $b_{1}a=b_{2}$, then
$\iota(b_{1})^{-1}\iota(b_{2})\in 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
$\operatorname{stww}(M^{G/N}_{a})\leqslant\operatorname{stww}(S)$.

Suppose now that $\operatorname{utww}(G)\leqslant k$ is witnessed by the order
$<$, meaning that for $x\in G$, $\operatorname{stww}(M^{G}_{x})\leqslant k$.
Using Theorems 3.2 and 3.7, and that $S$ is contained in the superposition of
$t$ matrices $M^{G}_{x}$, we obtain

$\operatorname{stww}(M^{G/N}_{a})\leqslant\operatorname{stww}(S)\leqslant
2^{t^{O(tk)}}.$

If $G$ merely has finite twin-width witnessed by $<$, there still is a bound
on $\operatorname{stww}(M^{G}_{x})$ for $x\in a$ with $a$ fixed, because $a$
is finite. The same arguments show that $\operatorname{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\in I}$ a family of groups, their _direct product_ is denoted
by $\prod_{i\in I}G_{i}$. Their _direct sum_ $\bigoplus_{i\in I}G_{i}$ is the
subgroup of the direct product consisting of finitely supported tuples, i.e.
the $(x_{i})_{i\in I}$ with $x_{i}\in 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\in I}$ a possibly infinite family of groups, consider
$S=\bigoplus_{i\in I}G_{i}$ their direct sum, and $P=\prod_{i\in I}G_{i}$
their direct product. Then $S$ has finite twin-width if and only if all
$G_{i}$ do, and

$\operatorname{utww}(S)=\operatorname{utww}(P)=\sup_{i\in
I}\operatorname{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 $\operatorname{utww}(G_{i})\leqslant k$ is witnessed by $<_{i}$, Lemma
3.6 immediately gives $\operatorname{utww}(P)\leqslant k$, and a fortiori
$\operatorname{utww}(S)\leqslant 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\in I}\in 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\wr H\stackrel{{\scriptstyle\text{def}}}{{=}}G^{H}\rtimes H$

where $H$ acts by permuting indices by right product, i.e. for
$h,h^{\prime}\in H$ and $x\in G^{H}$, the action of $h$ is

$(x\cdot
h)(h^{\prime})\stackrel{{\scriptstyle\text{def}}}{{=}}x(h^{\prime}h).$

One may also consider the restricted wreath product, with a direct sum
replacing the direct product, and the same action of $H$.

$G\wr_{r}H\stackrel{{\scriptstyle\text{def}}}{{=}}\left(\bigoplus_{h\in
H}G\right)\rtimes H.$

It is a subgroup of the complete wreath product.

######  Lemma 6.15.

$\operatorname{utww}(G\wr
H)=\max(\operatorname{utww}(G),\operatorname{utww}(H)).$

###### Proof.

By Lemmas 6.14 and 6.7. ∎

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

###  6.4. Group actions

The twin-width of a group is defined through its self-action 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
$<_{\operatorname{\mathfrak{S}}_{X}}$ on the permutation group
$\operatorname{\mathfrak{S}}_{X}$ such that for
$\sigma\in\operatorname{\mathfrak{S}}_{X}$

$\operatorname{stww}_{\operatorname{\mathfrak{S}}_{X}}(\sigma)\leqslant\operatorname{stww}_{X}(\sigma)$

where the right-hand side is the twin-width of $\sigma$ acting on $(X,<_{X})$,
whereas the left-hand side is the twin-width of $\sigma$ acting on
$(\operatorname{\mathfrak{S}}_{X},<_{\operatorname{\mathfrak{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 $\operatorname{\mathfrak{S}}_{X}$,
i.e. for $\sigma,\tau\in\operatorname{\mathfrak{S}}_{X}$ and $x\in X$, we
write $x\cdot\sigma=\sigma(x)$ and $\sigma\tau=\tau\circ\sigma$.

We order $X^{X}$ lexicographically, i.e. for any $f\neq g:X\to X$, define
$m_{f,g}=\min\textstyle\left\\{x\in X\ |\ x\cdot f\neq x\cdot g\right\\}$ and

$f<_{X^{X}}g\quad\iff\quad m_{f,g}\cdot f<_{X}m_{f,g}\cdot g.$

The group $\operatorname{\mathfrak{S}}_{X}$ acts on $X^{X}$ by post-
composition, that is $(f\cdot\sigma)(x)=f(x)\cdot\sigma$. We define
$<_{\operatorname{\mathfrak{S}}_{X}}$ by restricting the former order from
$X^{X}$ to $\operatorname{\mathfrak{S}}_{X}$, while the restriction of this
action is simply right product.

For $\sigma\in\operatorname{\mathfrak{S}}_{X}$, let $M_{\sigma}$ be the matrix
of $\sigma$ acting on $(X,<_{X})$, let $M^{X}_{\sigma}$ be the matrix of
$\sigma$ acting on $(X^{X},<_{X^{X}})$ by post-composition, and let
$M^{\operatorname{\mathfrak{S}}_{X}}_{\sigma}$ be the matrix of $\sigma$
acting on
$(\operatorname{\mathfrak{S}}_{X},<_{\operatorname{\mathfrak{S}}_{X}})$ by
right product. Then $M^{X}_{\sigma}$ is a tensor product of $M_{\sigma}$ with
itself, hence by Lemma 3.6, we have
$\operatorname{stww}(M^{X}_{\sigma})=\operatorname{stww}(M_{\sigma})$.
Furthermore $M^{\operatorname{\mathfrak{S}}_{X}}_{\sigma}$ is clearly a
submatrix of $M^{X}_{\sigma}$, thus

$\operatorname{stww}_{\operatorname{\mathfrak{S}}_{X}}(\sigma)=\operatorname{stww}(M^{\operatorname{\mathfrak{S}}_{X}}_{\sigma})\leqslant\operatorname{stww}(M^{X}_{\sigma})=\operatorname{stww}(M_{\sigma})=\operatorname{stww}_{X}(\sigma).$

∎

######  Corollary 6.17.

Let $(X,<_{X})$ be a well-ordered set, and $G$ a 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
$\operatorname{utww}(G)\leqslant k$.

###### Proof.

Through the faithful action, $G$ is a subgroup of
$\operatorname{\mathfrak{S}}_{X}$. ∎

Let $T$ be the infinite rooted binary tree. Let $\operatorname{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 $\operatorname{Aut}(T)$ is
uncountable, but it has some interesting finitely generated subgroups, notably
the Grigorchuk group [15].

######  Proposition 6.18.

The group $\operatorname{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
$\operatorname{Aut}(T)$ on $T$ with regards to $<$ has uniform twin-width 2.

Let $f\in\operatorname{Aut}(T)$, and for $d\in\mathbb{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
$\operatorname{stww}(M_{f_{d}})=2$ for all $d$. (These are _separable_
permutation matrices, see [19, Section 3.2].) Finally, the matrix of $f$ can
be seen as the $\mathbb{N}\times\mathbb{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 $\operatorname{\mathfrak{S}}_{\mathbb{Z}}$ be the group of permutations on
$\mathbb{Z}$, and let $\operatorname{\mathfrak{S}}_{\mathbb{Z}}^{f}$ be the
subgroup consisting of finitely supported permutations. Furthermore, let
$T=\textstyle\left\\{x\mapsto x+c\ |\ c\in\mathbb{Z}\right\\}$ the subgroup of
translations. While $\operatorname{\mathfrak{S}}_{\mathbb{Z}}^{f}$ is not
finitely generated, $\operatorname{\mathfrak{S}}_{\mathbb{Z}}^{f}\rtimes T$
is. The latter is sometimes called lampshuffler group.

Consider the well-order $0,1,-1,2,-2,\dots$ on $\mathbb{Z}$. The transposition
of $0$ and $1$ and the translation by $1$ are two permutations of $\mathbb{Z}$
which generate $\operatorname{\mathfrak{S}}_{\mathbb{Z}}^{f}\rtimes T$, and
whose action on $\mathbb{Z}$ clearly has finite twin-width. Thus, by Lemma
3.11, the action of the lampshuffler on $\mathbb{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\in\mathbb{N}$.

  1. (1)

For all finite group $G$, $\operatorname{utww}(G)\leqslant k$.

  2. (2)

$\operatorname{utww}(\operatorname{\mathfrak{S}}_{\mathbb{Z}}^{f}\rtimes
T)\leqslant k$.

  3. (3)

For all elementary amenable group $G$, $\operatorname{utww}(G)\leqslant k$.

###### Proof.

The lampshuffler $\operatorname{\mathfrak{S}}_{\mathbb{Z}}^{f}\rtimes T$ is
elementary amenable and contains all finite groups, hence (3) implies (2)
which implies (1). 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\geqslant 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 [8]. It follows by
Corollaries 6.6 and 6.2 that all elementary amenable groups have twin-width at
most $k$. ∎

One could replace $\operatorname{\mathfrak{S}}_{\mathbb{Z}}^{f}\rtimes T$ with
just $\operatorname{\mathfrak{S}}_{\mathbb{Z}}^{f}$ 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.

##  7\. 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 twin-width in a Cayley graph. The existence of such graphs is
given by counting arguments (see Theorem 1.1). The embedding into a group uses
the following result of Osajda, based on graphical small cancellation theory.

######  Theorem 7.1 ([28, Theorem 3.2]).

Consider constants $A>0$ and $D\in\mathbb{N}$, and let
$(G_{n})_{n\in\mathbb{N}}$ be a sequence of connected graphs such that

  1. (1)

$\Delta(G_{n})\leqslant D$,

  2. (2)

$\textsf{girth}(G_{n})\geqslant\textsf{girth}(G_{n-1})+6$, and

  3. (3)

$\textsf{diam}(G_{n})/\textsf{girth}(G_{n})\leqslant A$.

Then there exists a group $\Gamma$ finitely generated by $S$ such that every
$G_{n}$ isometrically embeds in $\text{Cay}(\Gamma,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 following444Logarithms in this section are in base 2.:

  1. (1)

Each $G_{n}$ has maximum degree at most 6,

  2. (2)

$\textsf{diam}(G_{n})\leqslant 3\log|{V(G_{n})}|$, and

  3. (3)

$\textsf{girth}(G_{n})>\frac{1}{4}\log|{V(G_{n})}|$.

For $n\in\mathbb{N}$, we write $[n]=\\{1,\dots,n\\}$. For $n$ even, let
$\mathcal{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$,

$|{\mathcal{C}_{1}(n)}|>n!\cdot c^{n}.$

###### Proof.

The class $\mathcal{C}_{1}(n)$ contains all possible choices of 3 perfect
matchings from $\\{1,\dots,n/2\\}$ to $\\{n/2+1,\dots,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!\cdot c^{n}$. ∎

Fix $n\in\mathbb{N}$ even and define
$g\stackrel{{\scriptstyle\text{def}}}{{=}}\log(n)/4$. Define
$\mathcal{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 $\mathcal{C}_{1}(n)$ can be obtained from graphs of
$\mathcal{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 $\mathcal{C}_{1}(n)$, then the
expected number of cycles in $G$ of length at most $g$ is at most $2\cdot
6^{g}$.

###### Proof.

Let $C$ be a potential cycle of length $\ell\leqslant g$ properly edge-colored
with $1,2,3$; that is, a sequence $v_{1},\dots,v_{\ell}$ of vertices in $[n]$
where each potential edge $v_{i}v_{i+1}$ (with indices modulo $\ell$) 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
$\frac{n}{2}/\binom{n}{2}=\frac{1}{n-1}$. If these probabilities were
independent, $C$ would appear in $G$ with probability exactly $(n-1)^{-\ell}$.
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\leqslant\ell\leqslant g\ll n$, hence this
probability is upper bounded by $2/n$. Thus the probability that $C$ appears
in $G$ is at most $(2/n)^{\ell}$. Therefore the expected total number of
cycles of length at most $g$ in $G$ is at most

$\sum_{i=2}^{g}3^{i}\cdot n^{i}\cdot(2/n)^{i}\leqslant 2\cdot 6^{g}.$

∎

######  Lemma 7.4.

For any even $n$, for at least half of the graphs $G=(V,E)$ in
$\mathcal{C}_{1}(n)$, there exists $G^{\prime}=(V,E^{\prime})$ in
$\mathcal{C}_{2}(n)$ such that $|E\triangle E^{\prime}|=O(n^{7/8})$, where
$\triangle$ denotes the symmetric difference.

###### Proof.

By Lemma 7.3 and Markov’s inequality, at least half of the graphs $G_{1}$ in
$\mathcal{C}_{1}(n)$ have at most $4\cdot 6^{g}$ cycles of length at most $g$.
Let $G_{1}$ be such a graph, and choose $F\subset E(G_{1})$ of size at most
$4\cdot 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}|\leqslant 8\cdot
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\cdot 2^{d}$
vertices. It follows that

(5) $|{N}|\leqslant 8\cdot 6^{g}\cdot 3\cdot
2^{g/2}=24\cdot(6\sqrt{2})^{g}\leqslant 24\cdot n^{\log(6\sqrt{2})/4}.$

Observe that $\log(6\sqrt{2})/4\leqslant 7/8$, hence

(6) $|{N}|\leqslant 24\cdot n^{7/8}.$

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\cap N$, and $X_{2}=X\setminus N$.

Let $v\in 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}}|\geqslant 2^{g/2}=n^{1/8}.$

Finally, any distinct $v,v^{\prime}\in X_{2}$ are at distance at least $\log
n$, which is more than $g$. Thus the balls $B_{v}$ and $B_{v^{\prime}}$ are
disjoint. It follows from Eq. 7 that

(8) $|{X_{2}}|\leqslant\frac{|{V(G_{2})}|}{n^{1/8}}=n^{7/8}.$

Using that $X=X_{1}\cup X_{2}$, $X_{1}\subset N$, and Eqs. 6 and 8, we obtain

(9) $|{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}\in\mathcal{C}_{2}(n)$.

To summarize, we transform $G_{1}$ into $G_{3}$ by deleting $|{F}|\leqslant
4\cdot 6^{g}$ edges, and then adding $|{X}|$ edges, which gives $O(n^{7/8})$
edge editions in total. ∎

######  Lemma 7.5.

The class $\mathcal{C}_{2}$ is not small. Precisely, for any constant $c$ and
any sufficiently large even $n$,

$|{\mathcal{C}_{2}(n)}|\geqslant n!\cdot c^{n}.$

###### Proof.

Fix $c$, consider $n$ even sufficiently large, and suppose for a contradiction
that $|{\mathcal{C}_{2}(n)}|\leqslant n!\cdot 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

(10) $\binom{n^{2}}{n^{7/8}}\leqslant n^{2n^{7/8}}\leqslant
2^{n},~{}\text{asymptotically}.$

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

(11) $2^{n}\cdot 3^{3n/2}\cdot n!\cdot c^{n}\leqslant n!\cdot c_{2}^{n}$

for some constant $c_{2}$. By Lemma 7.4, the cardinality of
$\mathcal{C}_{1}(n)$ is at most double the previous value, a contradiction of
Lemma 7.2. ∎

*

###### Proof.

By Lemmas 7.5 and 1.1, for any $k\in\mathbb{N}$ and for any sufficiently large
$n_{k}$, $\mathcal{C}_{2}(n_{k})$ contains graphs of twin-width more than $k$.
Thus, one can construct a sequence $(G_{k})_{k\in\mathbb{N}}$ of graphs such
that $\operatorname{tww}(G_{k})>k$ and $G_{k}\in\mathcal{C}_{2}(n_{k})$, for
any sequence $(n_{k})_{k\in\mathbb{N}}$ of even integers growing sufficiently
fast. Since $\textsf{girth}(G_{k})\geqslant\log(n_{k})/4$, an appropriate
choice of $n_{k}$ ensures that
$\textsf{girth}(G_{k})\geqslant\textsf{girth}(G_{k-1})+6$. Then
$(G_{k})_{k\in\mathbb{N}}$ satisfies the hypotheses of Theorem 7.1, hence
there exists a group $\Gamma$ finitely generated by $S$ such that every
$G_{k}$ isometrically embeds in $\text{Cay}(\Gamma,S)$. This group has
infinite twin-width. ∎

###  7.2. Computability considerations

In this section, we argue that the proof of section 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
$\left\langle S;R\right\rangle$, 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 [20], 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 section 1 in three steps, and
prove that each of them is effective.

  1. (1)

Constructing the sequence of graphs $(G_{k})_{k\in\mathbb{N}}$, with
appropriate conditions on degree, girth, diameter, and twin-width (section
7.1).

  2. (2)

Adding labels to this sequence satisfying the small cancellation conditions.
This is the core of Osajda’s proof, see [28, Section 2].

  3. (3)

Obtaining a group from this small cancellation graph labelling. This
construction, attributed to Gromov [18], 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\in\mathbb{N}}$,
satisfying the hypotheses of Theorem 7.1, and with unbounded twin-width.

###### Proof.

By Lemmas 7.5 and 1.1, one can find such a sequence by choosing a
$G_{k}\in\mathcal{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, 7.4 and 7.5. This yields a naive algorithm: Enumerate all graphs
of size $n_{k}$ until finding one in $\mathcal{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
$\mathcal{C}_{1}(n_{k})$. Edge editions are performed according to Lemma 7.4,
and the process is aborted should it require more than $4\cdot 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 $\mathcal{C}_{2}(n_{k})$.
Although the distribution of $G_{k}$ over $\mathcal{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\subset\mathcal{C}_{2}(n_{k})$ of size $|{X}|\leqslant
n!\cdot 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.1 that the sequence
$(G_{k})_{k\in\mathbb{N}}$ has unbounded twin-width with probability 1. Thus,
this probabilistic algorithm does not even need to compute the twin-width of
any graph.

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\in\mathbb{N}}$ with
an edge labelling satisfying the small cancellation condition: if
$p,p^{\prime}$ are two distinct paths in $G_{k},G_{k^{\prime}}$ respectively,
with the same length and edge labelling, then
$|p|<\lambda\cdot\textsf{girth}(G_{k})$, and
$|p^{\prime}|<\lambda\cdot\textsf{girth}(G_{k^{\prime}})$, where $\lambda>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},\dots,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},\dots,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 [25] may be helpful to improve the
complexity.

####  7.2.3. Deciding the word problem

The former labelling of $(G_{k})_{k\in\mathbb{N}}$ uses labels in $S\uplus
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

$\Gamma=\left\langle S;R\right\rangle$

where the set $R$ of relators contains all words on $S\uplus S^{-1}$ read
along some cycle of some $G_{k}$. This set $R$ is recursive: given some word
$w$ over $S\uplus S^{-1}$, to decide if $w\in R$, one must test if $w$ appears
as the labelling of some cycle of some $G_{k}$. This can only happen if
$\textsf{girth}(G_{k})\leqslant|w|$. Since $\textsf{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 [27]).

Let $G$ be a finite graph equipped with an edge labelling on $S\uplus S^{-1}$
satisfying the small cancellation condition. Let $R$ be the set of words read
along the cycles of $G$, and $\Gamma=\left\langle S;R\right\rangle$. If $w$ is
a word over $S\uplus S^{-1}$ which represents the identity of $\Gamma$, then
some relator $r\in R$ can be applied to $w$ to reduce it to $w^{\prime}$, with
$|{w^{\prime}}|<|{w}|$.

Although the above is stated for a finite graph, it generalises to a sequence
of finite graphs. Suppose a word $w$ over $S\uplus S^{-1}$ represents the
identity of $\Gamma$. 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\in\mathbb{N}}$, say
$G_{0},\dots,G_{s}$. Then $w$ is also equal to $1$ in the group $\left\langle
S;R^{\prime}\right\rangle$ where the relators $R^{\prime}$ are the ones read
along some cycle of $G_{0}\cup\dots\cup G_{s}$. We conclude by applying Lemma
7.9 to $\left\langle S;R^{\prime}\right\rangle$.

Where Greendlinger’s lemma applies, the word problem can be decided using
Dehn’s algorithm: given a word $w$ on $S\cup 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 $\Gamma$. This algorithm
works for $\Gamma$ 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

##  8\. 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)=\biguplus_{i=1}^{t}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
$\operatorname{qn}(G)$ (resp. $\operatorname{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
$\Delta$, given a $t$-queue-layout, refining the partition of edges with a
proper edge coloring gives a strict $(\Delta+1)t$-queue layout using Vizing’s
theorem. Thus

(12)
$\operatorname{qn}(G)\leqslant\operatorname{sqn}(G)\leqslant(\Delta+1)\operatorname{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.

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

###  8.2. Matrix characterisation

Say that an $X\times Y$ matrix $M$ is increasing if it is the matrix of an
increasing partial map, i.e. whenever there are 1-coefficients 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

(13) $\operatorname{sqn}(G)\leqslant\operatorname{sqn}(A_{<}(G))\leqslant
2\operatorname{sqn}(G).$

The first inequality is simple, and the second is obtained by using up to
$\operatorname{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 $\operatorname{sqn}(M)\leqslant 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: $\operatorname{sqn}(G^{(k)})$ is bounded by a
function of $\operatorname{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

$\operatorname{uqn}(G)\stackrel{{\scriptstyle\text{def}}}{{=}}\min_{\text{$<$
order on $G$}}\ \sup_{x\in G}\ \operatorname{sqn}(M_{x}^{<})$

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. Twin-width 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

(14) $\operatorname{sqn}(M[N])=\operatorname{sqn}(M)\operatorname{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
$\operatorname{uqn}(G\times
H)\leqslant\operatorname{uqn}(G)\operatorname{uqn}(H)$ by (14), and this bound
is tight for this specific choice of order. However, there might be a better
choice of order on $G\times H$ giving $\operatorname{uqn}(G\times
H)=\max(\operatorname{uqn}(G),\operatorname{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.

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

  1. (1)

Hyperbolic groups have finite queue number.

  2. (2)

Right-orderable groups have uniform queue number 1, and this is a
characterisation.

  3. (3)

Finitely generated abelian groups have finite uniform queue number, but a
priori without a universal bound.

  4. (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. (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
$\mathbb{Z}/2\mathbb{Z}$ 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 [1], 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 $\sigma\in G_{n-1}$ by substituting each ‘1’-coefficient of
$\sigma$ 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
$\operatorname{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 $\operatorname{Aut}(T)$ are not clear, but it is
likely that an answer to either question would give significant insight for
the other.

## References

  * [1] Yonatan Bilu and Nathan Linial.  Lifts, discrepancy and nearly optimal spectral gap.  Combinatorica, 26(5):495–519, 2006.
  * [2] Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes, and Stéphan Thomassé.  Twin-width VIII: delineation and win-wins.  CoRR, abs/2204.00722, 2022.
  * [3] Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width II: small classes.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pages 1977–1996, 2021.
  * [4] Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width III: max independent set, min dominating set, and coloring.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 35:1–35:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [5] Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk.  Twin-width IV: ordered graphs and matrices.  CoRR, abs/2102.03117, 2021, to appear at STOC 2022.
  * [6] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width I: tractable FO model checking.  J. ACM, 69(1):3:1–3:46, 2022.
  * [7] Sergei Buyalo, Alexander Dranishnikov, and Viktor Schroeder.  Embedding of hyperbolic groups into products of binary trees.  Inventiones mathematicae, 169(1):153–192, 2007.
  * [8] Ching Chou.  Elementary amenable groups.  Illinois Journal of Mathematics, 24(3):396–407, 1980.
  * [9] Josef Cibulka and Jan Kyncl.  Füredi-Hajnal limits are typically subexponential.  CoRR, abs/1607.07491, 2016.
  * [10] Guoli Ding and Bogdan Oporowski.  Some results on tree decomposition of graphs.  Journal of Graph Theory, 20(4):481–499, 1995.
  * [11] Vida Dujmovic, Pat Morin, and David R Wood.  Layout of graphs with bounded tree-width.  SIAM Journal on Computing, 34(3):553–579, 2005.
  * [12] David Eppstein, Laura Merker, Sergey Norin, Michał T Seweryn, David R Wood, et al.  Three-dimensional graph products with unbounded stack-number.  arXiv preprint arXiv:2202.05327, 2022.
  * [13] Jacob Fox.  Stanley-Wilf limits are typically exponential.  CoRR, abs/1310.8378, 2013.
  * [14] Joseph L Ganley and Lenwood S Heath.  The pagenumber of k-trees is O(k).  Discrete Applied Mathematics, 109(3):215–221, 2001.
  * [15] Rostislav Ivanovich Grigorchuk.  Burnside problem on periodic groups.  Funktsional’nyi Analiz i ego Prilozheniya, 14(1):53–54, 1980.
  * [16] Mikhael Gromov.  Groups of polynomial growth and expanding maps (with an appendix by Jacques Tits).  Publications Mathématiques de l’IHÉS, 53:53–78, 1981.
  * [17] Mikhael Gromov.  Hyperbolic groups.  In Essays in group theory, pages 75–263. Springer, 1987.
  * [18] Mikhail Gromov.  Random walk in random groups.  Geometric & Functional Analysis GAFA, 13(1):73–146, 2003.
  * [19] Sylvain Guillemot and Dániel Marx.  Finding small patterns in permutations in linear time.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 82–101, 2014.
  * [20] Graham Higman.  Subgroups of finitely presented groups.  Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 262(1311):455–475, 1961.
  * [21] Dietrich Kuske and Markus Lohrey.  Logical aspects of Cayley-graphs: the group case.  Annals of Pure and Applied Logic, 131(1-3):263–286, 2005.
  * [22] Roger C Lyndon and Paul E Schupp.  Combinatorial group theory, volume 188.  Springer, 1977.
  * [23] Seth M Malitz.  Graphs with E edges have pagenumber $O(\sqrt{E})$.  Journal of Algorithms, 17(1):71–84, 1994.
  * [24] Adam Marcus and Gábor Tardos.  Excluded permutation matrices and the Stanley-Wilf conjecture.  J. Comb. Theory, Ser. A, 107(1):153–160, 2004.
  * [25] Robin A Moser and Gábor Tardos.  A constructive proof of the general Lovász local lemma.  J. ACM, 57(2):1–15, 2010.
  * [26] Serguei Norine, Paul D. Seymour, Robin Thomas, and Paul Wollan.  Proper minor-closed families are small.  J. Comb. Theory, Ser. B, 96(5):754–757, 2006.
  * [27] Yann Ollivier.  On a small cancellation theorem of Gromov.  Bulletin of the Belgian Mathematical Society-Simon Stevin, 13(1):75–89, 2006.
  * [28] Damian Osajda.  Small cancellation labellings of some infinite graphs and applications.  Acta Mathematica, 225(1):159 – 191, 2020.