# A threshold for relative hyperbolicity in
random right-angled Coxeter groups

Jason Behrstock Department of Mathematics, Lehman College and The Graduate
Center, CUNY, New York, USA. Email<EMAIL_ADDRESS>Research
supported by a Simons Fellowship. R. Altar Çiçeksiz Institutionen för
Matematik och Matematisk Statistik, Umeå Universitet, Sweden. Emails:
altar.ciceksiz<EMAIL_ADDRESS>Research supported by Swedish
Research Council grant VR 2021-03687. Victor Falgas-Ravry††footnotemark:

###### Abstract

We consider the random right-angled Coxeter group $W_{\Gamma}$ whose
presentation graph $\Gamma\sim\mathcal{G}_{n,p}$ is an Erdős–Rényi random
graph on $n$ vertices with edge probability $p=p(n)$. We establish that
$p=1/\sqrt{n}$ is a threshold for relative hyperbolicity of the random group
$W_{\Gamma}$. As a key step in the proof, we determine the minimal number of
pairs of generators that must commute in a right-angled Coxeter group which is
not relatively hyperbolic, a result which is of independent interest.

We also show that there is a interval of edge probabilities of width
$\Omega(1/\sqrt{n})$ in which the random right-angled Coxeter group has
precisely cubic divergence. This interval is between the thresholds for
relative hyperbolicity (whence exponential divergence) and quadratic
divergence. Moreover, any simple random walk on any Cayley graph of the random
right-angled Coxeter group for $p$ in this interval satisfies a central limit
theorem.

##  1 Introduction

In his famous treatise [23], Gromov initiated the study of random groups with
the statement that “almost all” groups are hyperbolic. This idea was developed
further in work by Gromov and others, who established that for a number of
random group models as one varies a model parameter one sees a threshold at
which the typical behaviour changes from one regime into another: on one side
of the threshold, random groups outputted by the model are typically infinite
and hyperbolic, while on the other side of the threshold they are typically
finite, see e.g. Gromov [24], Ollivier [28] and Ol’shanskii [29]. The world of
these random group models thus splits into two distinct regimes. As we shall
see, this stands in some contrast with the model studied in this paper.

The right-angled Coxeter group (or RACG) $W_{\Gamma}$ with presentation graph
$\Gamma=(V,E)$ is the group with generators $V$ and relations
$a^{2}=\mathrm{id}$ and $ab=ba$ for all $a\in V$ and $ab\in E$. We will use
the Erdős–Rényi random graph model, which is defined as follows: for
$n\in\mathbb{N}$ and a sequence of probabilities $p=p(n)\in[0,1]$, we define a
random graph $\mathcal{G}_{n,p}$ on the vertex set $[n]:=\\{1,2,\ldots n\\}$
by including each of the $\binom{n}{2}$ possible edges with probability
$p(n)$, independently at random. We write $\Gamma\sim\mathcal{G}_{n,p}$ to
denote the fact that $\Gamma$ is a random graph with the same distribution as
$\mathcal{G}_{n,p}$. To any $\Gamma\sim\mathcal{G}_{n,p}$ one can associate
the RACG $W_{\Gamma}$ thereby obtaining a model for a _random right-angled
Coxeter group_.

The random right-angled Coxeter group was shown by Charney–Farber to be
typically infinite and hyperbolic if $pn\to 0$, and finite if $p(1-n)^{2}\to
0$ [10, Corollary 2]. However, unlike in the types of models introduced by
Gromov, there is a universe of interesting behavior which occurs between these
two extremes. In this paper we make progress towards understanding the algebra
and geometry of such groups via combinatorial and probabilistic tools.

The past two decades have revealed that generalizations of hyperbolicity
provide a powerful framework for studying finitely generated groups. One of
the strongest types of such “non-positive curvature” is called _relative
hyperbolicity_. This notion was introduced by Gromov [23], then developed by
Farb [20] and eventually given many equivalent geometric, topological, and
dynamical formulations, see Bowditch [9], Dahmani [12], Druţu and Sapir [17],
Osin [30], Sisto [32, 33], Yaman [37], and others. Relative hyperbolicity is
both general enough to include many important classes of groups including for
example all fundamental groups of finite-volume hyperbolic manifolds and all
finitely generated groups with infinitely many ends, while being sufficiently
restrictive to yield powerful implications concerning geometric, algebraic,
and algorithmic properties, see Arzhantseva, Minasyan and Osin [1], Druţu
[16], Druţu and Sapir [19], Farb [20], and many others.

Roughly speaking, a group is _relatively hyperbolic_ when all its ‘non-
hyperbolicity’ is confined to certain subgroups that do not interact with each
other in any substantial way. In this paper, rather than working directly with
the definition of relative hyperbolicity, we will rely on two of the main
results of Behrstock, Hagen and Sisto [7, Theorems I and II], which, in the
context of RACGs, establishes a necessary and sufficient criterion for
relative hyperbolicity in terms of combinatorial properties of the
presentation graph.

The main result in this paper is the following which shows that a random RACG
transitions from being asymptotically almost surely (a.a.s.) relatively
hyperbolic to being a.a.s. not relatively hyperbolic around $p=1/\sqrt{n}$.

######  Theorem 1.1.

Let $p=p(n)$ and $\Gamma\sim\mathcal{G}(n,p)$. Then the following hold:

  1. (i)

if $p\leq\frac{1}{4\sqrt{n\log n}}$ then $\Gamma$ is a.a.s. relatively
hyperbolic;

  2. (ii)

if $p\geq\frac{\sqrt{\sqrt{6}-2}}{\sqrt{n}}$ then $\Gamma$ is a.a.s. not
relatively hyperbolic.

We note that this threshold provides a wide range of RACGs which are both
relatively hyperbolic and one-ended, since the threshold for one-endedness
occurs much lower, at $p=\frac{\log(n)}{n}$, see [7, Theorem 3.2].

A powerful geometric invariant for distinguishing finitely generated groups is
their _divergence_. This notion was introduced by Gromov [24] and refined by
Gersten [21, 22] and, roughly speaking, is a function of $r$ providing a
measure of the length of a shortest path needed to connect a pair of points at
distance $r$ in a geodesic space while avoiding a ball of radius linear in $r$
around a third point. In Euclidean space the divergence is linear in $r$,
while in hyperbolic and relatively hyperbolic spaces it is exponential in $r$.

Dani and Thomas [13] gave a construction of RACGs with each possible degree of
polynomial divergence. On the other hand, combining work of
Behrstock–Hagen–Sisto [7] and Levcovitz [26] it follows that anytime a RACG is
not relatively hyperbolic, then its divergence is polynomial.

The degree of polynomial divergence of the Cayley graph of a group can be
computed via a geometric invariant called _thickness_ 111In the cases of
linear and quadratic divergence the characterization is in terms of _strong
algebraic thickness_ , for higher orders this notion does not characterize
(see [25] for an obstruction), but a more flexible invariant called _strong
thickness_ does characterize., which in turn can be characterized in terms of
the combinatorics of the presentation graph by results of Behrstock, Hagen and
Sisto [7] and Levcovitz [25]. This combinatorial characterization results in a
notion of _graph theoretic thickness_ , which is how we shall define and apply
thickness in this paper (see Section 2.4 for the definition).

We investigate the order of thickness and divergence in the random RACG
$W_{\Gamma}$, $\Gamma\sim\mathcal{G}_{n,p}$, in the $p$–regime when
$W_{\Gamma}$ is a.a.s. not relatively hyperbolic. The problem of determining
the threshold for thickness and divergence of various orders was raised by
Behrstock, Hagen and Sisto in [7, Question 1]. In prior work, Behrstock,
Falgas–Ravry and Susse [6] established a sharp threshold for thickness of
order 1 and quadratic divergence.

Adapting the ideas and arguments of [6], we show that thickness of order $2$
and cubic divergence in random RACG occurs a.a.s. for $p=p(n)$ in some
interval of values of width $\Omega\left(1/\sqrt{n}\right)$ below the sharp
threshold for thickness of order $1$ and quadratic divergence.

######  Theorem 1.2.

There exists an absolute constant $c>0$ such that the following hold:

  1. (i)

for $p=p(n)$ satisfying $\frac{\sqrt{\sqrt{6}-2}-c}{\sqrt{n}}\leq p(n)\leq
1-\Omega(\frac{\log n}{n})$, a.a.s. the random graph
$\Gamma\sim\mathcal{G}_{n,p}$ is thick of order at most $2$;

  2. (ii)

for every fixed $\varepsilon>0$ and
$p=p(n)\in[\frac{\sqrt{\sqrt{6}-2}-c}{\sqrt{n}},\frac{\sqrt{\sqrt{6}-2}-\varepsilon}{\sqrt{n}}]$,
a.a.s. the random graph $\Gamma\sim\mathcal{G}_{n,p}$ is thick of order
exactly $2$, and the random group $W_{\Gamma}$ has cubic divergence.

As an immediate consequence of Theorem 1.2 and a result of Chawla, Choi, He
and Rafi [11, Proposition 1.1] (a result about RACGs which are thick of order
at least 2) we have the following:

######  Corollary 1.3.

There exists an absolute constant $c>0$ such that for any fixed $\varepsilon$
with $0<\varepsilon<c$ and
$p=p(n)\in[\frac{\sqrt{\sqrt{6}-2}-c}{\sqrt{n}},\frac{\sqrt{\sqrt{6}-2}-\varepsilon}{\sqrt{n}}]$,
a.a.s. the random graph $\Gamma\sim\mathcal{G}_{n,p}$ has the property that
the simple random walk on any Cayley graph of the right-angled Coxeter group
$W_{\Gamma}$ satisfies a central limit theorem and has a normal limit law.

A key ingredient in the proof of Theorem 1.1 is the following extremal result
on the minimum number of edges required for a graph to be thick (meaning thick
of some finite order), and which is of independent interest.

######  Theorem 1.4.

Let $\Gamma$ be an $m$–vertex graph which is thick. Then $|E(\Gamma)|\geq
2m-4$.

The lower bound in Theorem 1.4 is best possible, since, e.g., for all $m\geq
4$ the complete bipartite graph $K_{2,m-2}$ is thick of order $0$ and has
exactly $2m-4$ edges. There are however many other extremal examples: consider
the graph on $\\{1,2,\ldots,m\\}$ obtained by joining $i,j$ by an edge if and
only if $|\lceil i/2\rceil-\lceil j/2\rceil|=1$ (this graph can be visualized
as a ‘path of squares’, see Figure 1 for an example). Again, it is easy to
verify that this graph is thick of order $1$ and has exactly $2m-4$ edges.
Further, one can identify any pair of non-edges present in two extremal
configurations on $m_{1}$ and $m_{2}$ vertices to obtain a new extremal
configuration on $m_{1}+m_{2}-2$ vertices — see Figure 2 for an example. In
this way one can obtain a wide variety of extremal examples, presenting a
particular challenge in the proof of Theorem 1.4. A somewhat surprising
feature of our result is that the order of thickness of $\Gamma$ does not
change the minimum number of edges required: in general, the least price to
pay for thickness of order $0$ is not lower than the least price to pay for
thickness of higher orders.

Theorem 1.4, taken together with a result of Behrstock, Hagen and Sisto [7,
Theorem I] showing that a RACG is relatively hyperbolic if and only it is not
thick, immediately implies the following tight lower bound on the minimum
number of commutative relations needed in a RACG to prohibit relative
hyperbolicity.

######  Corollary 1.5.

Consider a graph $\Gamma$ which we take to be the presentation graph of a
right-angled Coxeter group $W_{\Gamma}$. If $|E(\Gamma)|<2|V(\Gamma)|-4,$ then
$W_{\Gamma}$ is relatively hyperbolic.

### Questions and conjectures

We believe the following sharpening of Theorem 1.1 might hold. We expect that
to prove such a result will require either an entirely new approach or a
substantial quantitative strengthening of our techniques:

######  Conjecture 1.6.

Let $\Gamma\sim\mathcal{G}_{n,p}$. Then the following hold:

  1. (i)

if $p=p(n)=o\left(\frac{1}{\sqrt{n}}\right)$, then a.a.s. the right-angled
Coxeter group $W_{\Gamma}$ is relatively hyperbolic;

  2. (ii)

if $p=p(n)=\Omega\left(\frac{1}{\sqrt{n}}\right)$, then a.a.s. the right-
angled Coxeter group $W_{\Gamma}$ is thick of order $O(1)$ and has polynomial
divergence.

A key difficulty presented by this conjecture is the question of whether or
not a random graph $\Gamma\sim\mathcal{G}_{n,p}$ with
$p=p(n)=o\left(\frac{1}{\sqrt{n}}\right)$ may have thickness of order $t=t(n)$
finite but tending to infinity as $n\rightarrow\infty$.

In an even more challenging direction, we believe that Theorem 1.2 can be
generalized, and that for any fixed $k\in\mathbb{Z}_{\geq 3}$ there exist
intervals of width $\Omega\left(1/\sqrt{n}\right)$ of values of $p(n)$ for
which $W_{\Gamma}$ a.a.s. exhibits degree $k$ polynomial divergence.
Accordingly, we make the following bold conjecture, strengthening Conjecture
1.6 part (ii):

######  Conjecture 1.7.

There exists an infinite strictly decreasing sequence of strictly positive
real numbers $(\lambda_{k})_{k\in\mathbb{N}}$

$\lambda_{1}=\sqrt{\sqrt{6}-2}>\lambda_{2}>\lambda_{3}>\cdots>\lambda_{k}>\ldots\,,$

such that for every $k\in\mathbb{N}$ and every $\varepsilon>0$ fixed, the
following hold:

  1. (i)

for $p=p(n)\leq\frac{\lambda_{k}-\varepsilon}{\sqrt{n}}$, a.a.s. the random
graph $\Gamma\sim\mathcal{G}_{n,p}$ is not thick of order at most $k$;

  2. (ii)

for $p=p(n)$ satisfying $\frac{\lambda_{k}+\varepsilon}{\sqrt{n}}\leq p(n)\leq
1-\Omega(\frac{\log n}{n})$, a.a.s. the random graph
$\Gamma\sim\mathcal{G}_{n,p}$ is thick of order at most $k$.

Showing the existence of such constants $\lambda_{k}$ (let alone determining
their values!) seems however an extremely difficult problem even in the case
$k=2$ (although Theorem 1.2 is evidence in this direction). Indeed, it is not
even clear what the right rate of decay for the sequence $\lambda_{k}$ should
be: does it tend to $0$, and if so at what speed? As discussed in Remark 2.9
the property of being thick of order $k$ is not monotonic, which is another
difficulty in approaching this conjecture.

Finally, as already discussed by Behrstock, Falgas–Ravry and Susse in [6], it
could be fruitful to investigate similar questions to the ones considered in
this paper when the presentation graph $\Gamma$ is taken from a different
random graph distribution than that given by the Erdős–Rényi model. Random
$d$-regular graphs or random graph models with clustering such as random
intersection graphs or random geometric graphs could be interesting models to
study in this way, as the typical geometric properties of the resulting RACG
may differ in novel ways from those established in this paper.

### Related results

The study of random Right-angled Coxeter groups and their geometric and
cohomological properties was initiated in papers of Charney and Farber [10],
Davis and Kahle [14] and Behrstock, Hagen and Sisto [7] amongst others.
Theorem 1.1 part (i) of this paper represents a dramatic improvement on [7,
Theorem III], where it was established that for $p(n)=o(n^{-5/6})$, a.a.s. the
random RACG $W_{\Gamma}$, $\Gamma\sim\mathcal{G}_{n,p}$, is relatively
hyperbolic: this represents significant progress towards the completion of a
systematic picture of the geometric properties of random RACG proposed in [7,
Figure 4].

Improving on the earlier work of [7], Behrstock, Falgas–Ravry, Hagen and Susse
[5] established a threshold result for thickness of order $1$ and quadratic
divergence of the random RACG $W_{\Gamma}$, $\Gamma\sim\mathcal{G}_{n,p}$
around $p=1/\sqrt{n}$. More precisely, they showed that for $p=p(n)\leq
1/\left(\log(n)\sqrt{n}\right)$, $W_{\Gamma}$ exhibits a.a.s. at least cubic
divergence, while for $p=p(n)\geq 5\sqrt{\log n}/\sqrt{n}$ it has a.a.s. at
most quadratic divergence. This result was later sharpened by Behrstock,
Falgas–Ravry and Susse, who determined in [6, Theorem 1.6] the precise
location of the transition between cubic and quadratic divergence with the
following result.

######  Theorem 1.8 (Behrstock, Falgas–Ravry and Susse).

Let $c>0$ be fixed, and let $\Gamma\sim\mathcal{G}_{n,p}$. The following hold:

  1. (i)

if $c<\sqrt{\sqrt{6}-2}$ and $p=p(n)\leq c/\sqrt{n}$, then a.a.s. $W_{\Gamma}$
is not algebraically thick of order $1$ and has at least cubic divergence;

  2. (ii)

if $c>\sqrt{\sqrt{6}-2}$ and $c/\sqrt{n}\leq p(n)$, then a.a.s. $W_{\Gamma}$
is algebraically thick of order at most $1$ and has at most quadratic
divergence. Moreover if there is some constant $\varepsilon>0$ such that
$p(n)\leq 1-(1+\varepsilon)\frac{\log n}{n}$ then in fact $W_{\Gamma}$ is
algebraically thick of order exactly $1$ and has quadratic divergence.

More recently, Susse [34] studied Morse subgroups and Morse boundaries of
random RACG. In forthcoming work [2], the authors of the present paper
establish a threshold for connectivity of the square graph of a random graph,
a result that settles a conjecture of Susse and has geometric applications to
the study of cubical coarse rigidity in random RACG.

Finally, it would be remiss of us to close this section without mentioning the
closely related topic of _clique percolation_ , which arises in the study of
random graphs. Clique percolation first appeared as a simple model for
community detection in a work of Derényi, Palla and Vicsek [15], and was then
extensively featured in the network science literature [27, 31, 35, 36]. In
$(k,\ell)$–clique percolation, given a graph $\Gamma$ one forms an auxiliary
graph $K_{k,\ell}(\Gamma)$ whose vertices are the $k$–cliques of $\Gamma$ and
whose edges are those pairs of $k$–cliques having $\ell$ vertices in common.
One of the main research questions in the area was to determine the threshold
$p$ for the emergence of a giant component in $K_{k,\ell}(\Gamma)$ when
$\Gamma\sim\mathcal{G}_{n,p}$ is an Erdős–Rényi random graph. This was
achieved in a landmark 2009 paper of Bollobás and Riordan [8], using highly
sophisticated branching process techniques that in turn underpinned the
arguments deployed by Behrstock, Falgas–Ravry and Susse to study square
percolation and determine the threshold for quadratic divergence in random
RACG in [6].

###  1.1 Organization of the paper

In Section 2 we summarize the graph theoretic and probabilistic notions we
shall use, as well as discuss divergence and a combinatorial description of
thickness that will play a key role in the proof of Theorem 1.4. We then prove
our extremal results Theorem 1.4 and Corollary 1.5 in Section 3, while Section
4 is devoted to proofs of Theorems 1.1 and 1.2.

##  2 Preliminaries

###  2.1 Graph theoretic notions and notation

We recall here some standard graph theoretic notions and notation that we will
use throughout the paper. We write $[n]:=\\{1,2,\ldots,n\\}$, and
$x_{1}x_{2}\ldots x_{r}$ to denote the $r$-set
$\\{x_{1},x_{2},\ldots,x_{r}\\}$. Given a set $S$, we let $S^{(r)}$ denote the
collection of all subsets of $S$ of size $r$.

A graph is a pair $\Gamma=(V,E)$, where $V=V(\Gamma)$ is a set of vertices and
$E=E(\Gamma)$ is a subset of $V^{(2)}$. All graphs considered in this paper
are thus simple graphs, with no loops or multiple edges. We use
$v(\Gamma):=|V(\Gamma)|$ and $e(\Gamma):=|E(\Gamma)|$ to denote respectively
the order and the size (i.e. the number of vertices and the number of edges)
of a graph. Two subgraphs $\Gamma$ and $\Gamma^{\prime}$ are isomorphic if
there exists a bijection from $V(\Gamma)$ to $V(\Gamma^{\prime})$ taking edges
to edges and non-edges to non-edges; we denote this fact by
$\Gamma\cong\Gamma^{\prime}$.

A subgraph of $\Gamma$ is a graph $\Gamma^{\prime}$ with
$V(\Gamma^{\prime})\subseteq V(\Gamma)$ and $E(\Gamma^{\prime})\subseteq
E(\Gamma)$. We say $\Gamma^{\prime}$ is the subgraph of $\Gamma$ induced by a
set of vertices $S$ if $\Gamma^{\prime}=(S,S^{(2)}\cap E(\Gamma))$, and denote
this fact by writing $\Gamma^{\prime}=\Gamma[S]$. The complement of $\Gamma$
is the graph $\overline{\Gamma}:=(V,V^{(2)}\setminus E)$. Given a vertex $x$
in $\Gamma$, we denote the set of its neighbors by $N_{\Gamma}(x):=\\{y\in
V(\Gamma):\ xy\in E(\Gamma)\\}$.

A path of length $\ell\geq 0$ in $\Gamma$ is a sequence of distinct vertices
$v_{0},v_{1},\ldots,v_{\ell}$ with $v_{i}v_{i+1}\in E(\Gamma)$ for all
$i\in[\ell-1]\cup\\{0\\}$. The vertices $v_{0}$ and $v_{\ell}$ are called the
endpoints of the path. Two vertices are said to be connected in $\Gamma$ if
they are the endpoints of some path of finite length. Being connected in
$\Gamma$ is an equivalence relation on the vertices of $\Gamma$, whose
equivalence classes form the connected components of $\Gamma$. If there is a
unique connected component, then the graph $\Gamma$ is said to be connected. A
minimally connected subgraph of a connected graph is called a spanning tree.
Two useful facts about trees we shall use in our argument are (i) that every
connected graph contains a spanning tree, and (ii) that the vertex set of a
tree can be ordered starting from any vertex $v$ as $v=v_{1}$, $v_{2}$,
$\ldots$, $v_{n}$ in such a way that for every $j>1$ the vertex $v_{j}$ sends
at least one edge into the set $\\{v_{i}:\ 1\leq i<j\\}$.

Finally, we denote by $K_{1,2}$ the _cherry_ , or induced path on three
vertices, $K_{1,2}:=([3],\\{12,23\\})$; we let $C_{4}$ denote the _square_ (or
_$4$ -cycle_), $C_{4}:=([4],\\{12,23,34,14\\})$; and we write $K_{m}$ for the
_clique_ (or _complete graph_)of order $m$, $K_{m}:=([m],[m]^{(2)})$.

###  2.2 Probabilistic notation and tools

We write $\mathbb{P}$ and $\mathbb{E}$ and $\mathrm{Var}$ for probability,
expectation and variance respectively. We say that a sequence of events
$\mathcal{E}=\mathcal{E}(n)$, $n\in\mathbb{N}$ holds _a.a.s._ (asymptotically
almost surely) if $\lim_{n\rightarrow\infty}\mathbb{P}(\mathcal{E}(n))=1$.
Throughout the paper we use standard Landau notation: for functions $f,g:\
\mathbb{N}\rightarrow\mathbb{R}$ we write $f=o(g)$ if
$\lim_{n\rightarrow\infty}f(n)/g(n)=0$, $f=O(G)$ if there exists a real
constant $C>0$ such that $\limsup_{n\rightarrow\infty}|f(n)/g(n)|\leq C$. We
further write $f=\omega(g)$ if $g=o(f)$ and $f=\Omega(g)$ if $g=O(f)$.

We shall make repeated use of Markov’s inequality: given a non-negative
integer-valued random variables $X$,
$\mathbb{P}(X>a)\leq\frac{1}{a+1}\mathbb{E}X$ for any integer $a\geq 0$.

###  2.3 Divergence

A useful object in geometry is the _divergence function_ of a geodesic space.
Roughly speaking, this function measures the length of a shortest path between
pairs of points at distance $r$ apart in the space when forced to avoid a ball
of radius $r$ around a third point. There are a number of different ways to
formalize this and it is proven in [18, Proposition 3.5] that the various
definitions in the literature carry the same information. For more background
on divergence, we refer the reader to, e.g., Behrstock and Druţu [3] or Druţu,
Mozes and Sapir [18].

A quasi-isometry preserves the divergence function up to affine functions.
Hence the _growth rate of the divergence function_ is a quasi-isometry
invariant and thus is the same for all Cayley graphs of a given finitely
generated group, independently of the choice of the generating set.
Accordingly, we will abuse language slightly and just say the divergence
function is linear, quadratic, polynomial, etc, when strictly speaking we are
talking about the growth rate of the divergence function.

###  2.4 Thickness and the square graph

An important role in this paper is played by a graph theoretic notion of
thickness. _Graph-theoretic thickness_ was introduced by Behrstock, Hagen and
Sisto in [7] as a combinatorial way of capturing a geometric/algebraic
property of groups called _algebraic thickness_.

This latter notion of thickness first appeared in the context of geometric
group theory in work of Behrstock, Druţu and Mosher [4]. Algebraic thickness
is defined inductively. Roughly speaking, the base level of this property
(algebraic thickness of order zero) holds in groups that geometrically look
like the direct product of two infinite groups. Higher levels of this property
hold for groups that are a union of subgroups, each of which look like direct
products and which can be chained together through infinite diameter
intersections. (When the chaining can be done in a nice group-theoretic way
this leads to algebraic thickness, in this paper, we only require adjacent
steps have infinite intersection, which corresponds to a more general
invariant called _thickness_.)

As we explain below, the graph theoretic thickness of a presentation graph
completely encodes the thickness of the associated right-angled Coxeter group.
Accordingly, throughout this paper, without creating any ambiguity, we thus
use the term ‘thickness’ to simultaneouly refer to both notions. We now
formally define thickness for graphs.

Given graphs $\Gamma_{1},\Gamma_{2}$, the _join_ of $\Gamma_{1}$ and
$\Gamma_{2}$ is the graph $\Gamma_{1}*\Gamma_{2}$ obtained by taking the
disjoint union of $\Gamma_{1}$ and $\Gamma_{2}$ and adding a complete
bipartite graph between them. In other words,
$V(\Gamma_{1}*\Gamma_{2}):=V(\Gamma_{1})\sqcup V(\Gamma_{2})$ and
$E(\Gamma_{1}*\Gamma_{2}):=E(\Gamma_{1})\cup
E(\Gamma_{2})\cup\\{\\{v_{1},v_{2}\\}:\ v_{1}\in V(\Gamma_{1}),v_{2}\in
V(\Gamma_{2})\\}$. Note that the RACG of a join of two graphs is the direct
product of the RACGs associated to the two factors of the join. So for example
the square $C_{4}$, which is the join of two non-edges, corresponds to the
direct product of two free groups of rank two on generators of order $2$.

With this in hand, we now give the base case of our inductive definition of
thickness of order zero in graphs. By [7, Proposition 2.11] this graph
theoretic notion corresponds to the associated RACG being algebraically thick
of order 0.

######  Definition 2.1 (Thickness of order $0$).

A graph $\Gamma$ is _thick of order $0$_ if there exists a partition
$V(\Gamma)=A\sqcup B$ of its vertex set for which neither $\Gamma[A]$ nor
$\Gamma[B]$ is a clique and such that $\Gamma=\Gamma[A]*\Gamma[B]$.

Identifying vertex sets in $\Gamma$ with the corresponding induced subgraphs,
we say that a subset $S\subseteq V(\Gamma)$ is _thick of order $0$_ if the
induced subgraph $\Gamma[S]$ is thick of order $0$. Further, we say that $S$
is a _maximal_ thick of order $0$ subset if for every $S^{\prime}$ with
$S\subsetneq S^{\prime}\subseteq V(\Gamma)$ we have that $S^{\prime}$ is not
thick of order $0$.

Thus a subset $S\subset V(\Gamma)$ is thick of order 0 if and only if there
exists a bipartition $S=A\sqcup B$ such that the associated sets
$S_{A}=A^{(2)}\cap E(\overline{\Gamma})$ and $S_{B}=B^{(2)}\cap
E(\overline{\Gamma})$ are both non-empty (ensuring $\Gamma[A]$, $\Gamma[B]$
are non-cliques) and $\Gamma[A\cup B]=\Gamma[A]*\Gamma[B]$. Further, $S$ is a
maximal thick of order $0$ subset if in addition for every such partition
$A\sqcup B$ and every $v\in V(\Gamma)\setminus S$, there is some $a\in A$ and
$b\in B$ where neither $av$ and $bv$ are edges of $\Gamma$.

To inductively define higher levels of thickness, we shall glue together
subsets which are thick of lower orders. Accordingly, we define the following,
which will form the base level for the inductive definition.

######  Definition 2.2 ($T_{0}$: the level $0$ subsets).

The _level $0$ subsets of $\Gamma$_, $T_{0}(\Gamma)$, will denote the
collection of sets $S\subseteq V(\Gamma)$ such that $S$ is a maximal thick of
order $0$ subset. We refer to elements of $T_{0}(\Gamma)$ as _level $0$
components_ of $\Gamma$.

Given $S\in T_{0}(\Gamma)$ it will often be convenient to consider the
associated set of non-edges $S^{(2)}\cap E(\overline{\Gamma})$. Note that
$T_{0}(\Gamma)$ is just a collection of sets and not a graph. Below we shall
construct a sequence of auxiliary graphs $T_{k}(\Gamma)$,
$k\in\mathbb{Z}_{\geq 1}$. Each of these graphs will have as its vertex set
the collection $E(\overline{\Gamma})$ of non-edges of $\Gamma$, with connected
components merging as we increase the value of $k$ according to specific
rules, which we specify below.

The first of these auxiliary graphs is known as the _square graph_ , as it
encodes the induced squares of $\Gamma$ and their pairwise interactions.

######  Definition 2.3 ($T_{1}$: the square graph).

Given a graph $\Gamma$, the _square graph of $\Gamma$_, denoted by
$T_{1}(\Gamma)$, is defined as follows. The vertex set of $T_{1}(\Gamma)$ is
the collection $E(\overline{\Gamma})$ of non-edges of $\Gamma$. The edges of
$T_{1}(\Gamma)$ consist of those pairs of non-edges $f,f^{\prime}\in
E(\overline{\Gamma})$ such that the $4$–set of vertices $f\cup f^{\prime}$
induces a copy of the _square_ $C_{4}$ in $\Gamma$.

We refer to connected components in $T_{1}(\Gamma)$ as square components, or
level $1$ components. Given such a level $1$ component $C$, we define its
support to be $\mathrm{supp}_{1}(C):=\bigcup_{f\in C}f$, the collection of
vertices in $V(\Gamma)$ belonging to some $f\in C$. Further, we define the
latch-set of $C$ to be the collection of pairs from $\mathrm{supp}_{1}(C)$
that are non-edges in $\Gamma$,
$\mathrm{latch}_{1}(C):=E(\overline{\Gamma})\cap\left(\mathrm{supp}_{1}(C)\right)^{(2)}$.

######  Remark 2.4.

An equivalent definition of the square graph of $\Gamma$ is to let
$T_{1}(\Gamma)$ be the graph on $E(\overline{\Gamma})$ obtained by replacing
each level $0$ component $S$ by a clique on $S^{(2)}\cap E(\overline{\Gamma})$
(and replacing multi-edges by single edges), whence the connection to
$T_{0}(\Gamma)$.

######  Remark 2.5.

For certain applications in geometric group theory, it is natural to work with
another auxiliary graph closely related to (but distinct from) the square
graph $T_{1}(\Gamma)$, namely the line graph of $T_{1}(\Gamma)$, denoted by
$S(\Gamma)$, see [5, 13]. This other graph (which in [5, 13] is referred to as
the square graph) has the induced squares of $\Gamma$ as its vertices, and as
its edges those pairs of induced squares having a diagonal in common.

The square graph given in Definition 2.3 was introduced by Behrstock,
Falgas–Ravry and Susse in [6] as a more natural object to study from a
combinatorial viewpoint. As noted in [6, Remark 1.2] the two non-equivalent
definitions of a square graph carry essentially the same information, so
working with one rather the other is primarily a question of which definition
is convenient for the application one has in mind.

The study of the properties of $S(\Gamma)$ and $T_{1}(\Gamma)$ when $\Gamma$
is a random graph is known as _square percolation_ , by analogy with the well-
studied _clique percolation_ model from network science mentioned in the
introduction.

Having defined the level $0$ subsets and the level $1$ graph, we will define
the level $k$ graphs inductively after first giving a preliminary definition.

######  Definition 2.6 (Suspension).

Given $f=\\{u_{1},u_{2}\\}\in E(\overline{\Gamma})$, we let
$\mathrm{susp}(f):=\\{v\in V(\Gamma):\ v\in N_{\Gamma}(u_{1})\cap
N_{\Gamma}(u_{2})\\}$ denote the collection of common neighbors of the
endpoints of $f$, or, equivalently, the collection of all vertices $v$ such
that the $3$–set of vertices $\\{v\\}\cup f$ induces a copy of the cherry
$K_{1,2}$ in $\Gamma$. We refer to $\mathrm{susp}(f)$ as the suspension based
at $f$.

Note that if a (sub)graph $\Gamma$ is a suspension then there exists a
partition $V(\Gamma)=A\sqcup B$ of its vertex set for which $|A|=2$,
$\Gamma[A]$ is a non-edge, and $\Gamma=\Gamma[A]*\Gamma[B]$. If additionally
$\Gamma[B]$ is a clique, then we call $\Gamma$ a _strip_ (sub)graph.

The level $k$ graph will be built by merging lower level components if they
have a non-edge of $\Gamma$ in common; more formally:

######  Definition 2.7 ($T_{k}$, $k\geq 2$: the level $k$ graph).

For $k\geq 1$, we define $T_{k+1}(\Gamma)$ as a graph on the vertex set
$E(\overline{\Gamma})$ (the non-edges of $\Gamma$) by joining $f_{1},f_{2}\in
E(\overline{\Gamma})$ by an edge if for $i\in\\{1,2\\}$ there exist level $k$
components $C_{1}$, $C_{2}$ such that $f_{i}\in\mathrm{latch}_{k}(C_{i})$ and
$\mathrm{latch}_{k}(C_{1})\cap\mathrm{latch}_{k}(C_{2})\neq\emptyset$.

Given a connected component $C$ in $T_{k+1}$, we define its support to be

$\mathrm{supp}_{k+1}(C):=\bigcup_{f\in C}f\cup\mathrm{susp}(f),$

i.e. the collection of vertices in $V(\Gamma)$ that either belong to a member
$f$ of $C$ or to a suspension based at some $f\in C$. Further, we define the
latch-set of $C$ to be
$\mathrm{latch}_{k+1}(C):=E(\overline{\Gamma})\cap\left(\mathrm{supp}_{k+1}(C)\right)^{(2)}$.

$K_{2,5}$A ‘path of squares’ Figure 1: examples of a thick of order $0$ graph
(left) and a thick of order $1$ graph (right). A thick union of $K_{2,5}$ and
a path of squares Figure 2: an example of a thick of order $2$ graph

######  Definition 2.8 (Thickness).

Given a collection of non-edges $C\subseteq E(\overline{\Gamma})$ that forms a
level $k$ connected component for some $k\geq 0$, we say that $C$ is a level
$k_{0}$ component if $k_{0}$ is the least integer $k\geq 0$ such that $C$
forms a connected component in $T_{k}$. We say that such a component has full
support if $\mathrm{supp}_{k_{0}}(C)=V(\Gamma)$ or, equivalently, if
$\mathrm{latch}_{k_{0}}(C)=E(\overline{\Gamma})$. If this occurs, we say that
the graph $\Gamma$ is _thick of order $k_{0}$_. More generally, we say that
$\Gamma$ is _thick_ if it is thick of some finite order.

######  Remark 2.9 (Non-monotonicity under the addition/removal of edges).

The thickness properties of the graphs $T_{k}(\Gamma)$ are _not_ monotone
under the addition of edges to $\Gamma$. Indeed, adding an edge to $\Gamma$
could potentially create some new induced squares in $\Gamma$ (and thus new
edges in $T_{1}(\Gamma)$) as well as destroy existing ones. As an example,
consider the complete bipartite graph $\Gamma=K_{2,n-2}$ with one part of size
$2$ and another of size $n-2$. This graph is clearly thick of order $0$.
However if we delete any edge from $\Gamma$, or if we add an edge inside the
part of size $2$, then $\Gamma$ ceases to be thick of any order.

The non-monotonicity of thickness under the addition or deletion of edges make
its study a delicate matter, and explains in particular why many results on
the geometric properties of random RACG feature both a lower and an upper
bound on the edge probability $p$ required for a certain property to hold
a.a.s..

To compute the order of thickness of RACGs, the following definition of
hypergraph index was introduced by Levcovitz in [25]. Levcovitz proved in [26,
Theorem A] that a graph $\Gamma$ has finite hypergraph index if and only if
the corresponding RACG $W_{\Gamma}$ is thick of order $k$; moreover, this
occurs if and only if the RACG $W_{\Gamma}$ has divergence which is polynomial
of degree $k+1$. This strengthens earlier partial results from [4, 13, 7, 5].

######  Definition 2.10 (Hypergraph index).

Let $\Gamma$ be a graph. Let $\Psi(\Gamma)$ denote the collection of subsets
of $V(\Gamma)$ that induce strip subgraphs in $\Gamma$. Let $\Lambda_{0}$ be
the (non-uniform) hypergraph whose vertex set is $V(\Gamma)$ and whose set of
hyperedges is $T_{0}(\Gamma)\cup\Psi(\Gamma)$.

For all integers $n\geq 0$, inductively define a hypergraph $\Lambda_{n+1}$ as
follows. Introduce an equivalence relation $\cong_{n}$ on pairs of hyperedges
of $\Lambda_{n}$ by setting $E\equiv_{n}E^{\prime}$ when there exists a finite
sequence of hyperedges $E=E_{1}$, $E_{2}$, $\ldots$, $E_{k}$,
$E_{k+1}=E^{\prime}$ such that for every $i\in[k]$ the subgraph of $\Gamma$
induced by $E_{i}\cap E_{i+1}$ contains a non-edge. The hypergraph
$\Lambda_{n+1}$ then has $V(\Gamma)$ as its vertex set, and a hyperedge
$\bigcup_{E\in C}E$ for each $\equiv_{n}$–equivalence class $C$.

If $T_{0}(\Gamma)\neq\emptyset$ we define the _hypergraph index_ of $\Gamma$
to be the smallest non-negative integer $n$ for which $\Lambda_{n}$ contains
$V(\Gamma)$ as a hyperedge. When no such $n$ exists or when
$T_{0}(\Gamma)=\emptyset$ we define the _hypergraph index_ of $\Gamma$ to be
$\infty$.

Our definition of higher order thickness for graphs is defined so that it
encodes this notion. Indeed, it is not hard to see that the hypergraph index
of Levcovitz coincides precisely with the order of thickness as defined in
Definition 2.8. Thus Levcovitz’s results imply the order of thickness of a
RACG $W_{\Gamma}$ coincides precisely with the order of graph theoretic
thickness of its presentation graph $\Gamma$, and the two notions can be
conflated in the context of RACGs.

##  3 An extremal result for thickness in graphs

We shall prove the following strengthening of Theorem 1.4 using an inductive
strategy. Recall that the union $\Gamma_{1}\cup\Gamma_{2}$ of the graphs
$\Gamma_{1}$ and $\Gamma_{2}$ is the graph $\Gamma$ with
$V(\Gamma)=V(\Gamma_{1})\cup V(\Gamma_{2})$ and $E(\Gamma)=E(\Gamma_{1})\cup
E(\Gamma_{2})$.

######  Theorem 3.1.

Let $k\in\mathbb{Z}_{\geq 0}$. Let $\Gamma_{1}=(V_{1},E_{1})$ be a graph, and
let $\Gamma_{2}=(V_{2},E_{2})$ be either a copy of the cherry $K_{1,2}$ or a
thick of order at most $k$ graph. Set $I:=V_{1}\cap V_{2}$, and suppose that
$\Gamma_{2}[I]$ is not a clique of order at most $2$. Then

$\displaystyle e(\Gamma_{1}\cup\Gamma_{2})\geq e(\Gamma_{1})+2|V_{2}\setminus
V_{1}|.$ (3.1)

In particular if $\Gamma$ is thick of order at most $k+1$, then $e(\Gamma)\geq
2v(\Gamma)-4$.

######  Remark 3.2.

If $\Gamma_{2}\cong K_{1,2}$, then (3.1) is easily seen to hold: if
$\Gamma_{2}[I]$ is a non-clique, then it must either be the entirety of
$\Gamma_{2}$, or it must consist of the unique non-edge in $\Gamma_{2}$, and
in both cases the claimed upper bound holds. Thus the content of Theorem 3.1
lies in the case where $\Gamma_{2}$ is thick of order at most $k$; the
formulation including the cherry as a special case is nonetheless useful as it
will make the formulation of our inductive argument easier.

Our proof of Theorem 3.1 follows an inductive strategy that relies on the
following characterization of thick of order $k+1$ graphs.

######  Proposition 3.3.

Let $\Gamma$ be a thick of order $k+1$ graph, for some $k\geq 0$. Then for
some $T>0$, there exists a collection of induced subgraphs of $\Gamma$,
$\Gamma_{i}=(V_{i},E_{i})$ for $i\in[T]$, and a tree $\mathcal{T}$ on the
vertex set $[T]$ such that:

  1. (a)

for every $i\in[T]$, $\Gamma_{i}$ is a copy of the cherry $K_{1,2}$ or is
thick of order at most $k$;

  2. (b)

for every $ij\in E(\mathcal{T})$, the induced subgraph $\Gamma[V_{i}\cap
V_{j}]$ is not complete;

  3. (c)

$\bigcup_{i=1}^{T}V_{i}=V$.

###### Proof.

Follows immediately from the combinatorial characterization of thickness in
right-angled Coxeter groups given in [7, Theorem II] which implies that any
thick graph gives a connected graph whose vertices are associated to full
induced subgraphs which are thick of lower order and which are connected by an
edge if the associated graphs overlap in a non-clique. The result then follows
from the fact that every connected graph contains a spanning tree as a
subgraph. ∎

######  Proposition 3.4.

Let $k\in\mathbb{Z}_{\geq 0}$. Suppose that every thick of order at most $k$
graph $\Gamma$ satisfies $e(\Gamma)\geq 2v(\Gamma)-4$ and that in addition
(3.1) holds for all graphs $\Gamma_{1}$ and all thick of order at most $k$
graphs $\Gamma_{2}$. Then every graph $\Gamma^{\prime}$ that is thick of order
at most $k+1$ satisfies $e(\Gamma^{\prime})\geq 2v(\Gamma^{\prime})-4$.

###### Proof.

Let $\Gamma^{\prime}$ be a thick of order at most $k+1$ graph, and let
$\Gamma^{\prime}_{i}=(V_{i},E_{i})$, $i\in[T]$ be the collection of induced
thick of order at most $k$ subgraphs of $\Gamma^{\prime}$ whose existence is
guaranteed by Proposition 3.3. Since $\mathcal{T}$ is a tree, we can relabel
the indices of the $\Gamma^{\prime}_{i}$ so that for every $j>1$ there exists
$i\in[j-1]$ with $ij\in E(\mathcal{T})$.

By our assumption on graphs which are thick of order at most $k$, we have
$e(\Gamma^{\prime}_{1})\geq 2|V_{1}|-4$. Now for each $j>1$, there exists
$i\in[j-1]$ such that $ij\in E(\mathcal{T})$ and hence (by Proposition
3.3.(b)) $\Gamma^{\prime}[V_{i}\cap V_{j}]$ is non-complete. Since
$\Gamma^{\prime}_{j}$ is thick of order at most $k$ or a copy of the cherry
$K_{1,2}$, our assumption allows us to apply (3.1), which yields:

$\displaystyle
e\left(\left(\bigcup_{j^{\prime}<j}\Gamma^{\prime}_{j^{\prime}}\right)\cup\Gamma^{\prime}_{j}\right)\geq
e\left(\bigcup_{j^{\prime}<j}\Gamma^{\prime}_{j^{\prime}}\right)+2\left|V_{j}\setminus\left(\bigcup_{j^{\prime}<j}V_{j^{\prime}}\right)\right|.$

Iterating $T-1$ times, we get the desired bound on $e(\Gamma^{\prime})$:

$\displaystyle e(\Gamma^{\prime})$ $\displaystyle\geq
e\left(\bigcup_{j=1}^{T}\Gamma^{\prime}_{i}\right)\geq
2|V_{1}|-4+\sum_{j>1}2\left|V_{j}\setminus\left(\bigcup_{j^{\prime}<j}V_{j^{\prime}}\right)\right|=2\left|\bigcup_{j=1}^{T}V_{i}\right|-4=2v(\Gamma^{\prime})-4,$

where the last equality follows from Proposition 3.3.(c). ∎

Thus armed, we begin our proof of Theorem 3.1 by proving the base case $k=0$.

######  Proposition 3.5.

Let $\Gamma$ be thick of order $0$, and let $V(\Gamma)=A\sqcup B$ be a
partition of its vertex-set such that neither of $\Gamma[A]$ nor $\Gamma[B]$
is a clique and $\Gamma=\Gamma[A]*\Gamma[B]$. Setting $a:=|A|$ and
$m:=v(\Gamma)$, we have

$e(\Gamma)\geq a(m-a)\geq 2(m-2)=2m-4.$

###### Proof.

As neither of $\Gamma[A]$ and $\Gamma[B]$ is a clique, we have $2\leq a\leq
m-2$. Now clearly $e(\Gamma)\geq|A|\cdot|B|=a(m-a)$, which for $a\in[2,m-2]$
is at least $2(m-2)$. ∎

######  Proposition 3.6.

The statement of Theorem 3.1 holds for $k=0$.

###### Proof.

We have already established in Proposition 3.5 that a thick of order 0 graph
on $m$ vertices must have at least $2m-4$ edges. By Proposition 3.4, it is
thus enough to establish (3.1) for $k=0$. Further, by Remark 3.2 we need not
consider the case where $\Gamma_{2}$ is a cherry.

Let $\Gamma_{1}=(V_{1},E_{1})$ be a graph, and let $\Gamma_{2}=(V_{2},E_{2})$
be a thick of order $0$ graph. Set $I:=V_{1}\cap V_{2}$, and suppose this is a
non-empty subset of $V_{2}$. If $V_{2}\subseteq V_{1}$, then (3.1) holds
trivially. We may thus assume $V_{2}\setminus V_{1}$ is non-empty. Since
$\Gamma_{2}$ is thick of order zero it admits a partition
$V(\Gamma_{2})=A\sqcup B$ where $\Gamma_{2}[A]$ and $\Gamma_{2}[B]$ are both
non-complete and $\Gamma_{2}=\Gamma_{2}[A]*\Gamma_{2}[B]$. Denote $a:=|A|$,
$b:=|B|$, $x:=|A\cap I|$ and $y:=|B\cap I|$. Assume without loss of generality
that $x\leq y$.

Then we have the following key inequality:

$\displaystyle e(\Gamma_{1}\cup\Gamma_{2})-e(\Gamma_{1})-2|V_{2}\setminus
V_{1}|$ $\displaystyle\geq|B\setminus I|\left(|A|-2\right)+|A\setminus
I|\left(|B\cap I|-2\right)$ $\displaystyle=(b-y)(a-2)+(a-x)(y-2).$ (3.2)

To see why this inequality holds note: every vertex in $A$ sends edges to
every vertex in $B\setminus I$, giving us a first set of $|B\setminus
I|\cdot|A|$ edges; that every vertex in $B\cap I$ sends edges to every vertex
in $A\setminus I$, giving us a second set of $|A\setminus I|\cdot|B\cap I|$
edges disjoint from the first; and, that none of the edges in these two sets
belong to $\Gamma_{1}$ since all of them are incident to a vertex of $(A\sqcup
B)\setminus I=V(\Gamma_{2})\setminus V(\Gamma_{1})$.

To conclude the proof, it suffices to show that either $\Gamma_{2}[I]\cong
K_{\epsilon}$ for some $\epsilon\in\\{1,2\\}$ or that the expression on the
right hand side of (3.2) is non-negative. By thickness of order $0$, we know
that $a=|A|$ and $b=|B|$ are both at least $2$, and we also have $a\geq x$ and
$b\geq y$. In particular the first term in (3.2) above is always non-negative.

Consider now the second term. We have $2y\geq x+y=|I|>0$, whence $y>0$. If
$y=1$ and $x=0$, then $\Gamma_{2}[I]\cong K_{1}$ and we are done. Similarly if
$y=1$ and $x=1$, then $\Gamma_{2}[I]\cong K_{2}$ (since $\Gamma_{2}$ contains
as a subgraph the complete bipartite graph on the bipartition $A\sqcup B$) and
we are done. Finally if $y\geq 2$, then $(b-y)(a-2)+(a-x)(y-2)\geq 0$, as
desired. The proposition follows. ∎

###### Proof of Theorem 3.1.

We perform induction on $k$. We established the base case $k=0$ in Proposition
3.6. For the inductive step, assume we have proved the theorem for all $k\leq
K$, for some $K\geq 0$. By Proposition 3.4, it suffices then to show (3.1)
holds for $k=K+1$.

Let $\Gamma_{1}=(V_{1},E_{1})$ be an arbitrary graph, and let
$\Gamma_{2}=(V_{2},E_{2})$ be a thick of order $K+1$ graph. Set $I=V_{1}\cap
V_{2}$, and suppose this is a non-empty subset of $V_{2}$ with
$\Gamma_{2}[I]\not\cong K_{1}$, $K_{2}$. Note first of all that if
$|V_{2}\setminus V_{1}|=0$, then (3.1) holds trivially. We may thus assume
that $V_{2}\setminus V_{1}$ is non-empty.

Applying Proposition 3.3 to $\Gamma_{2}$, provides a collection of induced
subgraphs $\Gamma_{2,i}=(V_{2,i},E_{2,i})$, $i\in[T]$, of our graph
$\Gamma_{2}$, each of which is either a $K_{1,2}$ or thick of order at most
$K$, together with a tree $\mathcal{T}$ on $[T]$ satisfying properties (a)—(c)
from the statement of Proposition 3.3. Here we must consider two cases.

Case 1: suppose first of all that there is some $i_{0}$ such that

$\displaystyle e(\Gamma_{1}\cup\Gamma_{2,i_{0}})\geq
e(\Gamma_{1})+2|V_{2,i_{0}}\setminus V_{1}|.$ (3.3)

Reordering the indices of the $\Gamma_{2,i}$ as necessary, we may assume that
$i_{0}=1$ and that for every $j>1$ there exists $i\in[j-1]$ with $ij\in
E(\mathcal{T})$ (the existence of such an ordering is implied by the fact that
$\mathcal{T}$ is a tree), which in turn implies $\Gamma_{2}[V_{2,i}\cap
V_{2,j}]$ is non-complete (by property (b)). In particular, we must have that
$\Gamma_{2}\left[\left(V_{1}\cup\bigcup_{i<j}V_{2,i}\right)\cap
V_{2,j}\right]$ is a graph on at least two vertices not isomorphic to $K_{1}$
or $K_{2}$. Applying our inductive hypothesis $T-1$ times and appealing to
(3.3), we conclude that

$\displaystyle e\left(\Gamma_{1}\cup\Gamma_{2}\right)\geq
e\left(\Gamma_{1}\cup\left(\bigcup_{j}\Gamma_{2,j}\right)\right)$
$\displaystyle\geq
e\left(\Gamma_{1}\cup\Gamma_{2,1}\right)+\sum_{j>1}2\left|V_{2,j}\setminus\left(V_{1}\cup\left(\bigcup_{j^{\prime}<j}V_{2,j^{\prime}}\right)\right)\right|$
$\displaystyle\geq e(\Gamma_{1})+2\left|\bigcup_{j\geq 1}V_{2,j}\setminus
V_{1}\right|=e(\Gamma_{1})+2|V_{2}\setminus V_{1}|,$

and (3.1) holds as required.

Case 2: suppose that (3.3) does not hold for any $i_{0}\in[T]$. By our
inductive hypothesis this implies the following:

$\displaystyle(\star)$ $\displaystyle\textrm{for every }i\in[T]\textrm{,
}\Gamma_{2}[V_{1}\cap V_{2,i}]\textrm{ is a clique on at most two vertices}$

By property (c), there exists some $i_{0}$ such that $V_{2,i_{0}}\cap V_{1}$
is a non-empty subset of $I=V_{1}\cap V_{2}$. Reordering the indices of the
$\Gamma_{2,i}$ as necessary, we may assume that $i_{0}=1$, that $|V_{1}\cap
V_{2,1}|\geq|V_{1}\cap V_{2,i}|$ for all $i\in[T]$, and that for every $j>1$
there exists $i\in[j-1]$ with $ij\in E(\mathcal{T})$.

Now $\Gamma_{2}[V_{2,1}\cap V_{1}]=\Gamma_{2,1}[V_{2,1}\cap V_{1}]$, which by
$(\star)$ above is a clique on at least one and at most two vertices. Since
$\Gamma_{2}[V_{2}\cap V_{1}]$ is not a clique on at most two vertices, it
follows by property (c) again that there is some $j>1$ such that
$\left(V_{2,j}\cap V_{1}\right)\setminus\left(V_{2,1}\cap V_{1}\right)$ is
non-empty. Let $j_{0}$ be the least such $j$.

Consider now the graph $\Gamma_{2,[j_{0}]}=\bigcup_{i=1}^{j_{0}}\Gamma_{2,i}$,
and write $V_{2,[j_{0}]}:=\bigcup_{i=1}^{j_{0}}V_{2,i}$ for its vertex set.
Since for every $j>1$ there exists $i\in[j-1]$ with $ij\in E(\mathcal{T})$, it
follows from property (b) and the definition of thickness that
$\Gamma_{2,[j_{0}]}$ is thick of order at most $K+1$. By the ‘in particular’
part of our inductive hypothesis, we have

$\displaystyle E(\Gamma_{2,[j_{0}]})\geq 2\left|V_{2,[j_{0}]}\right|-4.$ (3.4)

Set $I_{0}:=V_{1}\cap V_{2,1}$ and $I_{1}:=V_{1}\cap V_{2,j_{0}}$, so that
$V_{1}\cap V_{2,[j_{0}]}=I_{0}\cup I_{1}$ by the minimality of $j_{0}$.
Further we have $I_{0}\setminus I_{1}$ and $I_{1}\setminus I_{0}$ both non-
empty — indeed, the latter follows by definition of $j_{0}$, and the former
from the maximality of $|V_{1}\cap V_{2,i}|$.

Since the elements of $I_{1}\setminus I_{0}$ do not appear in any $V_{2,i}$
with $i\in[j_{0}-1]$, and since the elements of $I_{0}\setminus I_{1}$ do not
belong to $V_{2,j_{0}}$ it follows that there is no edge from $I_{1}\setminus
I_{0}$ to $I_{0}\setminus I_{1}$ in $\Gamma_{2,[j_{0}]}$. By the inclusion-
exclusion principle and inequality (3.4), we have

$\displaystyle e(\Gamma_{1}\cup\Gamma_{2,[j_{0}]})$ $\displaystyle\geq
e(\Gamma_{1})+E(\Gamma_{2,[j_{0}]})-e\left(\Gamma_{2,[j_{0}]}[I_{0}\cup
I_{1}]\right)$ $\displaystyle\geq
e(\Gamma_{1})+2\left|V_{2,[j_{0}]}\right|-4-e\left(\Gamma_{2,[j_{0}]}[I_{0}\cup
I_{1}]\right)$ $\displaystyle\geq
e(\Gamma_{1})+2\left|V_{2,[j_{0}]}\right|-4-\binom{|I_{0}\cup
I_{1}|}{2}+|I_{0}\setminus I_{1}|\cdot|I_{1}\setminus I_{0}|.$ (3.5)

######  Claim 3.7.

$2|V_{2,[j_{0}]}|-4-\binom{|I_{0}\cup I_{1}|}{2}+|I_{0}\setminus
I_{1}|\cdot|I_{1}\setminus I_{0}|\geq 2|V_{2,[j_{0}]}\setminus V_{1}|$.

###### Proof.

Set $t:=|I_{0}\cup I_{1}|$ and $N:=|V_{2,[j_{0}]}|$, so that
$|V_{2,[j_{0}]}\setminus V_{1}|=N-t$.

Since $I_{0}$ and $I_{1}$ have size at least $1$ and at most $2$ (by
$(\star)$), and since $I_{0}\Delta I_{1}\neq\emptyset$ we have $2\leq t\leq
4$. Furthermore, $t=4$ is possible if and only $I_{0}$ and $I_{1}$ are
disjoint sets of size two.

If $2\leq t\leq 3$, then we have

$\displaystyle 2|V_{2,[j_{0}]}|-4-\binom{|I_{0}\cup I_{1}|}{2}+|I_{0}\setminus
I_{1}|\cdot|I_{1}\setminus I_{0}|\geq
2N-4-\binom{t}{2}+1=2(N-t)-\frac{(t-2)(t-3)}{2},$

which is equal to $2(N-t)$ as desired. On the other hand if $t=4$, then we
have

$\displaystyle 2|V_{2,[j_{0}]}|-4-\binom{|I_{0}\cup I_{1}|}{2}+|I_{0}\setminus
I_{1}|\cdot|I_{1}\setminus I_{0}|=2N-4-\binom{4}{2}+4=2(N-4)+2>2(N-4),$

as required. The claim follows. ∎

Combining Inequality (3.5) and Claim 3.7, we deduce that

$\displaystyle e(\Gamma_{1}\cup\Gamma_{2,[j_{0}]})\geq
e(\Gamma_{1})+2|V_{2,[j_{0}]}\setminus V_{1}|.$ (3.6)

We can now conclude the proof of this case much as we did in Case 1: for every
$j>j_{0}$ there exists $i\in[j-1]$ with $ij\in E(\mathcal{T})$, which in turn
implies $\Gamma_{2}[V_{2,i}\cap V_{2,j}]$ is non-complete. In particular, we
must have that $\Gamma_{2}\left[\left(V_{1}\cup\bigcup_{i<j}V_{2,i}\right)\cap
V_{2,j}\right]$ is a graph on at least two vertices not isomorphic to $K_{1}$
or $K_{2}$. Applying our inductive hypothesis $T-j_{0}$ times and appealing to
(3.6), we conclude that

$\displaystyle e\left(\Gamma_{1}\cup\Gamma_{2}\right)\geq
e\left(\Gamma_{1}\cup\left(\bigcup_{j}\Gamma_{2,j}\right)\right)$
$\displaystyle\geq
e\left(\Gamma_{1}\cup\Gamma_{2,[j_{0}]}\right)+\sum_{j>j_{0}}2\left|V_{2,j}\setminus\left(V_{1}\cup\left(\bigcup_{j^{\prime}<j}V_{2,j^{\prime}}\right)\right)\right|$
$\displaystyle\geq e(\Gamma_{1})+2\left|\bigcup_{j\geq 1}V_{2,j}\setminus
V_{1}\right|=e(\Gamma_{1})+2|V_{2}\setminus V_{1}|,$

and (3.1) holds as required.

∎

##  4 Thresholds in random right-angled Coxeter groups

###  4.1 Relative hyperbolicity: proof of Theorem 1.1

The key novelty in this paper is in Theorem 1.1 part (i) and its proof, which
we shall now give. By results of Behrstock Hagen and Sisto [7] and Levcovitz
[25] discussed in the introduction, a RACG $W_{\Gamma}$ is relatively
hyperbolic if and only if its presentation graph $\Gamma$ fails to be thick.
Thus part (i) of Theorem 1.1 is implied by the following stronger theorem
giving upper bounds on the order of thick components in
$\Gamma\sim\mathcal{G}_{n,p}$.

######  Theorem 4.1.

Let $p=p(n)\leq\frac{1}{4\sqrt{n\log n}}$ and $\Gamma\sim\mathcal{G}(n,p)$.
Then a.a.s. for every $k\in\mathbb{N}$, every component in $T_{k}(\Gamma)$ has
support of size at most $\log n$. In particular, $\Gamma$ is a.a.s. not thick
of order $k$.

We prove Theorem 4.1 in an inductive fashion by combining our extremal result,
Theorem 1.4, with the following simple result about random graphs.

######  Proposition 4.2.

Let $p=p(n)\leq\frac{1}{4\sqrt{n\log n}}$ and $\Gamma\sim\mathcal{G}_{n,p}$.
Then a.a.s. for every $m\in[\log n,2\log n]$, every $m$–vertex subset of
$\Gamma$ supports at most $2m-5$ edges.

###### Proof.

Let $X_{m}$ denote the number of $m$–vertex subsets in $\Gamma$ supporting at
least $2m-4$ edges. Set $X:=\sum_{m\in[\log n,2\log n]}X_{m}$. Applying the
inequalities $\binom{N}{r}\leq\left(\frac{eN}{r}\right)^{r}$ and
$2m-4\geq\frac{2e}{3}m$ for $m\geq 7$, we have that for all $n\geq e^{7}$,

$\displaystyle\mathbb{E}(X)$ $\displaystyle=\sum_{m=\lceil\log
n\rceil}^{\lfloor 2\log n\rfloor}X_{m}\leq\sum_{m=\lceil\log n\rceil}^{\lfloor
2\log
n\rfloor}\binom{n}{m}\binom{\binom{m}{2}}{2m-4}p^{2m-4}\leq\sum_{m=\lceil\log
n\rceil}^{\lfloor 2\log
n\rfloor}\left(\frac{ne}{m}\right)^{m}\left(\frac{3mp}{4}\right)^{2m-4}$
$\displaystyle\leq\sum_{m=\lceil\log n\rceil}^{\lfloor 2\log
n\rfloor}\left(\frac{9em}{256\log n}\right)^{m}\left(\frac{16n\log
n}{m^{2}}\right)^{2}=O\left(\frac{1}{\log n}\right).$

where in the last inequality we used the fact that the function

$x\mapsto x\log\left(\frac{256}{9ex}\right)=x\left(8\log(2)-2\log(3)-1-\log
x\right)$

is strictly greater than $2$ in the interval $x\in[1,2]$. It follows from
Markov’s inequality that a.a.s. $X=0$ and thus $\Gamma$ contains no $m$–vertex
subset supporting more than $2m-5$ edges for any $m\in[\log n,2\log n]$, as
claimed. ∎

###### Proof of Theorem 4.1.

Let $\mathcal{E}$ denote the event that for every $m\in[\log n,2\log n]$,
every $m$–set of vertices in $\Gamma$ supports at most $2m-5$ edges. By
Proposition 4.2, $\mathcal{E}$ occurs a.a.s., so it is enough to show the
conclusions of the theorem hold conditional on $\mathcal{E}$.

Suppose therefore that $\mathcal{E}$ occurs. We shall then prove by induction
on $k\geq 0$ that every component of $T_{k}(\Gamma)$ has support of size at
most $\log n$ (which implies both parts of Theorem 4.1).

For the base case $k=0$, suppose that $\Gamma$ contains an induced thick of
order $0$ subgraph on more than $\log n$ vertices. Let $A\sqcup B$ be any
partition of this induced subgraph such that $\Gamma[A]$ and $\Gamma[B]$ are
both non-complete and $\Gamma[A\sqcup B]=\Gamma[A]*\Gamma[B]$. Then, provided
$n$ is sufficiently large, there exists $A^{\prime}\subseteq A$ and
$B^{\prime}\subseteq B$ such that $\Gamma[A^{\prime}]$, $\Gamma[B^{\prime}]$
are both non-complete, $\Gamma[A^{\prime}\sqcup
B^{\prime}]=\Gamma[A^{\prime}]*\Gamma[B^{\prime}]$ and $\log
n\leq|A^{\prime}|+|B^{\prime}|\leq 2\log n$. In other words,
$\Gamma[A^{\prime}\sqcup B^{\prime}]$ is an induced thick of order $0$
subgraph of $\Gamma$ on $m$ vertices, for some $m$ with $\log n\leq m\leq
2\log n$. By Proposition 3.5, we have $e(\Gamma[A^{\prime}\sqcup
B^{\prime}])\geq 2m-4$, contradicting our assumption that $\mathcal{E}$ holds.
Thus $T_{0}(\Gamma)$ contains no level $0$ component supported on more than
$\log n$ vertices, as required.

For the inductive step, suppose a component $C$ in $T_{k+1}(\Gamma)$ has
support of size at least $\log n$. Observe that $C$ is obtained by
successively glueing together components or cherries
$C^{\prime}_{1},C^{\prime}_{2},\ldots$ from $T_{k}(\Gamma)$, each of which has
support of size at most $\log n$, and that the sequence of glueing can be done
in such a way that for every $i$, the subgraph of $\Gamma$ induced by the
union $U_{i}:=\bigcup_{j=1}^{i}\mathrm{supp}(C^{\prime}_{j})$ is thick of
order at most $k+1$.

In particular, we must have $|U_{i+1}|<|U_{i}|+\log n$ for every $i$, and
hence there must be a least $i_{0}$ such that $|U_{i_{0}}|>\log n$ satisfying
in addition $m:=|U_{i_{0}}|<2\log n$. Now the $m$–vertex induced subgraph
$\Gamma[U_{i_{0}}]$ is thick of order at most $k+1$, and hence by Theorem 1.4
must support at least $2m-4$ edges. Since $m\in[\log n,2\log n]$, this again
contradicts our assumption that $\mathcal{E}$ holds.

It follows by induction that, conditional on the a.a.s. event $\mathcal{E}$,
for all integers $k\geq 1$, $T_{0}(\Gamma)$ contains no component with support
of size greater than or equal to $\log n$. In particular $\Gamma$ is a.a.s.
not thick.∎

Part (ii) of Theorem 1.1 follows directly from Theorem 1.2 part (i), which is
proven below. (In fact, for $p\geq(\sqrt{\sqrt{6}-2}+\varepsilon)/\sqrt{n}$,
the statement of part (ii) already follows from Theorem 1.8 part (ii), so we
only appeal to Theorem 1.2 to remove the $\varepsilon$.)

###  4.2 Thickness of order two: proof of Theorem 1.2

To prove Theorem 1.2, we will employ a twist on the argument used in [6] to
prove Theorem 1.8. The crux of the proof of Theorem 1.8 lay in the analysis of
an exploration process for the square graph $T_{1}(\Gamma)$ and its comparison
with a supercritical Bienaymé–Galton–Watson branching process. We describe
that exploration process below and explain how a slight modification of it
allows us to explore thick of order $2$ rather than thick of order $1$
components, and to keep the associated branching process supercritical for $p$
a little below the threshold for thickness of order $1$.

The exploration process introduced in [6, Section 6.1] is as follows. Starting
at time $t=0$ from an induced square of $\Gamma\sim\mathcal{G}_{n,p}$ on
$\\{v_{1},v_{2},v_{3},v_{4}\\}$ with non-edges $v_{1}v_{3}$ and $v_{2}v_{4}$
one defines a set of discovered vertices
$D_{0}=\\{v_{1},v_{2},v_{3},v_{4}\\}$, an (ordered) set of active pairs
$A_{0}=\\{v_{1}v_{3},v_{2}v_{4}\\}$ and a set of reached pairs
$R_{0}=\emptyset$. At every time $t\geq 0$, $D_{t}$ is a subsets of
$V(\Gamma)$, while $A_{t}$ and $R_{t}$ are disjoint subsets of
$E(\overline{\Gamma})\cap(D_{t})^{(2)}$, i.e. $A_{t}$ and $R_{t}$ are disjoint
subsets of non-edges in the subgraph of $\Gamma$ induced by the set of
discovered vertices $D_{t}$.

At each time step $t\geq 0$ of our exploration process, we proceed as follows:

  1. 1.

If $|R_{t}|+|A_{t}|$ is large, meaning $|R_{t}|+|A_{t}|>(\log n)^{4}$, then we
terminate the process and output $\mathrm{LARGE\ STOP}$.

  2. 2.

If there are no active pairs left (i.e. if $A_{t}=\emptyset$), then we
terminate the process and output $\mathrm{EXTINCTION\ STOP}$.

  3. 3.

Otherwise, we select the first active pair $x_{1}y_{1}\in A_{t}$, which by
construction induces a $C_{4}$ in $\Gamma$ with some pair $F_{t}\in A_{t}\cup
R_{t}$. For every undiscovered vertex $z\in V(\Gamma)\setminus D_{t}$, we test
whether or not $z$ sends an edge of $\Gamma$ to both of $x_{1}$ and $y_{1}$;
in this way we form a set $Z_{t}:=\\{z\in V(\Gamma):\
\\{x_{1}z,y_{1}z\\}\subset E(\Gamma)\\}$.

Finally we update our triple $(D_{t},A_{t},R_{t})$ by setting
$D_{t+1}=D_{t}\cup Z_{t}$,
$A_{t+1}=\left(A_{t}\setminus\\{x_{1},y_{1}\\}\right)\cup\left((F_{t}\cup
Z_{t})^{(2)}\setminus E(\Gamma)\right)$ and
$R_{t+1}=R_{t}\cup\\{x_{1}y_{1}\\}$.

Note that our update rule under 3. above ensures $A_{t}\cup R_{t}$ is a
collection of non-edges of $\Gamma$ which lie in the same component of the
square graph $T_{1}(\Gamma)$ and in particular preserves the property that
every pair in $A_{t}$ induces a square with some pair $F_{t}\in D_{t}^{(2)}$.

The key result in [6, Section 6.2] is that for any $\varepsilon>0$ fixed and
any $\lambda=\lambda(n)$ satisfying
$\sqrt{\sqrt{6}-2}+\varepsilon\leq\lambda\leq 5\sqrt{\log n}$, for
$p=\lambda/\sqrt{n}$ the above exploration process is supercritical, and that
a.a.s. a strictly positive proportion of induced squares in $\Gamma$ are part
of large square components, in the sense that their non-edges are part of
components of size at least $(\log n)^{4}$ in $T_{1}(\Gamma)$; this is the
content of [6, Lemma 6.2].

Supercriticality for the process follows from the fact that as long as the
number of discovered vertices $D_{t}$ is small, the number $|A_{t+1}\setminus
A_{t}|$ of active pairs discovered at each time step of the process (i.e. the
offspring distribution) stochastically dominates a random variable
$X^{\prime}\sim\binom{Z^{\prime}+2}{2}-1$, where
$Z^{\prime}\sim\mathrm{Binom}(n-o(n),p^{2}-o(p^{2}))$. For
$p=\lambda/\sqrt{n}$ and $\lambda=\theta(1)$, we have
$\mathbb{E}X^{\prime}=\frac{\lambda^{4}}{2}+2\lambda^{2}+o(1)$, which for
fixed $\lambda>\sqrt{\sqrt{6}-2}$ is at least $1+\eta$ for some fixed
$\eta>0$. For such $\lambda$, we can thus apply standard results from
branching process theory to conclude that the extinction probability is at
most $1-\delta$, for some fixed $\delta>0$, i.e. that with probability bounded
away from zero our exploration process ends with a $\mathrm{LARGE\ STOP}$.

Having shown that a.a.s. a strictly positive proportion of squares lie in
large square components, it easily followed that a.a.s. a positive proportion
of non-edges of $\Gamma$ belong to large square-components of $T_{1}(\Gamma)$
(see [6, Corollary 6.3]). With this fact in hand, a.a.s. thickness of order
$1$ for $\Gamma$ was proved in [6, Section 6.3-6.5] via a somewhat elaborate
vertex sprinkling argument relying on Janson’s inequality and partition
arguments. That part of the proof, however, only required
$p(n)=\Omega(1/\sqrt{n})$ together with the aforementioned fact that a.a.s.
$\Omega(n^{2})$ non-edges of $\Gamma$ belong to square components of order at
least $(\log n)^{4}$ in $T_{1}(\Gamma)$.

To prove Theorem 1.2, it thus suffices to show that there exists some absolute
constant $c>0$ such that for $\sqrt{\sqrt{6}-2}-c\leq\lambda\leq 5\sqrt{\log
n}$, a.a.s. a strictly positive proportion of non-edges of $\Gamma$ lie in
thick of order $2$ components of size at least $(\log n)^{4}$. As we observe
below, this can be done with a modification of the exploration algorithm that
increases the expected number of offspring and thus allows the exploration
process to remain supercritical a little below $p=\sqrt{\sqrt{6}-2}/\sqrt{n}$.
As the technical modification of the analysis from [6] is fairly
straightforward, and yields an upper bound on the threshold for thickness of
order $2$ which we do not believe is optimal, we only sketch the argument and
leave the details to the reader.

Given an active pair $x_{1}y_{1}\in A_{t}$, observe that if there is a
quadruple of vertices $\\{x_{2},x_{3},y_{2},y_{3}\\}\subseteq D_{t}$ such that
setting $X=\\{x_{1},x_{2},x_{3}\\}$ and $Y=\\{y_{1},y_{2},y_{3}\\}$ we have
that the subgraph of $\Gamma$ induced by $X\sqcup Y$ is the complete bipartite
graph on $X\sqcup Y$ with the edge $x_{1}y_{1}$ removed, then the pairs
$x_{i}x_{j}$ and $y_{i}y_{j}$ all lie in the same component of $T_{2}(\Gamma)$
as $x_{1}y_{1}$ (since $\Gamma[X\sqcup Y]$ is thick of order $1$ and has
$x_{1}y_{1}$ as a member of its latch-set but not as the diagonal of an
induced square), and may thus be added to $A_{t+1}$ if we are looking to
explore $T_{2}(\Gamma)$ rather than $T_{1}(\Gamma)$. This leads us to make the
following modification of Step 3:

  1. $3^{\prime}$

Otherwise, we select the first active pair $x_{1}y_{1}\in A_{t}$, which by
construction induces a $C_{4}$ in $\Gamma$ with some pair $F_{t}\in A_{t}\cup
R_{t}$. For every undiscovered vertex $z\in V(\Gamma)\setminus D_{t}$, we test
whether or not $z$ sends an edge of $\Gamma$ to both $x_{1}$ and $y_{1}$; in
this way we form a set $Z_{t}:=\\{z\in V(\Gamma):\ \\{x_{1}z,y_{1}z\\}\subset
E(\Gamma)\\}$.

Next, for every pair of pairs $\\{x_{2}x_{3},y_{2}y_{3}\\}$ drawn from
$V(\Gamma)\setminus\left(D_{t}\cup Z_{t}\right)$, we test wether we have
$x_{i}y_{j}\in E(\Gamma)$ for all $(i,j)\neq(1,1)$ and
$x_{2}x_{3},y_{2}y_{3}^{\prime}\notin E(\Gamma)$ both holding; if this is the
case, we say $x_{2}x_{3}$ and $y_{2}y_{3}$ are bridge pairs, and we denote by
$B^{\prime}_{t}$ the collection of all such bridge pairs.

Finally we update our triple $(D_{t},A_{t},R_{t})$ by setting
$D_{t+1}=D_{t}\cup Z_{t}$,
$A_{t+1}=\left(A_{t}\setminus\\{x_{1},y_{1}\\}\right)\cup\left((F_{t}\cup
Z_{t})^{(2)}\setminus E(\Gamma)\right)\cup B^{\prime}_{t}$ and
$R_{t+1}=R_{t}\cup\\{x_{1}y_{1}\\}$.

The arguments of [6] are readily adapted to show that
$\mathbb{E}B^{\prime}_{t}\geq\frac{1}{2}\left(\binom{n-o(n)}{2}\right)^{2}p^{8}(1-p)^{6}$
and that as a result the expected number of offspring in our modified
exploration process when $p=\lambda/\sqrt{n}$ and $\lambda=\theta(1)$ is
$\frac{\lambda^{4}}{2}+2\lambda^{2}+\frac{\lambda^{8}}{8}+o(1)$. In
particular, there exist constants $c,\eta>0$ such that for
$\sqrt{\sqrt{6}-2}-c\leq\lambda\leq 2\sqrt{\sqrt{6}-2}$ the expected number of
offspring in our modified process is at least $1+\eta$, whereupon the rest of
the machinery from [6] can be deployed essentially without any further
alterations to ensure the a.a.s. existence of a strictly positive proportion
of non-edges in large components of $T_{2}(\Gamma)$, and, from there, a.a.s.
thickness of order $2$. Theorem 1.2 follows.

## Acknowledgements

The initial research that led to this paper was carried out when the first
author visited the second and third author in Umeå in January 2023 at the
occasion of the third Midwinter Meeting in Discrete Probability. The
hospitality of the Umeå mathematics department as well as the financial
support of the Simons Foundation which made this visit possible are gratefully
acknowledged. In addition the research of the first author was supported by
the Simons Foundation as a Simons Fellow while the research of the second and
third authors is supported by the Swedish Research Council grant VR
2021-03687.

## References

  * [1] G. Arzhantseva and A. Minasyan.  The SQ-universality and residual properties of relatively hyperbolic groups.  J. Algebra, 315(1):165–177, 2007.
  * [2] J. Behrstock, R. A. Çiçeksiz, V. Falgas-Ravry  Connectivity for square percolation and unique cubical coarse medians in random right-angled Coxeter groups.  In preparation.
  * [3] J. Behrstock and C. Druţu.  Divergence, thick groups, and short conjugators.  Illinois J. Math., 58(4):939–980, 2014.
  * [4] J. Behrstock, C. Druţu, and L. Mosher.  Thick metric spaces, relative hyperbolicity, and quasi-isometric rigidity.  Mathematische Annalen, 344(3):543–595, 2009.
  * [5] J. Behrstock, V. Falgas-Ravry, M.F. Hagen, and T. Susse.  Global structural properties of random graphs.  International Mathematics Research Notices, 2018(5):1411–1441, 2018\.
  * [6] J. Behrstock, V. Falgas-Ravry, and T. Susse.  Square percolation and the threshold for quadratic divergence in random right-angled Coxeter groups.  Random Structures & Algorithms, 60(4):594–630, 2022.
  * [7] J. Behrstock, M.F. Hagen, and A. Sisto.  Thickness, relative hyperbolicity, and randomness in Coxeter groups.  Algebr. Geom. Topol., 17(2):705–740, 2017.
  * [8] B. Bollobás and O. Riordan.  Clique percolation.  Random Structures Algorithms, 35(3):294–322, 2009.
  * [9] B.H. Bowditch.  Relatively hyperbolic groups.  Internat. J. Algebra Comput., 22(3):1250016, 66, 2012.
  * [10] R. Charney and M. Farber.  Random groups arising as graph products.  Alg. Geom. Topol., (12):979–996, 2012.
  * [11] K. Chawla, I. Choi, V. He, and K. Rafi.  Random walks on groups and superlinear divergent geodesics.  arXiv:2310.18506.
  * [12] F. Dahmani.  Les groupes relativement hyperboliques et leurs bords.  PhD thesis, Université de Strasbourg, 2003.  Available at `https://www-fourier.ujf-grenoble.fr/~dahmani/`.
  * [13] P. Dani and A. Thomas.  Divergence in right-angled Coxeter groups.  Trans. Amer. Math. Soc., 367(5):3549–3577, 2015.
  * [14] M.W. Davis and M. Kahle.  Random graph products of finite groups are rational duality groups.  J. Topol., 7(2):589–606, 2014.
  * [15] I. Derényi, G. Palla, and T. Vicsek.  Clique percolation in random networks.  Phys. Rev. Lett., 94:160202, Apr 2005.
  * [16] C. Druţu.  Relatively hyperbolic groups: geometry and quasi-isometric invariance.  Comment. Math. Helv., 84(3):503–546, 2009.
  * [17] C. Druţu and M.V Sapir.  Tree-graded spaces and asymptotic cones of groups.  Topology, 44(5):959–1058, 2005.  With an appendix by Denis Osin and Mark Sapir.
  * [18] C. Druţu, S. Mozes, and M.C. Sapir.  Divergence in lattices in semisimple Lie groups and graphs of groups.  Trans. Amer. Math. Soc., 362(5):2451–2505, 2010.
  * [19] C. Druţu and M.V. Sapir.  Groups acting on tree-graded spaces and splittings of relatively hyperbolic groups.  Adv. Math., 217(3):1313–1367, 2008.
  * [20] B. Farb.  Relatively hyperbolic groups.  Geom. Funct. Anal., 8(5):810–840, 1998.
  * [21] S.M. Gersten.  Quadratic divergence of geodesics in CAT(0)-spaces.  Geom. Funct. Anal., 1(4):37–51, 1994.
  * [22] S.M. Gersten.  Divergence in $3$-manifold groups.  Geom. Funct. Anal., 4(6):633–647, 1994.
  * [23] M. Gromov.  Hyperbolic groups.  In S. Gersten, editor, Essays in group theory, volume 8 of MSRI Publications. Springer, 1987.
  * [24] M. Gromov.  Asymptotic invariants of infinite groups, Geometric Group Theory, vol. 2 (Niblo, Roller, eds.).  LMS Lecture Notes Ser, 182, 1993.
  * [25] I. Levcovitz.  A quasi-isometry invariant and thickness bounds for right-angled Coxeter groups.  Groups Geom. Dyn., 13(1):349–378, 2019.
  * [26] I. Levcovitz.  Characterizing divergence and thickness in right-angled Coxeter groups.  J. Topol., 15(4):2143–2173, 2022.
  * [27] M. Li, Y. Deng, and B.-H. Wang.  Clique percolation in random graphs.  Phys. Rev. E (3), 92(4):042116–042122, 2015.
  * [28] Y. Ollivier.  Sharp phase transition theorems for hyperbolicity of random groups.  Geom. Funct. Anal., 3(14):595–679, 2004.
  * [29] A. Ol’shanskii.  Almost every group is hyperbolic.  Internat. J. Algebra Comput., 1(2):1–17, 1992.
  * [30] D.V. Osin.  Relatively hyperbolic groups: intrinsic geometry, algebraic properties, and algorithmic problems.  Mem. Amer. Math. Soc., 179(843):vi+100, 2006.
  * [31] G. Palla, I. Derényi, Illés Farkas, and T. Vicsek.  Uncovering the overlapping community structure of complex networks in nature and society.  Nature, 435:814–818, June 2005.
  * [32] A. Sisto.  On metric relative hyperbolicity.  Preprint, arXiv:math/1210.8081, 2012.
  * [33] A. Sisto.  Projections and relative hyperbolicity.  Enseign. Math., 59:165–181, 2013.
  * [34] T. Susse.  Morse subgroups and boundaries of random right-angled Coxeter groups.  Geometriae Dedicata, 217(2):15, 2023.
  * [35] B. Tóth, T. Vicsek, and G. Palla.  Overlapping modularity at the critical point of $k$-clique percolation.  J. Stat. Phys., 151(3-4):689–706, 2013.
  * [36] B. Wang, L. Cao, H. Suzuki, and K. Aihara.  Impacts of clustering on interacting epidemics.  J. Theoret. Biol., 304:121–130, 2012.
  * [37] A. Yaman.  A topological characterization of relatively hyperbolic groups.  J. Reine Angew. Math. (Crelle’s Journal), 566:41–89, 2004.


# Action Bar Adaptations for One-Handed Use of Smartphones

Siddharth Mehrotra, Saurav Das, and Sourabh Zanwar  RWTH Aachen
UniversityTemplergraben 55AachenNorth Rhine-WestphaliaGermany52062
<EMAIL_ADDRESS>
###### Abstract.

One-handed use of smartphones is a common scenario in daily life. However, use
of smartphones with thumb gives limited reachability to the complete screen.
This problem is more severe when targets are located at corners of the device
or far from the thumb’s reachable area. Adjusting screen size mitigates this
issue by making screen UI to be at the reach of the thumb. However, it does
not utilize available screen space. We propose UI adaptation for action bar to
address this. With our results, designed adaptations are faster for non-
dominant hand and provides significantly better grip stability for holding
smartphones. Intriguingly, users perceived our system as faster, more
comfortable and providing safer grip when compared with the existing placement
of action bar. We conclude our work with video analyses for grip patterns and
recommendations for UI designers.

UI adaptation; one-handed; reachability; smartphone

††conference: Current Topics in HCI - Project; July 10, 2019; Aachen, DE††ccs:
Human-centered computing User studies††ccs: Human-centered computing Graphical
user interfaces††ccs: Human-centered computing Interaction techniques

##  1\. Introduction

Figure 1. A user using the action bar on an Android phone with the GMail App.

Smartphone screens in today’s world have increased considerably in size.
Looking back at the rise of the smartphone era with Apple iPhone coming to the
market in 2007 with dimensions (115 x 61 x 11.6 mm) all the way to the latest
iPhone, iPhone XR with dimension (150.9 x 75.7 x 8.3 mm), we can already see
how the phones have become taller and thinner. Smartphones with bigger screens
are now popular owing to the fact that they are becoming one of the primary
multimedia content viewing devices in our everyday lives. With more screen
area displaying more content, problems such as reachability are becoming
predominant. The reachability issue occurs since most of the users use
smartphones in one-handed mode (Hoober, [n. d.]) rather than in the cradled or
two-handed modes in which reachability issues are far less. This choice of
holding the phone may be attributed to the fact that usually users are multi-
tasking and the other hand is being used to perform some low cognition task or
tasks involving only procedural knowledge. In one-handed mode the screen is
accessed by the thumb only and it’s range and flexibility is limited. Usually
users cope with this by tilting the device to bring the far screen corner
closer to the stretched thumb (Chang et al., 2015; Negulescu and McGrenere,
2015) but this technique has limited scope and also compromises the grip
stability.

Most common technique used by users to deal with reachability is to change the
gripping pattern in order to reach far targets. Also, with recent advancements
the phone layout can be changed to bring the top panel to the center of the
phone. However, we believe by doing this the benefits of a large screen is not
being fully utilized.

We propose UI Adaptation for smartphones in one-handed mode, a method in which
we address the issue of reachability of existing UI elements. We use the
Orientation information from the device to make changes in the UI to better
position elements across the screen. We use the UI element action bar because
it is one of most common UI element across all apps, offers change in grip for
one hand usage (because of it’s position) and it is essential for visually
challenged users as screen readers starts from action bars. We document time
taken, orientation angles, and our observations related to various grip
patterns & gripping strategies that users take to cope with reachability. We
conclude with recommendations for inclusion of our technique in Smartphone
Applications. In summary, this paper makes the following contributions:

  1. (1)

We compare 3 different adaptations of action bar based on existing UI element
for touchscreen mobile phones.

  2. (2)

a quantitative study examining the effect of different phone sizes and
interaction hand on UI adaptations.

  3. (3)

Empowering our results based on user’s Likert scale responses and video
analyses of the experiment to study the overall experience with the
adaptations.

##  2\. Related Works

There are variety of techniques in the commercial market for tackling
reachability in smartphones. With Apple’s iPhone users can turn on
Reachability to bring items at the top of the screen down to the lower half of
the screen111https://support.apple.com/guide/iphone/reachability-
iph66e10a71c/ios. With Motorola swipe to shrink screen mode, user can make
screen smaller for one-handed use 222https://motorola-global-
portal.custhelp.com. In addition, there are techniques to tweak the keyboard
layout for one-handed operation. The keyboard snaps to one side of the screen
and one can use the arrow button to switch sides333https://gizmodo.com/the-
essential-guide-to-using-your-oversized-phone-with-1830709197. However, re-
sizing the screen outcasts the benefit of the large screen smartphones (Kim et
al., 2012).

A good amount of literature already exists focusing on one-handed use of
devices (Girouard et al., 2015)(Huot and Lecolinet, 2006). Lehtovirta &
Oulasvirta has modelled the functional area of the thumb on mobile
touchscreens. Their model ensures that a user interface is suitable for
interaction with the thumb (Bergstrom-Lehtovirta and Oulasvirta, 2014). Chang
et. al in CHI’15 constructed a design space for one-handed targeting
interactions. They conducted an empirical experiment to discover usage
patterns of tilting devices toward user thumb for touch screen regions (Chang
et al., 2015). Hong and Lee introduced TouchShield which provides shortcuts to
frequently used commands via the thumb. The designed virtual control
(TouchShield) provides an area in which the thumb can pin the phone down in
order to provide a stable grip (Hong and Lee, 2013). Although these methods
tackles reachability issues and grip stability, they introduce new concepts
which needs to be adapted first as indirect inputs and requires additional use
of thumb’s press for hitting the target.

In another attempts to tackle reachability issue from existing UI perspective,
Alt & Buschek in CHI’17 proposed ProbUI, a model that automatically evaluate
user’s touch sequences. They intend to guess the behaviour and target of the
user based on machine learning probabilistic models (Buschek and Alt, 2017).
Karlson & Bederson introduced ThumbSpace and Shift —two software based
interaction techniques. ThumbSpace addresses distant objects while Shift
addresses small object occlusion. Their results supports better overall speed
and accuracy in hitting small targets when combining both the techniques
(Karlson and Bederson, 2008).

While such methods can be used to predict the user’s intention for button
press however the reachability issue is still an open question as generative
models have to surpass multiple UI elements before reaching targets on screen
corners. Using a similar approach, Alt et. al introduces trigger based dynamic
change in layout for rolling bar and floating menu button. Their results shows
that trigger based elements improve reachability on a large device, and can
reduce interaction time and device tilting (Buschek et al., 2017). Our
research contribution is different from these prior works in the form that
adapting existing UI element and measuring overall device orientation for
phone stability. We focus on re-orienting the device only when it is required
rather than based on triggers which is not ideal in real life context. In
addition, we include comparison across hand dominance for wider audience
reach.

##  3\. UI Adaptation Technique

The UI Adaptation technique in Smartphones is a technique which can mitigate
certain aspects of the reachability issue. Anchoring and Repositioning are
known methods used to handle application screens at different device
orientations. With UI Adaptation, the individual UI elements have a not-too-
strict layout. The UI elements can be categorically segregated according to
types, frequency or importance to the user at a particular context. For items
lying in the screen space out of the thumb’s reach, these adaptations will
rearrange the UI based on the reach-intent of the user.

The term reach-intent is defined as the intention of the user to click a
specific area of the Application while tilting the device in single handed
mode. Device Orientation coupled with categorization of UI elements on a
loosely based layout gives us a way to guess the UI element user wants to
access and make them more reachable.

##  4\. User Study

In order to understand whether UI adaptation is a useful technique, we wanted
to study the target selection speed and device orientation angles in the case
where regular UI elements are re-positioned. We took a common UI element, the
Action Bar and carried an User Study with 8 participants (5 males and 3
females, 21-29 years, M = 25.39, SD = 2.7). All our users were right-handed
with about 8-9 years of experience with smartphone interaction. The Action Bar
position was varied in 2 different ways in addition to the usual top position
(the control condition here). The Action Bar area was divided into 6 sub-areas
marked from 1-6. This was done to understand the difference in measurements
for the far and the near target areas. The buttons were all equally sized for
all the UI orientations. The sequence in which the buttons need to be pressed
came as an instruction message in the screen along with information about
which hand the user should use when clicking the button.

Figure 2. UI of our study prototype showing the baseline and adapted
positioning of the action bar. Left: UI with number 1 is the baseline ’top’
layout of the action bar. Right: UI with number 2 & 3 are adaptation ’left’
and ’right’ layout of the action bar.

The sequence was preset in the application by randomizing a number sequence
before. The participants were asked to select numbered buttons on the screen
according to the number shown on the instruction portion of the screen. This
had to be done for all 3 Action Bar placements and while using the dominant
and the non-dominant hand in turn. The participants were asked to always use
the device in one-handed mode, in portrait orientation and without supporting
their arm in any way while using the device.

We recorded the overall time taken by the users to hit the target once a
number corresponding to 6 sub-areas displayed at the center of the screen.
Once all 6 sub-areas were pressed the user was asked to click on ’next’ button
for another UI layout. The size of the buttons on sub-areas were kept similar
to actual guidelines by Android Community
444https://material.io/design/components/buttons.html. We also recorded the
overall orientation of the phone with respect to X, Y, Z directions. We used
the device’s geomagnetic field sensor in combination with the device’s
accelerometer to log those readings in Android Studio logs.

  1. (1)

For X Direction, Pitch is the angle between a plane parallel to the device’s
screen and a plane parallel to the ground. The range of values can be between
-180 degrees to +180 degrees.

  2. (2)

For Y Direction, Roll is the angle between a plane perpendicular to the
device’s screen and a plane. The range of values can be between -90 degrees to
+90 degrees.

  3. (3)

For Z Direction, Azimuth is the angle between the device’s current compass
direction and magnetic north. The range of values can be between 0 degrees to
270 degrees.

###  4.1. Apparatus

Two different devices were used for the experiment -

  1. (1)

Google Pixel 3 (145.6 x 68.2 x 7.9 mm)

  2. (2)

Motorola Moto G4 (153 x 76.6 x 9.8 mm)

All information related to the devices have been collected from GSM Arena
555https://www.gsmarena.com/. Both devices run on the Android platform, with
comparable specs and performance. Since our application (which has been
designed for the purpose of this experiment) is not processor or memory heavy,
we safely assumed that the minor individual differences in the smartphones
won’t influence any change in the data being gathered. No other active
applications were running on the phone during the study. The phones were
connected over WiFi to Android Studio and System logs were sent from the
device to gather the data. To prevent other services of the phone, we used the
device in airplane mode during our experiment. A mobile phone video camera was
used to capture the complete study, focusing only on the device and user’s
hands.

###  4.2. Variables

Independent Variables were _UI-Element Placement_ (Baseline - top layout and
adaptation - left/right layout), _Interaction Hand_ (dominant and non-
dominant), _Sub-Area_ (1-6), and _Phone Size_ used (Google Pixel 3 and
Motorola MotoG4). UI-Element Placement denotes with which layout user
interacted during the experiment. Interaction Hand denotes whether the
dominant or the non-dominant hand is being used during interaction. Sub-Area
denotes one of the 6 areas in which the Action Bar is divided in. Phone Size
used denotes with which device user interacts with during the experiment.

Dependent Variables were _Target Selection Time_ [ms], _Device Orientation_ in
X, Y, Z direction [degrees]. For each trial, Target Selection Time denotes the
time from the appearance of the instruction to choose a number on the screen
till the time the target was actually hit. Device orientation denotes the
change in grip of the phone in the three dimensions.

We recorded 3 UI-Element Placement (top/left/right) X 6 Sub-Area (1-6) X 2
Phone Size (Pixel/MotoG4) X 2 Interaction Hand (dominant/non-dominant) X 3
repetitions = 216 trials per participant. We also logged all trials to
investigate potential outliers later. _UI-Element Placement_ and _Phone Size_
were both counterbalanced using a Latin Square, and Sub-Area selection
sequence in all 3 layouts were randomized. Once all three repetitions were
done, the user continued with the next technique, until all techniques had
been tested. A trial session was presented before the start of the experiment
to the user to get familiar with the task.

After the experiment concluded the users were asked to fill up a short
Questionnaire where they were asked to rank the techniques based on perceived
speed, safe grip and comfort.

##  5\. Results

A total of 5 outliers were identified by applying the Tukey Method for Extreme
Outliers on Time (7-12 sec). Looking at the video recordings for these trials
revealed that users held the phone with both hands and then switched to one
hand or were trying to adjust their sleeve/watch, while time was being
counted, but they asked us to delete these button press. Hence, these trials
were not representative and we excluded them from the analysis.

Firstly, we checked the normal distribution of our data using Q-Q plot and
based on the result, we performed repeated measure multivariate ANOVA to
report following results.

Time Consumption: For non-dominant hand, the speed was statistically
significantly different (F(2, 694) = 22.563, p ¡ 0.05) for different
placements of action bar. When comparing pairwise with Bonferroni post-hoc
test, we found that for non-dominant hand left panel was significantly faster
than both top panel (p = 0.0005) and right panel (p = 0.0005). Left (M =
1079.13 ms; 95% CI [588.76, 1569.50]) incurred less time consumption than top
(M = 1142.11 ms; 95% CI [593.20, 1691.02]) and (M = 1378.05 ms; 95% CI
[578.926, 2177.174]) right panel. Difference between the means for left & top
is 62.98 ms and between right & top is 298.92 ms. For dominant hand, there was
no significant result observed for any panel layout. However, the average time
consumed for hitting target on left panel (1077.95 ms) was less than both top
panel (1140.70 ms) and right panel (1369.76 ms). In addition, there was no
significant effect of phone sizes on time required to hit the target.

Device Orientation: The overall pitch orientation angle was significantly
different (F(2, 694) = 143.88, p ¡ 0.05) for different layouts of the action
bar in context of dominant hand. When comparing pairwise with Bonferroni post
hoc test, we found that for dominant hand, right panel layout had
significantly less device pitch compared to left panel and top panel. Right (M
= 0.4100 degrees ; 95% CI [588.76, 1569.50]) incurred less pitch orientation
angle than top (M = -1.7868 degrees; 95% CI [1.830, 2.564]) and (M = -1.5609
degrees; 95% CI [1.628, 2.314]) left panel. Difference between the means for
right & top is 2.197 degrees and between right & left is 1.971 degrees.
However, this significant difference was not found for non-significant hand.

For device roll orientation angle, we found both left and right layout having
less device roll compared to top panel (F(2, 1378) = 406.976, p ¡ 0.05). Right
(M = 2.773 degrees ; 95% CI [2.597, 2.951]) and left (M = 2.619 degrees; 95%
CI [2.411, 2.828]) incurred less pitch orientation angle than top (M = 4.376
degrees; 95% CI [4.240, 4.514]). Difference between the means for top & right
is 1.603 degrees and between top & left is 1.757 degrees. However, there was
no significant difference between left and right layout. In addition, it was
interesting to note that the right panel layout also had significantly less
device roll (p=0.0001) when compared to left panel layout. In all, these
results had no significant impact for dominant and non-dominant hands & both
phone sizes.

We found an interesting result for azimuth device orientation angle for
dominant hand. When performing paired t-test on our combinations we found that
the top panel layout significantly incurred less azimuth orientation t(347) =
23.570, p ¡ 0.0005 compared to right layout. Top (M = 7.713 degrees; 95% CI
[6.289, 9.137]) incurred less azimuth orientation than (M = 8.819 degrees; 95%
CI [7.708, 9.93]) right panel. Difference between the means is 1.106 degrees.
This implies more safer grip of the phone with action bar being on left panel
of the device. The result was consistent across both the phone sizes.

Far Targets: We also found positive correlations between time taken and the
distance to the far targets. We define far targets as targets on the screen
edges i.e. 1 and 6 which are not ease to reach. On comparing left and right
screen layout of the action bar for non-dominant hand, we found right screen
layout has significant positive co-relation (r=0.342, p¡0.001) with time taken
to hit far targets compared to left screen layout. However, there was no
significant difference between top layout compared to both right and left
layout. Similarly, there was no significant difference when we take into
account the dominant hand.

Figure 3. The chart show user feedback (dominant hand) (P=8) where 5 = very
fast, very fast and very comfortable, suggesting that users found the baseline
panel less comfortable and had unsafe gripping as per their experience.
Perceived Speed (mean = 3.055, std = 1.198), Comfort (mean = 3.364, std =
1.249), and Safe Gripping (mean = 2.733, std = 1.290).

User Ratings: We recorded Likert scale data for user ratings. Adaptation
elements were perceived as faster, more comfortable to use, and more grip safe
compared to the baseline top position for use with dominant hand for both the
devices (refer figure 3). On the other hand, the baseline layout ’top’
position was considerably less fast, comfortable and had unstable grip
compared to adaptation condition (refer figure 4). Given the small sample
size, we refrain from reporting any statistical analyses.

Figure 4. The chart show user feedback (dominant hand) (P=8) where 5 = very
fast, very fast and very comfortable, suggesting that users found the
adaptation panel easy to use and were satisfied overall with the experience.
Perceived Speed (mean = 4.564, std = 0.798), Comfort (mean = 4.464, std =
1.265), and Safe Gripping (mean = 4.235, std = 1.361).

Video Recording Analysis We attempted to find out if there exists any patterns
while holding device and hitting targets on the action bar. We found 4
different patterns that were common across all of the participants.

Figure 5. This figure shows 4 different observed patterns (a, b, c and d)
while holding mobile devices when selecting targets on action bar. a
represents ease of use, b represents use of additional hand, c represents
touching back side of phone and d represents change in grip

In figure 5a, for a left-handed user the adapted layout on left and right
panel of the screen was easy to navigate in terms of change of gripping of the
phone compared to baseline layout of top panel. For figure 5b, some of our
right-handed users placed their right hand under the phone while performing
the non-dominant hand trial in order to make sure phone doesn’t fall down. In
figure 5c, a right-handed user placed left hand on back side of phone to
change his grip. Another interesting pattern was found for baseline layout. In
figure 5d, a right-handed user had to change her grip always whenever she
tried reaching the buttons on the top version of the action bar.

##  6\. Discussion

Our results show how users interact with touch screen mobile devices for
action bar. Action bar is a vital UI element in almost all the applications
used independent of the device platform. Our study can help designers to
consider hand dominance and UI adaptations while designing the action bar. We
first discuss the importance of one-handed use of mobile phones and then draw
the reader’s attention to already available techniques and our difference with
them through experiment.

We then discuss our experiment focusing upon 2 different devices with 3
different layouts for action bar including the existing use of action bar i.e.
at the top of the screen. Our results suggest that hand dominance plays a
crucial role while approaching targets on the action bar. We however didn’t
find any significant difference in our adaptation compared to existing
position in terms of time consumption. The difference in means for time in
both condition waves a path that researchers can consider as potential
research area in future. We found significant differences in pitch and azimuth
angles of orientation for our designed adaptation on comparing with top
layout. These results infers higher stability of phone while reaching far
targets so that users have better grip. In addition we found a positive co-
relation between far targets and time consumption in all the 3 techniques used
in the experiment.

Our user ratings indicates that designed adaptations were perceived as faster,
more comfortable and offering more stability for the smartphone. These results
are at par with the observed logged data, however the recorded data didn’t
reveal any significant result. In addition, our video recording analyses
reveals interesting observed patterns. We found left-handed users doesn’t
change their grip as much in our UI adaptations compared to baseline top
layout. Also, there is a common pattern to hold the mobile device to save it
from falling. Either users place their free hand beneath the phone while
interacting with action bar or they firmly hold the phone with strength so
that it doesn’t fall down.

As expected for right-handed users placing action bar on right side of the
screen would be easy to reach. Naturally, the displacement between the target
and thumb position is decreased owing to faster hitting of target.
Nevertheless, the top layout was user’s most experienced way of interacting
with action bar, we found adaptations to be useful as well. In all,
significant results for orientation led us to investigate whether we could now
effectively consider other UI elements in our future designs.

##  7\. Limitations and Future Work

In our study, we only tested our adaptations only for action bar. There are
other important elements in devices which plays crucial role for reachability
as well. Unlike testing mere speed we incorporated several factors which can
influence the target hitting at far areas on the mobile touch screen. We also
displayed only 6 sub-areas of action bar which were essential for the covering
the entire bar area. This was done in order to utilize maximum screen area.
However, the sub-area count can be less or more for different screen sizes.
Our future work would involve investigating UI adaptations for floating action
bar, tabbed menus and hamburger menu options. We also aim to conduct a
comparative future study in a controlled environment v/s in different
scenarios in field to better understand how users use adaptations when we can
automatically switch layout based on users intentions.

##  8\. Summary and Conclusion

In summary, we presented UI adaptations for action bar, an interaction
technique to improve reachability for smartphones. With our study we found
that UI adaptations were significantly better technique both in terms of speed
and device orientation if users use non-dominant hand to reach targets on
action bar. It offers better grip and stability of smartphones. No significant
difference was found for use of UI adaptations compared to existing layout of
action bar for time consumption i.e. at the top of the screen. Our users rated
designed adaptations faster, comfortable to use and offering stable grip when
compared with existing layout. In addition, video analyses shows that with
designed adaptations stable grip coping strategies were better while using
action bar one handed.

##  9\. Acknowledgement

The authors would like to extend warm thanks to all participants who
participated in this study. Also, the authors thank Marcel & Oliver for
helping them in designing the study and providing feedback on the overall
project.

## References

  * (1)
  * Bergstrom-Lehtovirta and Oulasvirta (2014) Joanna Bergstrom-Lehtovirta and Antti Oulasvirta. 2014.  Modeling the functional area of the thumb on mobile touchscreen surfaces. In _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems_. ACM, 1991–2000.
  * Buschek and Alt (2017) Daniel Buschek and Florian Alt. 2017.  ProbUI: Generalising touch target representations to enable declarative gesture definition for probabilistic GUIs. In _Proceedings of the 2017 CHI Conference on Human Factors in Computing Systems_. ACM, 4640–4653.
  * Buschek et al. (2017) Daniel Buschek, Maximilian Hackenschmied, and Florian Alt. 2017\.  Dynamic UI for One-Handed Use of Large Mobile Touchscreen Devices. In _IFIP Conference on Human-Computer Interaction_. Springer, 184–201.
  * Chang et al. (2015) Youli Chang, Sehi L’Yi, Kyle Koh, and Jinwook Seo. 2015\.  Understanding users’ touch behavior on large mobile touch-screens and assisted targeting by tilting gesture. In _Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems_. ACM, 1499–1508.
  * Girouard et al. (2015) Audrey Girouard, Jessica Lo, Md Riyadh, Farshad Daliri, Alexander Keith Eady, and Jerome Pasquero. 2015.  One-handed bend interactions with deformable smartphones. In _Proceedings of the 33rd annual ACM conference on human factors in computing systems_. ACM, 1509–1518.
  * Hong and Lee (2013) Jonggi Hong and Geehyuk Lee. 2013.  TouchShield: a virtual control for stable grip of a smartphone using the thumb. In _CHI’13 Extended Abstracts on Human Factors in Computing Systems_. ACM, 1305–1310.
  * Hoober ([n. d.]) Steven Hoober. [n. d.].  How Do Users Really Hold Mobile Devices :: UXmatters.  Retrieved July 5, 2019 from https://www.uxmatters.com/mt/archives/2013/02/how-do-users-really-hold-mobile-devices.php
  * Huot and Lecolinet (2006) Stéphane Huot and Eric Lecolinet. 2006.  SpiraList: a compact visualization technique for one-handed interaction with large lists on mobile devices. In _Proceedings of the 4th Nordic conference on Human-computer interaction: changing roles_. ACM, 445–448.
  * Karlson and Bederson (2008) Amy K Karlson and Benjamin B Bederson. 2008.  One-handed touchscreen input for legacy applications. In _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems_. ACM, 1399–1408.
  * Kim et al. (2012) Sunjun Kim, Jihyun Yu, and Geehyuk Lee. 2012.  Interaction techniques for unreachable objects on the touchscreen. In _Proceedings of the 24th Australian Computer-Human Interaction Conference_. ACM, 295–298.
  * Negulescu and McGrenere (2015) Matei Negulescu and Joanna McGrenere. 2015.  Grip change as an information side channel for mobile touch interaction. In _Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems_. ACM, 1519–1522.