arXiv:1610.03376v1 [math.GR] 9 Oct 2016

CUBULATING RANDOM GROUPS IN THE SQUARE MODEL
TOMASZ ODRZYGÓŹDŹ
3
Abstract. Our main result is that for densities < 10
a random group in the
square model has the Haagerup property and is residually ﬁnite. Moreover, we
generalize the Isoperimetric Inequality, to some class of non-planar diagrams
and, using this, we introduce a system of modiﬁed hypergraphs providing the
structure of a space with walls on the Cayley complex of a random group.
Then we show that the natural action of a random group on this space with
walls is proper, which gives the proper action of a random group on a CAT(0)
cube complex.

1. Introduction
In [Odr16] we introduced the square model for random groups, where we draw
at random relations of length four. The motivation was that the Cayley complex of
such a group has a natural structure of a square complex, which should be easier
to analyze than the polygonal Cayley complexes for groups in the Gromov model.
Definition 1.1. [Square model, [Odr16, Definition 1.3]] Consider the set An =
{a1 , . . . , an }, which we will refer to as an alphabet. Let Wn be the set of all
cyclically reduced words of length 4 over An . Note that |Wn | = (2n − 1)4 up
to a multiplicative constant. By Fn we will denote the free group generated by
the elements of An . By relators we will understand words over generators and by
relations the corresponding equalities holding in the group.
For d ∈ (0, 1) let us choose randomly, with uniform distribution, a subset Rn ⊂
Wn such that |Rn | = ⌊(2n − 1)4d ⌋. Quotienting Fn by the normal closure of the set
Rn , we obtain a random group in the square model at density d.
We say that property P occurs in the square model at density d with overwhelming probability (w.o.p.) if the probability that a random group has property P
converges to 1 as n → ∞.
In [Odr16] we showed that a random group in the square model at density d
w.o.p.:
• is trivial for d > 21 ,
• is infinite, hyperbolic, torsion-free of geometric dimension 2 for d < 12 ,
• is free for d < 41
• does not have Property (T) for d < 31
In this paper we prove
3
a random group in the square model w.o.p.
Theorem 1.2. For densities d < 10
acts properly and cocompactly on a CAT(0) cube complex.
3
Corollary 1.3. For densities d < 10
a random groups in the square model w.o.p.
has the Haagerup property and is residually finite.
1

2

TOMASZ ODRZYGÓŹDŹ

Proof. The residual finiteness results from [Ago13, Corollary 1.2] and the Haagerup
Property by a folklore remark (see for example [CMV04]).

To obtain Theorem 1.2 we needed to generalize the isoperimetric inequality
([Oll07, Theorem 2]) to a class of non-planar diagrams (see Theorem 2.5). This
generalization has already proved to be useful in other work on random groups (see
for example [MP15]). Theorem 2.5 is stated in the regime of the square model, but
the reasoning can be easily repeated in the Gromov model (see [Odr14] for some
version of it). The main idea of the proof of Theorem 1.2 is based on introducing
modified hypergraps, which provide a structure of a space with walls on the Cayley
complex of a random group, that has desired metric properties. This modified walls
allowed us to construct a proper action of a random group on a space with walls,
which was impossible to obtain using standard hypergraphs (introduced in [OW11]
for the Gromov model and in [Odr16] for the square model).
Organization. The paper is organized as follows: first we prove a generalization of
the isoperimetric inequality, then using this we introduce “corrected” hypergraphs
that provide the structure of a space with walls on the Cayley complex of a random
group. Finally we show that a random group acts properly on this space with walls.
The idea of correcting hypergraphs was inspired by [MP15].
Acknowledgements. The author would like to thank Piotr Przytycki for many
discussions and Piotr Nowak for general advice on writing.
2. Non-planar isoperimetric inequality
The goal of this section is to generalize the isoperimetric inequality to some class
of non-planar complexes, but having “disc-like” structure, meaning that they are
unions of a large disc component and some bounded non-planar pieces. Firstly, let
us recall the isoperimetric inequality:
Theorem 2.1 ([Oll07, Theorem 2]). For any ε > 0, in the Gromov model at density
d < 21 , with overwhelming probability all reduced van Kampen diagrams associated
to the group presentation satisfy
(2.1)

|∂D| ≥ l(1 − 2d − ε)|D|.

Here ∂D denotes the set of boundary edges of the diagram D and |D| denotes the
number of 2-cells of D.
One of the corollaries of Theorem 2.1 is that in the Gromov density model
at densities < 21 a random group is w.o.p. hyperbolic (see [Oll04, Theorem 1]
and [Gro93]). In [Odr16, Theorem 3.15] the author proved that Equation (2.1) is
satisfied w.o.p. as well for the square model of random groups.
Let us now introduce some definitions.
Definition 2.2. Suppose Y is a finite 2–complex, not necessarily a disc diagram.
˜ |, is
• The generalized boundary length of Y , denoted |∂Y
X
˜ | :=
(2 − deg(e)),
|∂Y
e∈Y (1)

CUBULATING RANDOM GROUPS IN THE SQUARE MODEL

• and the cancellation in Y is
Cancel(Y ) :=

X

e∈Y

3

(deg(e) − 1),

(1)

where deg(e) is the number of times that e appears as the image of an edge of the
attaching map of a 2–cell of Y .
˜ | = |∂Y |. Moreover, Cancel(Y ) =
Note, that for every planar diagram Y we have |∂Y
| − |∂Y |).

1
2 (4|Y

Definition 2.3. We say that a finite 2-complex Y is fulfilled by a set of relators
e
R if there is a combinatorial map from Y to the presentation complex X/G
that is
locally injective around edges (but not necessarily around vertices).
e is fulfilled by R.
In particular, any subcomplex of the Cayley complex X

Definition 2.4 (Diagram with K-small legs). Let G = hS|Ri be a finite group
presentation where R consists of cyclically reduced words of length 4 over S. For
K > 0 let Y be a 2–complex that is a union of a reduced Van Kampen diagram Z
and a family Zi of connected complexes, called legs of Y , such that |Zi | ≤ K, for
each i the leg Zi contains an external vertex of Z and that every edge of Y belongs
to maximally two legs. We call such Y a diagram with K-small legs (with respect
to the presentation hS|Ri). The disc diagram Z is called the disc basis of Y .
Until the end of this section G will denote the random group in the square model
e — the Cayley complex of G with respect to this
with the presentation hS|Ri and X
presentation.

Theorem 2.5 (Generalized Isoperimetric Inequality). In the square model at density d ≤ 21 the following statement holds w.o.p.: for each K and ε > 0 there is no
diagram Y with K-small legs fullfilable by R and satisfying:
(2.2)

Cancel(Y ) > 4(d + ε)|Y |,

or equivalently
(2.3)

˜ | > 4(1 − 2d − ε)|Y |.
|∂Y

Our strategy to prove Theorem 2.5 is to first prove a “local” version of it, that is
with the additional limit on the number of 2-cells in a diagram, and then to show
that this locality assmuption can be ommited. Analogous results for the Gromov
model was obtained by the author in [Odr14] and used in [MP15] to construct
balanced walls. We thank Piotr Przytycki for suggesting the statement of Theorem
2.5 involving the notion of cancellation.
2.1. Local version of the generalized isoperimetric inequality.
Lemma 2.6. In the square model at density d ≤ 21 , for each K, ε > 0 w.o.p. there
is no 2-complex Y with |Y | ≤ K fulfilled by R and satisfying
(2.4)

Cancel(Y ) > 4(d + ε)|Y |.

Our proof of Lemma 2.6 will be only a slight modification of Olliver’s proof of
Theorem 2.1. We postpone it to to introduce some necessary tools first.

4

TOMASZ ODRZYGÓŹDŹ

Definition 2.7. Let Y be a 2-complex. Suppose that the following additional
information is given:
(1) Every face of Y is labeled by a number i ∈ {1, 2, . . . , n}. The labels can
repeat and for each number 1 ≤ i ≤ n there is at least one face labeled with
i. We call n the number of distinct relators.
(2) For each face there is a distinguished edge, called the starting edge and an
orientation.
Such Y will be referred to as an abstract 2-complex. We say that Y is fulfilled
by a sequence of relators (r1 , r2 , . . . , rn ) if it is fulfilled by {r1 , r2 , . . . , rn } as 2complex, in such a way that each face f labelled by i ∈ {1, 2, . . . , n} (according
to (1) in Definition 2.7) is sent under the combinatorial map to the face of X/G
corresponding to ri , so that the image in X (1) /G of the attaching path of f , starting
at the oriented starting edge (according to (2) in Definition 2.7) reads off the word
ri . If f is labeled by i we say that f bears the relator i.
Recall that S denotes the cardinality of the generating set of a random group in
the square model. Let m denote the cardinality of the set S.
Proposition 2.8. Let R be a random set of relators at density d and at length
4 on m generators. Let Y be an abstract 2-complex. Then either Cancel(Y ) <
4(d + 2ε)|Y | or the probability that there exists a tuple of relators in R fulfilling Y
is less than (2m − 1)−4ε .
Before we prove this proposition we introduce some additional notation. Let n
be the number of distinct relators in an abstract 2-complex Y . For 1 ≤ i ≤ n let
mi be the number of times relator i appears in Y . Up to reordering the relators we
can suppose that m1 ≥ m2 ≥ · · · ≥ mn .
For 1 ≤ i1 , i2 ≤ n and 1 ≤ k1 , k2 ≤ l we say that (i1 , k1 ) > (i2 , k2 ) if i1 > i2
or i1 = i2 but k1 > k2 (lexicographic order). Suppose that for some s ≥ 2 an
edge e of Y is adjacent to faces f1 , f2 , . . . , fs labeled by i1 , i2 , . . . , is accordingly.
Suppose moreover that for 1 ≤ j ≤ s the edge e is the kj –th edge of the face fj .
Since Y → X/G is locally injective around e, the pairs (ij , kj ) are distinct. Choose
j = jmin for which (ij , kj ) is minimal. We say that edge e belongs to faces fj for
j ∈ {1, 2, . . . s} \ {jmin }.
Let δ(f ) be the number of edges belonging to a face f . For 1 ≤ i ≤ n let
κi = max{δ(f ) : f is a face labeled by relator i}
Note that
(2.5)

Cancel(Y ) =

X

f ∈Y

(2)

δ(f ) ≤

X

mi κ i

1≤i≤n

Definition 2.9. Let Y be an abstract 2-complex with n distinct relators. For
1 ≤ k ≤ n let R′ = (w1 , w2 , . . . , wk ) be a sequence of relators. We say that Y is
partially fulfilled by R′ if the abstract 2-complex Y ′ ⊂ Y that is the closure of the
faces of Y labeled by the numbers i ∈ {1, 2, ..., k} is fulfilled by R′ .
Lemma 2.10. For 1 ≤ i ≤ n let pi be the probability that i randomly chosen words
w1 , w2 , . . . , wi partially fulfill Y and let p0 = 1. Then
pi
≤ (2m − 1)−κi .
(2.6)
pi−1

CUBULATING RANDOM GROUPS IN THE SQUARE MODEL

5

Proof. Suppose that first i − 1 words w1 , . . . , wi−1 partially fulfilling Y are given.
We will successively analyze what is the choice for the consecutive letters of the
word wi , so that Y is fulfilled. Let k ≤ 4 and suppose that the first k − 1 letters of
wi are chosen. Let f be the face realizing δ(f ) = κi and let e be the k-th edge of
the face f .
If e belongs to f this means that there is another face f ′ meeting e which bears
relator i′ < i or bears i too, but e appears in f ′ as a k ′ < k-th edge. In both cases
the letter on the edge e is imposed by some letter already chosen so drawing it at
1
up to some small error. In fact, this estimate
random has probability ≤ (2m−1)
would be valid only if the words were only required to be reduced; since they are
cyclically reduced a negligible error appears, which we ignore.
Combining all these observations we get that the probability to choose at random

the correct word wi is at most pi−1 (2m − 1)−κi .
Now we can provide the proof of Proposition 2.8
Proof of Proposition 2.8. For 1 ≤ i ≤ n let Pi be the probability that there exists
an i-tuple of words partially fulfilling Y in the random set of relators R. We trivially
have:
Pi ≤ |R|i pi = (2m − 1)4id pi

(2.7)

Combining equations (2.5) and (2.6) we get
n
X

Cancel(Y ) ≤

mi (log2m−1 pi−1 − log2m−1 pi ) =

i=1

=

n−1
X

(mi+1 − mi ) log2m−1 pi − mn log2m−1 pn + m1 log2m−1 p0 .

i=1

Now p0 = 1 so log2m−1 p0 = 0 and we have
Cancel(Y ) ≤

n−1
X

(mi+1 − mi ) log2m−1 pi − mn log2m−1 pn .

i=1

From (2.7) and the fact that mi+1 − mi ≤ 0 we obtain
Cancel(Y ) ≤

n−1
X

(mi+1 − mi )(log2m−1 Pi − 4id) − mn log2m−1 (Pn − 4nd)

i=1

Observe that

Pn−1
i=1

(mi − mi+1 )i + mn n =

Cancel(Y ) ≤ 4|Y |d +

n−1
X

Pn

i=1

mi = |Y |. Hence

(mi+1 − mi ) log2m−1 Pi − mn log2m−1 Pn

i=1

Setting P = mini Pi and using the fact that mi+1 − mi ≤ 0 we get

Cancel(Y ) ≤ 4|Y |d + (log2m−1 P )

n−1
X

(mi+1 − mi ) − mn log2m−1 P =

i=1

= 4|Y |d − m1 log2m−1 P ≤ |Y |(4d − log2m−1 P ),

6

TOMASZ ODRZYGÓŹDŹ

since m1 ≤ |Y |. It is clear that a complex is fulfillable if it is partially fulfillable for
any i ≤ n and so:
Probability(Y is fullfillable by relators of R) ≤ P ≤ (2m − 1)

4|Y |d−Cancel(Y )
|Y |

which was to be proven.

,


Proof of Lemma 2.6. Denote by C(K, m) the number of abstract square complexes
with at most K 2-cells. Observe that there are finitely many square complexes with
at most K faces. There are also finitely many ways to decide which faces would
bear the same relator, and also finitely many ways to choose the starting point of
each relator. Therefore, the values {C(K, m)}m∈N with fixed K have a uniform
bound M . We know by Proposition 2.8 that for any abstract 2-complex with at
most K faces violating the inequality Cancel(Y ) < 4(d + ε)|Y | the probability that
it is fulfilled by a random set of relators is ≤ (2m − 1)−4ε . So the probability that
there exists a fulfilled 2-complex with at most K faces, violating the inequality is
≤ C(K, m)(2m − 1)−4εl ≤ M (2m − 1)−4εl , so it converges to 0 as m → ∞.

2.2. From the local version to the global. We start this subsection by reformulating [Oll07, Lemma 11] by replacing the length of relator l by 4.
Lemma 2.11. Let G = hS|Ri be a finite presentation in which all elements of R
have length 4. Suppose that for some constant C ′ > 0 every van Kampen diagram
E of this presentation satisfies:
|∂E| ≥ 4C ′ |E|.
Then every van Kampen diagram D can be partitioned into two diagrams D′ , D′′ by
with endpoints on the boundary
cutting it along a path of length at most 4 + 8 log(|D|)
C′
of D such that each of D′ and D′′ contains at least one quarter of the boundary of
D.
We will state now prove two propositions „approximating” Theorem 2.5.
Proposition 2.12. Let G = hS|Ri be a finite presentation such that all elements of
R are reduced words of length 4. Suppose that for some constant C ′ all van Kampen
diagrams D with respect to this presentation satisfy
|∂D| ≥ C ′ 4|D|.
7A
Choose any K, ε > 0. Take A large enough to satisfy εA > 2(1 + C2′ log( 6C
′ ) + 2K).
Suppose that for some C > 0 all diagrams with K–small legs Y having the disc
basis of boundary at most 4A satisfy:

˜ | ≥ C4|Y |.
|∂Y
Then all diagrams with K–small legs Y having the disc basis of boundary at most
14
3 A satisfy:
˜ | ≥ (C − ε)4|Y |
|∂Y

CUBULATING RANDOM GROUPS IN THE SQUARE MODEL

7

Proof. Let Y be the diagram with K–small legs such that its disc basis Z has the
boundary length between 4A and 14
3 A. By Lemma 2.11 we can perform a partition
of Z into two reduced disc diagrams Z ′ and Z ′′ such that: |∂Z ′ |, |∂Z ′′ | ≥ 41 |∂Z|
and |∂Z ′ ∩ ∂Z ′′ | ≤ 4 + C8′ log(|Z|). The number of 1–cells that belong both to Z
and one of the legs Zi is bounded by 4K, since there are no more than 4K 1–cells
in Zi . We define Y ′ to be the union of Z ′ and all legs of Y that are adjacent to
Z ′ , and Y ′′ to be the union of Z ′′ and all legs of Y adjacent to it. Hence we can
perform a partition of Y into two diagrams Y ′ and Y ′′ with K–small legs such that
˜ | ≥ |∂Y
˜ ′ | + |∂Y
˜ ′′ | − 2(4 + 8′ log(|Z|) + 8K).
|∂Y
C
Note that |∂Z ′ |, |∂Z ′′ | < 4A so by our assumption we know
˜ ′ | ≥ C4|Y ′ |
|∂Y
˜ ′′ | ≥ C4|Y ′′ |.
|∂Y
Moreover by the assumption on van Kampen diagrams we obtain that
7A
1
C ′ log( 6C ′ ). Hence

1
C′

log(|Z|) <

˜ | ≥ |∂Y
˜ ′ | + |∂Y
˜ ′′ | − 2(4 + 8 log(|Z|) + 8K)
|∂Y
C′
7A
8
≥ C4(|Y ′ | + |Y ′′ |) − 2(4 + ′ log( ′ ) + 8K).
C
6C
7A
We have chosen A large enough so that 2(1 + 2 C1′ log( 6C
′ ) + 2K) < εA so we
can continue estimation
˜ | ≥ Cl|Y | − 4εA ≥ 4(C − ε)|Y |
|∂Y
since 4|Y | ≥ |∂Z| ≥ 4A.



The last approximation to Theorem 2.5 is the following
Proposition 2.13. Let G = hS|Ri be a finite presentation such that all elements of
R are reduced words of length 4. Suppose that for some constant C ′ all van Kampen
diagrams D with respect to the presentation satisfy
(2.8)

|∂D| ≥ C ′ l|D|.

7A
Choose any K, ε > 0. Take A large enough to satisfy εA > 2(1+2 C1′ log( 6C
′ )+2K).
Suppose that for some C > 0 all diagrams Y with K–small legs and the disc basis
with boundary length at most 4A satisfy:

(2.9)

˜ | ≥ 4C|Y |.
|∂Y

Then all diagrams with K–small legs Y satisfy:
˜ | ≥ 4(C − ε)|Y |
|∂Y
Proof. The assumptions of this proposition and Proposition 2.12 are the same.
Hence by the statement of Proposition 2.12 we can conclude that the assumptions
1
of Proposition 2.12 are fulfilled with the new parameters: A1 = 67 A, ε1 = ε( 67 ) 2
and C1 = C − ε instead of A, ε, C and with the same C ′ (these new parameters
1
indeed satisfy ε1 A1 > 2(1 + C2′ log( 7A
6C ′ ) + 2K)). By induction every diagram with

8

TOMASZ ODRZYGÓŹDŹ

K − small legs such that its disc basis has boundary of length at most 4A
satisfies
˜ |≥
|∂Y

C−ε

k−1
X
i=0

and we conclude by the inequality

P∞

i=0

6
7

6
7

 2i

 2i !


7 k
6

4|Y |

< 14.



Proof of Theorem 2.5. First, by Theorem 2.1 we know that all Van Kampen diagrams satisfy Equation (2.8) for C = (1 − 2d − ε′ ), for arbitrary small ε′ . By
Lemma 2.6 we know that for any K, ε all diagrams with K-small legs satisfy Equation (2.9). Hence the assumptions of the Proposition 2.13 are satisfied, which gives
the statement.

3. Colored hypergraphs
In this section we we will introduce colored hypergraphs, which can be effectively
used in investigating random groups in the square model. We start with
e be the Cayley complex of a random group in the square
Proposition 3.1. Let X
1
model at density d < 3 . Then w.o.p.:
e having three common edges.
(1) There is no pair of 2-cells in X
e such that |∂D ∩ ∂E| = 2, then there is no 2-cell
(2) If D and E are 2-cells in X
e
F in X such that |(∂D ∪ ∂E) ∩ ∂F | > 1.

e having three common edges forms a van Kampen
Proof. (1) A pair of 2-cells in X
diagram D satisfying |∂D| = 2 and |D| = 2. Therefore |∂D| ≤ 43 |D|, so D violates
Theorem 2.5, which implies that w.o.p. there is no such a pair of 2-cells.
(2) Suppose, on the contrary, that there exist such 2-cells D, E and F . Consider
a diagram D consisting of 2-cells D and E. Adding a new 2-cell to D by gluing
it along two edges does not change the generalized boundary length of D. Hence
˜ | = 4, |Y | = 3.
the diagram Y that is a union of D and the 2-cell F satisfies: |∂Y
˜
Therefore, Y violates Theorem 2.5, which states that |∂Y | > 4(1 − 2d)|Y |, so w.o.p.
there is no such a triple of 2-cells.


e be the Cayley complex of a random group in the square
Definition 3.2. Let X
1
e have two common edges, we say they are
model at density ≤ 3 . If two 2-cells in X
strongly adjacent. If a 2-cell D is strongly adjacent to some other 2-cell we say that
D is a distinguished 2-cell. The common edges of two strongly adjacent 2-cells we
call distinguished edges. A 2-cell which is not a distinguished 2-cell we call a regular
2-cell.
Proposition 3.3. Let D and E be strongly adjacent 2-cells. Then there is no
e
element of a random group G sending D to E under the natural action of G on X.
e
In other words, D and E are in different orbits of the action of G on X.


(2n−1)4 −6(2n)2
(2n−1)4d



(2n−1)4
(2n−1)4d





,

CUBULATING RANDOM GROUPS IN THE SQUARE MODEL

9

Proof. Suppose that there exists g ∈ G sending D to E. By Lemma 3.1 we know
that a 2-cell can be strongly adjacent to at most one other 2-cell, co g preserves the
pair {D, E}. The diagram Y consisting of 2-cells D and E has exactly one internal
vertex (that is a vertex isolated from the boundary). If the diagram {D, E} is
preserved by g the internal vertex must be also preserved, which contradicts the
fact that the action of G on its Cayley graph is free.

Definition 3.4 (Procedure of painting the Cayley complex). By Proposition 3.1
we know that distinguished 2-cells form a set S of disjoint unordered pairs of 2-cells.
By Proposition 3.3 we know that none of these pairs lies in one orbit of G-action
e We will now perform a procedure of painting distinguished 2-cells in two
on X.
colors: red and blue.
In the first step we consider one of the pairs {D, E} ∈ S and choose arbitrarily
one 2-cell from this pair. Without loss of generality we can suppose that D is
chosen. We say that D is a red 2-cell and E is a blue cell. Moreover we say that
each element in the orbit of D is red and each element in the orbit of E is blue.
In the next step we choose another pair of strongly adjacent 2-cells {D1 , D2 },
that is not in the orbit of the pair {D, E}. Then we paint all elements in the orbit
of D1 in red, and all elements in the orbit of E1 in blue. We repeat this step until
all distinguished 2-cells are painted. The Cayley complex is cofinite, so there are
finitely many orbits of 2-cells and therefore this painting procedure must end after
a finite number of steps. The Cayley complex with painted distinguished 2-cells we
call painted Cayley complex.
From now we will always assume that the Cayley complex of a random group is
e
painted, and we will denote it by X.
We now recall the definition of a hypergraph from [OW11, Definition 2.1].

Definition 3.5 (standard hypergraph). Let X be a connected square complex. We
define a graph Γ as follows: The set of vertices of Γ is the set of 1-cells of X. There
is an edge in Γ between two vertices if there is some 2-cell R of X such that these
vertices correspond to opposite 1-cells in the boundary of R (if there are several
such 2-cells we put as many edges in Γ). The 2-cell R is the 2-cell of X containing
the edge.
There is a natural map ϕ from Γ to X, which sends each vertex of Γ to the
midpoint of the corresponding 1-cell of X and each edge of Γ to a segment joining
two opposite points in the 2-cell R. Note that the images of two edges contained
in the same 2-cell R always intersect, so that in general ϕ is not an embedding.
A standard hypergraph in X is a connected component of Γ. The 1-cells of X
through which a hypergraph passes are dual to it. The hypergraph Λ embeds if ϕ
is an embedding from Λ to X, that is, if no two distinct edges of Λ are mapped to
the same 2-cell of X.
We call the subdiagram of X consisting of all open faces containing edges of the
hypergraph Λ the carrier of Λ and denote it by Car(Λ).
The hypergraph segment in X is a finite path in a hypergraph immersed into X.
The carrier of a segment Λ′ denoted Car(Λ′ ) is the diagram consisting of all open
2-cells containing edges of the segment Λ′ .
By [Odr16, Lemma 5.16] we know that standard hypergraphs are embedded
trees. Moreover, [OW11, Lemma 2.3] states that for each standard hypergraph Γ
e − Γ has exactly two connected components. However the system of
the space X

10

TOMASZ ODRZYGÓŹDŹ

standard hypergraphs is not sufficient to construct a proper action of a random
group on a CAT(0) cube complex, which we need to prove Theorem 1.3. Our
strategy of constructing such an action is based on showing that the wall space
metric on the Cayley complex is equivalent to the edge path metric. This means
in particular that for every number N if we have two enough distant points in the
Cayley complex they are separated by at least N walls, which are hypergraphs in our
case. In Figure 1 we present an example of a geodesic edge-path γ of an arbitary
length such that no standard hypergraph separates its ends x and y. Situation
presented in Figure 1 cannot be excluded for densities ≥ 14 in the square model,
therefore we need a better system of walls, based on more systems of hypergraphs.

x
γ
...
y

Figure 1. Arbitrary long geodesic edge-path joining points x and
y that are not separated by a hypergraph.
We now introduce a new type of hypergraph - red hypegraph, which is modified
on red 2-cells.
Definition 3.6 (red and blue hypergraph). Let X be a connected square complex
e We define a graph Γ as
that is a subcomplex of the painted Cayley complex X.
follows: The set of vertices of Γ is the set of 1-cells of X. We put an edge in Γ
between two vertices if one the following holds:
(1) there is some regular or blue 2-cell R of X such that these vertices correspond to opposite 1-cells in the boundary of R (if there are several such
2-cells we put as many edges in Γ
(2) there is some red 2-cell R of X such that one of this vertices corresponds to
distinguished edge e of R and the second corresponds to non distinguished
edge of R which is not opposite to e.
The 2-cell R is the 2-cell of X containing the edge.
There is a natural map ϕ from Γ to X, which sends each vertex of Γ to the
midpoint of the corresponding 1-cell of X and each edge of Γ to a segment joining
two points in the boundary 2-cell R.
A red hypergraph in X is a connected component of Γ. The 1-cells of X through
which a hypergraph passes are dual to it. The red hypergraph Λ embeds if ϕ is an
embedding from Λ to X.
We call the subdiagram of X consisting of all open 2-cells containing edges of
the red hypergraph Λ the carrier of Λ and denote it by Car(Λ).
The hypergraph segment in X is a finite path in a hypergraph immersed into X.
The carrier of a segment Λ′ denoted Car(Λ′ ) is the diagram consisting of all open
2-cells containing edges of the segment Λ′ .

CUBULATING RANDOM GROUPS IN THE SQUARE MODEL

11

If in the above definition we replace every occurrence of the word “red” by the
word “blue” we obtain the definition of the blue hypergraph.
The comparison of the hypergraphs introduced above is presented in Figure 2.

Λst
blue
2-cell

Λst
blue
2-cell

Λred

red 2-cell

Λblue

red 2-cell

a)

b)

Figure 2. a) The comparison of a red hypergraph Λred and a
standard hypergraph Λst , b) The comparison of a blue hypergraph
Λblue and a standard hypergraph Λst .
3.1. Hypergraphs are embedded trees. Now we are going to prove
Theorem 3.7. In the square model at density d <
e are embedded trees.
hypergraphs in X

1
3

w.o.p. all red and blue

To investigate standard and red hypergraphs we need a notion of a collared
diagram. Our definition is a slight modification of the one introduced by Ollivier
and Wise in [OW11, Definition 3.2].
Definition 3.8. (collared diagram) Let D be a Van Kampen with the following
properties:
(1) there is an external 2-cell C called a corner of D
e of a hypergraph (standard, red or blue) of
(2) there is a segment λ → D → X
length at least 2
(3) the first and the last edge of λ lie in C, and no other edge lies in C
(4) λ passes through every other external 2-cell of D exactly once
(5) λ does not pass through any internal 2-cell of D
We call D a collared diagram and λ a collaring segment. We also say that D
is cornerless if the first and the last edge of λ coincide in C (in which case the
hypergraph cycles).
Now we will use the additional color-structure of a Painted Cayley complex to
perform the following procedure of adding horns to a diagram.
e
Definition 3.9 (adding horns procedure). Let D be a van Kampen diagram in X.
Let ∂2 (D) be the set of all 2-cells in D that contain a boundary edge of D. Let
∂2s (D) be the set of all distinguished 2-cells c in 2 − ∂(D) such that a 2-cell c′ , that
is strongly adjacent to c, does not belong to D.

12

TOMASZ ODRZYGÓŹDŹ

We define a diagram with horns D in the following way: for each c ∈ ∂2 (D) we
glue to a diagram D a 2-cell c′ that is strongly adjacent to c (gluing is in a way that
e
these 2-cells are glued in X).

If that will be clear we will call diagrams with horns just diagrams, for shortness.

˜
Lemma 3.10. Let D be a diagram with horns. Then |∂(D)|
(the generalized boundary length) is an even number.

Proof. The statement results from the fact that every 2-cell of D has even number of
edges and every gluing of 2-cells along an edge decreases the generalized boundary
length by 2.

Remark 3.11. A diagram with horns is a union of a disc diagram D and a set
Z of 2-cells, each of them being adjacent to the boundary of D along at least one
vertex and such that no two elements of Z share an edge.
Proof. The only thing that we need to prove is that no two elements of Z share an
edge. This results by Proposition 3.1.

Corollary 3.12 (of Remark 3.11). Collared diagrams with horns w.o.p. satisfy the
assumptions of Theorem 2.5.
The following theorem shows the relation between collared diagrams and hypergraphs
Theorem 3.13 (reformulation of [OW11, Theorem 3.5]). Let Λ be a hypergraph in
e The following conditions are equivalent:
X.
(1) Λ is an embedded tree.
(2) There is no collared diagram collared by a segment of Λ.
There is a definition of a diagram collared by a hypergraph in [OW11, Definition
3.11]. However, in the paper [OW11] this definition was stated for a general l-gon
complex and for the standard hypergraphs that join antipodal midpoints of faces
they are passing through. Definition 4.3 is a modification of [OW11, Definition
3.11]: we use it for l = 4 and for hypergraphs defined in a different way, but the
e is not necessary
fact the hypergraph joins the antipodal midpoints of edges in X
to provide the proof of Theorem 3.13, in fact the proof can be repeated, as well, in
case of colored hypergraphs.
The next theorem is motivated by Theorem 3.13 and shows the relation between
collared diagrams with horns and colored hypergraphs.
e If
Theorem 3.14. Let Λ be a red or blue hypergraph in X.
Λ is not an embedded tree, then there is a collared diagram with horns collared by
a segment of Λ.
Proof. By Theorem 3.13 we know that there exists collared diagram collared by a
segment of Λ. We obtain the statement of Theorem 3.14 by applying the procedure
of adding horns to a diagram described in Definiton 3.9

Proof of Theorem 3.7. Suppose, on the contrary, that there is a red or blue hypergraph that is not an embedded tree. By Theorem 3.14 we know that there is a
˜
collared diagram
with horns E collared by some segment λ. Let n = |∂E|.
For

1
ε < 2 3 − d by Theorem 2.5 we have w.o.p.

CUBULATING RANDOM GROUPS IN THE SQUARE MODEL

13

˜ ≥ 4|E|(1 − 2d − ε) > 4 |E|
n = |∂E|
3
There are two possibilities: either E is cornerless or not. First consider the
case where E is cornerless. Then every external 2-cell, which is not red or blue has
exactly one external edge. Each pair of strongly adjacent 2-cells gives a contribution
˜ equal 2, independently of the way the blue or red 2-cell is glued to the
to |∂E|
diagram E. Hence |E| ≥ n. By (3.1) we know that with overwhelming probability
all collared cornerless diagrams with horns satisfy:
(3.1)

4
n,
3
which is a contradiction. Therefore, with overwhelming probability there are no
such diagrams.
Let us now consider the case where the diagram E is not cornerless. The only
difference between the previous case is that a corner can have two external edges.
Therefore |E| ≥ n − 1. We have two possibilities |E| ≥ n or |E| = n − 1. If |E| ≥ n
we again obtain (3.2), which is a contradiction. Hence, the only remaining case is
˜ = n and |E| = n − 1. Again we use (3.1) to obtain:
where |∂E|
(3.2)

n>

4
(n − 1).
3
It can be easily seen that for n > 3 this is not possible. So we only have to exclude
˜ = 3. But there are no diagrams with odd generalized
the diagram |E| = 2, |∂E|
boundary length, according to Lemma 3.10.

n>

Lemma 3.15. Suppose that a red hypergraph or a blue hypergraph Λ is an embedded
e Then X
e − Λ consists of two connected components.
tree in X.
Proof. The proof is analogous to the proof of [OW11, Lemma 2.3].



4. Metrically proper action on a space with walls
In this section our goal is to prove the following
3
. Let
Theorem 4.1. Let G be a random group in the square model at density d < 10
e
e
X be the Cayley complex of G. For x, y ∈ X we denote by dwall (x, y) the number
of hypergraphs Λ (standard, red and blue) such that x and y lie in the different
e − Λ. Then w.o.p.
connected components of X

1
d e (1) (x, y)⌋,
15 X
e
denotes the edge metric on the 1-skeleton of X.
dwall (x, y) ≥ ⌊

where dXe (1)

The meaning of the foregoing theorem comes from the following
Proof of Theorem 1.2. By Lemma 3.15 hypergraphs are embeddes trees, and by
Lemma 3.15 and [OW11, Lemma 2.3] they separate the Cayley complex into two
connected components, so they provide a structure of a space with walls on it.
Every discrete group acts properly on its Cayley complex, and by Theorem 4.1 the
wall metric and edge metric on the Cayley complex are equivalent. Therefore a

14

TOMASZ ODRZYGÓŹDŹ

group acts properly on a space with walls. Then by [CN05] there is an action of a
random group on a CAT(0) cube complex.

Before we provide the proof of Theorem 4.1 we need several facts about the
geometry of hypergraphs. For simplicity, until the end of this section we will denote
e the painted Cayley complex of a random group in the square model at density
by X
3
e (1) the 1-skeleton of X
e (i.e. the Cayley graph of a random group).
and by X
d < 10

e let E be a 2-cell having exactly
Lemma 4.2. Let D be a distinguished 2-cell in X,
one common edge with D and let F be a 2-cell different than D and having at least
one common edge with E. Then w.o.p. E and F are regular 2-cells.

Proof. Suppose, on the contrary, that E is a distinguished 2-cell. Then let D′ and
E ′ be the 2-cells strongly adjacent to D and E respectively. By the assumption
we know that D′ 6= E and E ′ 6= D (otherwise D and E would be strongly adjacent). By Proposition 3.1 we know that D′ 6= E ′ . Therefore there are two pairs
of distinguished 2-cells {D, D′ } and {E, E ′ } which have at least one common edge.
Consider the diagram D consisting of 2-cells D, D′ , E, E ′ , glued in the way they
˜ ≤ 6. Note, that every diagram A consiste We will show that |∂D|
are glued in X.
˜ = 4. Gluing two
ing of two strongly adjacent 2-cells satisfies: |A| = 4 and |∂A|
such diagrams, consisting of disjoint sets of 2-cells, along one edge decreases the
˜ ≤ 6. Therefore, the diagram D violates
generalized boundary length by 2, so |∂D|
˜ ≥ |D|4(1 − 2d), so by Theorem 2.5 w.o.p. there is no such a
the inequality |∂D|
diagram D. Therefore E is a regular 2-cell.
Now suppose, on the contrary, that F is a distinguished 2-cell. Let F ′ be the
2-cell strongly adjacent to F . Again by Propistion 3.1, shows that F ′ 6= D, D′ 6= F
and F ′ 6= D′ . Moreover, from the previous part of the proof we know that with
w.o.p. E is a regular 2-cell, so F ′ 6= E. Hence, there is a diagram E, which is a
union of a pair {D, D′ } of strongly adjacent 2-cells, 2-cell E, and a second pair
of strongly adjacent 2-cells {F, F ′ }. Analogously as above, we can prove that E
˜ ≤ 8. Therefore the diagram E violates the inequality
satisfies: |E| = 5 and |∂E|
˜
|∂E| ≥ |E|4(1 − 2d), so by Theorem 2.5 w.o.p. there is no such a diagram E. Hence
F is a regular 2-cell.

Now, we introduce the notion of a diagram collared by hypergraph and path.
Definition 4.3. Let λ be a segment of a hypergraph (red, blue or standard) and
e (1) . Let D be a van Kampen diagram with the following
let γ be an edge-path in X
additional properties:
(1) λ passes only through external 2-cells of D
(2) every external edge of D belongs to the boundary of the carrier of λ or
belongs to γ.
We call D a diagram collared by hypergraph and path. After applying the procedure
of adding horns(see Definition 3.9) to D we obtain a diagram with horns collared
by hypergraph and path. We call λ a collaring hypergraph segment and γ a collaring
edge-path.
There is a definition of a diagram collared by hypergraphs and paths in [OW11,
Definition 3.11]. In the paper [OW11] this definition was stated for a general polygonal complex and for the hypergraphs that join antipodal midpoints of faces they
are passing through. Definition 4.3 is a modification of [OW11, Definition 3.11]: we

CUBULATING RANDOM GROUPS IN THE SQUARE MODEL

15

use it for l = 4, one path and one hypergraph segment, and for hypergraphs defined
in a different way, but the fact the hypergraph joins the antipodal midpoints is not
necessary to provide the proofs of upcoming lemmas. The proofs of lemmas from
[OW11] that we will use can be as well repeated for red and blue hypergraphs. The
following lemma is then a slight modification of [OW11, Lemma 3.17].
e and γ be an edge path in X
e (1) . Suppose,
Lemma 4.4. Let Λ be a hypergraph in X
that γ intersects Λ in two consecutive points x, y. Then there is a diagram with
horns collared by Λ and a segment of γ bounded by points x and y (here γ is an
edge path which starts and ends at“midedge vertices” corresponding to vertices of
Λ.
Proof. First we prove that there exists a diagram collared collared by Λ and a
segment of γ bounded by points x and y. The proof of this fact is analogous to
the proof of [OW11, Lemma 3.17]. Then we apply a procedure of adding horns
(Definition 3.9) to that diagram.

e (1) and let Λ be a hypergraph in X.
e
Lemma 4.5. Let γ be a geodesic edge-path in X
Suppose that there is a finite, nonempty geodesic segment γ ′ ⊂ γ, such that the first
and the last vertex of γ ′ lie in Car(Λ) but no other vertices of γ ′ lie in Car(Λ) and
no edge of γ ′ lie in Car(Λ). Then w.o.p. γ ′ has length 2, and there is the following
e
diagram D consisting of three 2-cells immersed in X:
γ′

Λ′
Figure 3. The diagram D.
Moreover, every 2-cell of D is a regular 2-cell.
Definition 4.6. A diagram D having the same shape as the one presented in Figure
4.5 will be called a house diagram. The geodesic segment γ ′ we be called a roof (of
a house diagram).
Proof. Let e0 , e1 be some edges dual to Λ with endpoints in the first and the last
vertex of γ ′ . By Lemma 4.4 we know that there is a diagram D with horns collared
by the edge-path {e0 , γ ′ , e1 } and a segment Λ′ of Λ. Suppose that the length of
this hypergraph segment equals k and the length of γ ′ equals l. Let k ′ denote the
number of horns in D. Note that
˜ ≤ k + k ′ + l + 2.
(4.1)
|∂D|
Note that every edge of γ ′ lies in the boundary of some 2-cell in D that is not in the
carrier of Λ, since otherwise there would be an inner vertex of γ ′ lying in Car(Λ).
Moreover, more than 2 edges of γ ′ cannot lie in the boundary of one 2-cell in D,

16

TOMASZ ODRZYGÓŹDŹ

since otherwise γ ′ would not be a geodesic. Therefore, there are at least
in D not lying in Car(Λ). Hence
 
l
′
.
(4.2)
|D| ≥ k + k +
2

l
2

2-cells

Moreover, l ≥ 2, because there is at least one vertex of γ ′ not lying in the carrier
of Λ and l ≤ k because γ is a geodesic. By Lemma 3.10 the number k + k ′ + l must
be even. Combining this with Theorem 2.5 gives the following system of conditions,
which is w.o.p. satisfied by k, k ′ and l:

(4.3)


 l 
8
′
′

k + k + l + 2 > 5 k + k + 2
l ≤ k, l ≥ 2, k ≥ 1 ⇐⇒ 2 ≤ l ≤ k


k + k ′ + l is an even number

Now we will find the possible values of l (see 4.3).
If l is even then we can rewrite the first inequality in (4.3) in form k + k ′ + l + 2 >
8
l
′
′
5 (k + k + 2 ). This is equivalent to 3(k + k ) < 10 + l. Combining this with the
second inequality in (4.3), that is l ≤ k, we obtain k < 5. Therefore l ≤ 4, since l
is even. Hence for even l possible solutions are: l = 4 and l = 2.
If l is odd then the first inequality in (4.3) becomes k +k ′ +l+2 > 85 (k +k ′ + l+1
2 ),
which is equivalent to 3(k + k ′ ) < l + 6. Combining this with l ≤ k we get k < 3.
Therefore l ≤ 1 since l is odd. This contradicts l ≥ 2. Hence, there are no solutions
with odd l.
First, consider the case, where l = 2. Then
8
k + k ′ + 4 > (k + k ′ + 1),
5
′
so k + k < 4. Combining this with the parity of k + k ′ + l we obtain that only
possible solution for l = 2 is k + k ′ = 2. Hence, there are two subcases to consider:
k ′ = 0 and k ′ = 1. If k ′ = 1 then the segment Λ′ consists of a distinguished 2-cell
c, which is strongly adjacent to some 2-cell c′ :
c′

A
c

B
Λ
γ′

D

C

Figure 4. The diagram D with one of possible hypergraphs Λ and
geodesic segments γ ′ .
The geodesic segment γ ′ joins vertices A and C or B and D, since otherwise γ
would not be geodesic. It can be easily seen that the 2-cell c′ also belongs to the
carrier of Λ. Therefore γ ′ cannot run along the boundary path of c′ , since it has at
least one vertex that lies outside the carrier of Λ. Hence, there must be at least one
˜ = 4 and |D| ≥ 3, which contradicts Theorem
more 2-cell in D. This gives us |∂D|
2.5.

CUBULATING RANDOM GROUPS IN THE SQUARE MODEL

17

The second subcase (of the case l = 2) is k ′ = 0 and k = 2. In that subcase
Car(Λ′ ) consists of two regular 2-cells (see Figure 5 a) ).
γ′
A

B

C

A

B

Λ′
F

E

C

Λ′
D

F

a)

E

D

b)
Figure 5. The diagram D.

Note, that γ ′ can join only vertices A with C or D with F , since in all other
cases γ ′ is either not a geodesic or intersects Λ, according to Lemma 3.15. After
relabelling vertices, we can always obtain a diagram D presented in Figure 5 b), as
desired. Moreover, every 2-cell in D is a regular 2-cell, since D does not have any
horns. There are exactly three 2-cells in D since by 2.5 there are no diagrams with
the boundary equal 6 consisting of more than three 2-cells.
Now, consider the case where l = 4. Then
8
k + k ′ + 6 ≥ (k + k ′ + 2),
5
so k + k ′ ≤ 4. We start with the subcase, where k + k ′ = 4. We know that
˜
|∂D| ≤ k + k ′ + l = 10 and |D| ≥ k + k ′ + 2l = 6. By Theorem 2.5 and the fact
˜ ≤ 10 we obtain that |D| = 6 and |∂D|
˜ = 10. Let C = D ∩ Car(Λ). The
that |∂D|
diagram D − C consists of two 2-cells, call them A and B. Note that all edges of γ ′
belong to A ∪ B. Therefore 2-cells A and B have no common edges, since otherwise
there will be no two points in A ∪ B within distance 4. This means, that there are
three vertices of γ ′ belonging to C. This contradicts our assumption on γ ′ so there
is no diagram with k + k ′ = 4 satisfying the assumptions of the Lemma 4.5.
Now consider the case, where k + k ′ = 2 and l = 4. If k + k ′ = 2 then the carrier
of Λ′ consists of maximally two 2-cells, so every pair of vertices in this carrier lies
in the distance dXe (1) equal at most 3. Therefore γ ′ cannot join any vertices of the
carrier of Λ′ . Hence, there is no diagram D with k + k ′ = 2 and l = 4.
There are no other possibilities, because of the parity of k + k ′ + l.

Definition 4.7. Let λ be a segment of a hypergraph. A diagram consisting of
two strongly adjacent 2-cells, such that λ passes through this pair will be called a
divided tile (of λ) we. A 2-cell in the carrier of λ that is not a regular 2-cell but
is not an element of a divided tile of λ will be called an isolated 2-cell. A tile is a
divided tile or a regular 2-cell.
Lemma 4.8 (hypergraphs do not osculate). Let Λ′ be a hypergraph segment in
e (1) . Suppose that one of the following conditions is satisfied
X

18

TOMASZ ODRZYGÓŹDŹ

a) Λ′ is a segment of a red hypergraph and there are no isolated red 2-cells of Λ′ ,
b) Λ′ is a segment of a blue hypergraph and there are no isolated blue 2-cells of Λ′ ,
c) Λ′ is a segment of a standard hypergraph and there is no divided tile of Λ′ .
Then w.o.p. holds
(1) For every vertex v of Car(Λ′ ) there is only one edge in Car(Λ′ ) ending in
v, dual to Λ′ that is not an internal edge of a divided tile (the situation
presented in Figure 6 a) does not occur). In other words: if there is a
vertex in Car(Λ′ ) being the endpoint of two edges dual to Λ′ then one of
these edges must be an internal edge of a divided tile.
e (1) such that its vertices lie in Car(Λ′ ) but e does
(2) There is no edge e in X
′
not lie in Car(Λ ), see Figure 6 b).

c1 v
c2

e

a)

b)

Figure 6. Two types of hypergraphs osculations.
Proof. (1) Suppose, on the contrary, that such a point v exists. Then let e1 , e2 be
the two edges, ending in v that are dual to the hypergraph segment Λ′ and that are
none of them is an internal edge of a divided tile. Let D be a diagram collared by
˜ ≤ |D| + 2. Therefore, by
Λ′ and an edge-path {e1 , e2 }. Such diagram satisfies |∂D|
˜
Theorem 2.5 we obtain |D| ≤ 3. Hence |∂D| ≤ 5, and combining this with Lemma
˜ ≤ 4. This by Theorem 2.5 gives us that that |D| ≤ 2. A
3.10 we get that |∂D|
diagram consisting of two 2-cells and having the generalized boundary length at
most 4 must be a pair of strongly adjacent 2-cells. This ends the proof in the case
c). If Λ′ is red or blue hypergraph we need to provide further argument. Note,
that both red and blue hypergraph join the antipodal midpoints of bundary edges
of every tile. Hence, there are no two edges that are dual do Λ′ , have common end
and non of them is an internal edge of a divided tile. This ends the proof in cases
a) and b).
Therefore there is a blue 2-cell and a red 2-cell in the carrier of Λ′ , which contradicts assumptions a), b) and c).
(2) Let v1 and v2 be the ends of the edge e. For i = 1, 2 let ei be the edge
dual to Λ′ ending in vi that is not an internal edge of a divided tile. Let E be a

CUBULATING RANDOM GROUPS IN THE SQUARE MODEL

19

diagram with horns collared by Λ′ and the edge-path {e1 , e, e2 }. As previously, E
satisfies |∂E| ≤ |E| + 2. Therefore by 2.5 |E| ≤ 3, so |∂E| ≤ 5. By Lemma 3.10 we
obtain that in fact |∂E| ≤ 4, which, by previous observation, means that |E| ≤ 2.
A diagram with two 2-cells and the boundary length equal 4 must be a pair of
strongly adjacent 2-cells. In a diagram which is a pair of strongly adjacent 2-cells
there is no edge which does not lie in Car(Λ) but its endpoints do. This end the
proof in cases a), b) and c).

e (1)
Lemma 4.9. Let Λ1 be a hypergraph segment and γ be a geodesic segment in X
that intersects Λ1 in two points, which are the endpoints of γ. Let Λ2 6= Λ1 be a
e intersecting γ in point x.
hypergraph in X
(1) Λ1 and Λ2 pass through a common 2-cell cx , that is Car(Λ1 )∩Car(Λ2 ) ⊇ cx .
(2) If moreover Λ2 intersects γ in two different points x and y that do not lie
in the boundary of the same 2-cell of Car(Λ1 ) then there are two different
2-cells in Car(Λ1 ) ∩ Car(Λ2 ).
Proof. Part (1) Let e be an edge of γ dual to Λ2 . There are two possibilities
• The edge e lies in the boundary of a 2-cell c ∈ Car(Λ1 ). In that case Λ2 is
dual to the boundary edge of c, so cx := c belongs to Car(Λ2 ). See Figure
7 a).
• The edge e does not lie in the boundary edge of a 2-cell c ∈ Car(Λ1 ). Since
γ is a geodesic edge-path, by Lemma 4.5 combined with Lemma 4.8 we
know that e lies in the boundary of a house diagram presented in Figure 7
b). It is clear from the Figure 7 b) that cx ∈ Car(Λ1 ) ∩ Car(Λ2 ).
Part (2). If x and y lie in the boundaries of distinct 2-cells cx and cy belonging
to Car(Λ) then it is clear that cx and cy both lie in Car(Λ1 ) ∩ Car(Λ2 ) (see Figure
7.
Consider the case where x lies in the boundary of a 2-cell c1 in Car(Λ1 ) and
y do not. Considering a hypergraph Λ1 dual to γ passing through y we will find
(as in part (1) ) a regular 2-cell c2 that lies in Car(Λ1 ) ∩ Car(Λ2 ) and that there
is no edge of γ in the boundary of c2 . Hence c2 6= c1 and c1 and c2 both lie in
Car(Λ1 ) ∩ Car(Λ2 ).
The last case to consider is when neither x nor y lie in the boundary of Car(Λ1 ).
First, note that x and y cannot lie in the roof of the same house diagram since
then there would be a self intersection of Λ2 (see Figure 7 b) ) which contardicts
Theorem 3.7. Hence, x and y lie in the roofs of different house diagrams, which
means that one 2-cell from each of those diagrams belongs to Car(Λ1 ) ∩ Car(Λ2 ).
This means that there are at least two different 2-cells in Car(Λ1 ) ∩ Car(Λ2 ).

e Let γ be a geodesic edge-path in the
Lemma 4.10. Let Λ be a hypergraph in X.
e Suppose that γ intersects Λ in two consecutive points x and y. Let
1-skeleton of X.
Λxy be the segment of Λ joining x and y. Then:
(1) if Λ is a red hypergraph, there is an isolated red 2-cell c of Λxy ,
(2) if Λ is a blue hypergraph, there is an isolated blue 2-cell c of Λxy ,
(3) if Λ is a standard hypergraph, there is a divided tile of Λxy , such that the
none of its internal edges belong to γ.
Proof. The proof relies on the idea, that if a geodesic crosses a hypergraph two
times it must be worthwile in terms of distance. If the hypergraph does not “turn”

20

TOMASZ ODRZYGÓŹDŹ

cx

cx
Λ1

γ

e

Λ2

γ

Λ1

x
y

x
e

a)
b)

Figure 7. Intersections of hypergraphs Λ1 and Λ2 .
there is no reason for a geodesic to cross it two times. A colored hypergraph can
“turn” only if there is an isolated 2-cell of the segment of hypergraph and a standard
hypergraph “effectively turns” when meeting a pair of strongly adjacent 2-cells. Let
now state a precise argument.
First, consider the case where Λ is a red hypergraph. Suppose, on the contrary,
that there is no isolated red 2-cell of Λxy . The the carrier of Λxy consists only
of tiles (regular 2-cells or divided tiles) and every edge of Λxy joins an antipodal
midpoints of boundary edges of every tile in Car(Λ′ ) i.e. the carrier of Λ′ has the
shape illustrated in Figure 8.
γ
x′
x
x′′

Λ′

...

y′
y
y ′′

k
Figure 8. The diagram collared by Λxy and γ.
e containing x, and suppose that
Let x′ and x′′ be the two ends of the edge of X
′
′′
e
x lies on γ between x and y. Let y and y be the two ends of the edge of X
′
′
containing y, and suppose that y lies on γ between x and y. Let γ0 be the subpath
of γ joining x′ and y ′ (see Figure 8). Let V be the set of vertices of γ ′ . Define
′

V ′ = {v ∈ V |there is at least one edge of γ ′ ending in v and not belonging to Car(Λ′ )}.
For each pair s, t of two consecutive vertices in V ′ consider the subsegment of
′
′
γ joining s and t and denote it by γst
. By Lemma 4.8 part (2) we obtain that γst
either
(1) lies in the boundary of the carrier of Λ, or
(2) has a length at least 2.
′
In the latter case, we know that γst
is a roof of a house diagram. Therefore
′
without change of the total length of γ ′ we can replace γst
with an edge-path of
length 2, that lies in the boundary of Car(Λxy ) and does not cross Λxy .
Hence, we can modify γ ′ to a path having the same length such that all its edges
lie in the boundary of Car(Λxy ). From now γ ′ denotes modified path. For every
′

CUBULATING RANDOM GROUPS IN THE SQUARE MODEL

21

vertex v of γ ′ denote by ev the edge dual to Λ′ ending in v that is not an internal
edge of a divided tile (this definition is unambiguous according to Lemma 4.8 part
(1) ). We will prove now that the length d of γ ′ equals the number k of tiles of
Λxy . Every edge of γ ′ lies in the boundary of exactly one tile so k ≥ d. Suppose,
on the contrary, that k > d. This means that there must be a vertex of γ ′ that is
a common vertex of more than two tiles. But in that case there are at least two
edges dual to Λxy that are not internal edges of a divided tile. This contradicts
e joining x′′
Lemma 4.8 part 1). Hence k = d. Consider now the edge-path γ ′′ in X
′′
and y and goes along the boundary of Car(Λxy ). The length of this edge-path is
not greater then k since every tile of Λxy shares at most one boundary edge with
γ ′′ . Hence there exists an edge-path joining x′′ and y ′′ of length k. Note that the
segment of γ joining x′′ and y ′′ has length k + 2. This contradicts the fact that γ
is a geodesic.
If Λ′ is a blue hypergraph the proof is analogous.
Consider now the case, where Λ is a standard hypergraph. In that case we can
provide an analogous argument to prove that there must be a divided tile of Λxy .
We only need to prove that none of the internal edges of a divided tile belong to γ.
Suppose, on the contrary, that this is the case.
By Lemma 4.4 there exists a planar diagram D collared by Λxy and γ. By
definiton of a diagram collared by a hypergraph and path γ cannot contain any
internal edge of D which ends the proof.

The definition of a 2-collared diagram in case of standard hypergraphs can be
found in [OW11, Subsection 3.3]. In a nutshell this is a diagram collared by two
hypergraphs (see Definition [OW11, Lemma 3.17]). Let us state this definition for
a case of general hypergraphs.
Definition 4.11 (2-collared diagram). Let λ1 and λ2 be two hypergraph segments.
Let D be a van Kampen diagram with the following additional properties:
(1)
(2)
(3)
(4)

There are two external 2-cells of D called corners
λ1 and λ2 pass only through external 2-cells of D
every external edge of D belongs to Car(λ1 ) ∪ Car(λ2 )
corners are the only 2-cells of D containing the edges of both hypergraph
segments λ1 and λ2 .

We call D 2-collared diagram (collared by λ1 and λ2 ).
Lemma 4.12 (reformulation of [OW11, Theorem 3.12]). Suppose, Λ1 and Λ2 are
e and that they intersect at least
distinct hypergraphs that are embedded trees in X,
twice. Let c be a common 2-cell of Car(Λ1 ) and Car(Λ2 ) Then there exists a 2collared diagram collared by segments Λ1 and Λ2 . Moreover we can choose c to be
one of its corners.
There is a definition of a 2-collared diagram in the beginning of [OW11, Section
3.11]. However this is the special case of the general definition of a diagram collared
by hypergraphs and paths that was stated for a general polygonal complex and for
the standard hypergraphs. Definition 4.11 is a modification of it: we use it for l = 4
and for general hypergraphs, but the fact that the hypergraph joins the antipodal
e is not necessary to provide the proof of Lemma 4.12, in
midpoints of edges in X
fact the proof can be provided, as well, in the case of colored hypergraphs.

22

TOMASZ ODRZYGÓŹDŹ

Figure 9. 2-collared diagram. Collaring segments are indicated
with thick lines.
e is a pair of strongly adjacent
Lemma 4.13. W.o.p. every 2-collared diagram in X
2-cells.

Proof. Let D be a 2-collared diagram (with horns) collared by hypergraphs Λ1 and
Λ2 . Let k1 be the length of the collaring segment of Λ1 and k2 be the length of
the collaring segment of Λ2 . Let h denote the number of horns in D. Each pair
of strongly adjacent 2-cells gives a contribution to the generalized boundary length
˜ ≤ k1 + k2 + h. There are two 2-cells in Car(Λ1 ) ∩ Car(Λ2 ), so
equal 2, hence |∂D|
3
|D| ≥ k1 + k2 + h − 2. Hence, by Theorem 2.5 for the density d < 10
we obtain
that w.o.p.:
˜ > 8 |D| > 8 (k1 + k2 + h − 2).
k1 + k2 + h ≥ |∂D|
5
5
˜ is even. Therefore
Hence k1 + k2 + h ≤ 5. By Lemma 3.10 we know that |∂D|
˜
|∂D| ≤ 4 and by (4.4) we obtain |D| ≤ 2. Hence, D must be a diagram consisting
of two strongly adjacent 2-cells.

(4.4)

Lemma 4.14. The following statement holds w.o.p.: Let Λ1 and Λ2 be two hypere Suppose that Λ1 and Λ2 intersect transversally in a 2-cell c, meaning
graphs in X.
that Car(Λ1 ) ∩ Car(Λ2 ) contains a regular 2-cell c and that Λ1 ∩ c 6= Λ2 ∩ c. Then Λ
and Λ′ intersect only once. Moreover c is the only one 2-cell in Car(Λ1 ) ∩ Car(Λ2 ).
Proof. Suppose, on the contrary, that there is another point of intersection. Then
by Lemma 4.12 there is a 2-collared diagram with horns D collared by Λ1 and Λ2
and containing c. By Lemma 4.13 we know that every 2-cell of D is distinguished,
so this is a contradiction with the assumption that c is regular.
Now suppose, on the contrary, that there is a 2-cell d ∈ Car(Λ1 ) ∩ Car(Λ2 ) such
that d 6= c. We know that there is only one point of intersection of Λ1 and Λ2 , so
the only possibility is that d is a distinguished 2-cell of some color, and Λ1 and Λ2
are both hypergraphs of this color (see Figure 10).
But then Λ1 and Λ2 intersect in the middle of the 2-cell strongly adjacent to d,
so there are two points of intersection of Λ1 and Λ2 , which is a contradiction.


CUBULATING RANDOM GROUPS IN THE SQUARE MODEL

Λ1

23

c
Λ2
d

Figure 10. Two 2-cells in Car(Λ1 ) ∩ Car(Λ2 ).
e (1) . Let e be an edge in γ, and
Lemma 4.15. Let γ be a geodesic edge-path in X
denote by s its midpoint. Then either:

(a) There is a hypergraph intersecting γ only in the point s.
(b) There is a hypergraph Λ such that its segment Λsx starting in s intersects γ
in two consecutive points: s and x such that there are at least two not sharing
an edge distinguished 2-cells in Λsx and Λ does not intersect γ anywhere else
between points s and x.

Proof. If one of the hypergraphs (red, blue or standard) dual to the edge e intersects γ only once, the statement is satisfied. Hence, consider the case where all
hypergraphs dual to the edge e intersect γ at least twice. Denote by x, y and z the
e (1) ), in which three hypergraphs
nearest points to s (in the edge-path metric in X
x
y
z
Λ , Λ and Λ dual to the edge e intersect γ. A priori, it may happen that some of
these points are equal. Without loss of generality, we can assume that x and y lie
in the same connected component of γ − s and that x is at least as far from s as y.
Now, we will prove that y 6= x. Suppose, on the contrary, that x = y. This
means that every time segments Λsx and Λsy split, they also rejoin at some point,
since they end in the same point. Every situation where Λsx and Λsy split an rejoin
gives us a 2-collared diagram collared by a subsegments of Λsx and Λsy . By Lemma
4.14 every 2-collared diagram is a pair of strongly adjacent 2-cells. This means that
if Λsx and Λsy split they rejoin in the next 2-cell of the common carrier, see Figure
11. This means that Car(Λsx ) = Car(Λsy ) and that distinguished 2-cells Car(Λsx )
occur only in strongly adjacent pairs.
blue
2-cell

red 2-cell

Λred
Λblue

Figure 11. The only possible way of splitting and rejoining of Λx
and Λy .
One of the hypergraphs Λx and Λy is red or blue, so by Lemma 4.10 in the carrier
of Λsx exists an isolated distinguished 2-cell, so this is a contradiction. Therefore
y 6= x.

24

TOMASZ ODRZYGÓŹDŹ

Therefore, y lies on a geodesic edge-path that intersects Λsx twice. Hence, by
Lemma 4.5 we know that y lies in the boundary of the carrier of Λsx (see Figure
12 a) or y lies the boundary of the house diagram F presented in Figure 12 b).
c

c1

Λy

c2

Λx
γsx

Λx

y
γsx

y
F

a)

b)

Figure 12. Two possible locations of y.
The hypergraphs Λx and Λy cannot intersect transversely in a regular 2-cell c1 ,
since otherwise by Lemma 4.14 they would intersect only once in the middle of
c1 , and we know that they intersect also in s. Hence y lies in the boundary of a
distinguished 2-cell cy ∈ Car(Λsx ). Therefore the carriers of the segments Λsx and
Λsy share a common distinguished 2-cell cy .
Without loss of generality, we can suppose that cy is red (if it is blue the argument
is analogous).
If Λx or Λy is blue then, according to Lemma 4.10, its carrier contains an isolated
blue 2-cell cb , so cb does not share an edge with cy . In that case the carrier of Λx
or Λy contains a red 2-cell cy and some non-adjacent by an edge to it blue 2-cell cb ,
so we are done.
The only cases left to consider are:
(1) Λy is a red hypergraph and Λx is a standard hypergraph
(2) Λx is a red hypergraph and Λy is a standard hypergraph.
First consider the situation 1). If there are at least two red 2-cells in the carrier
of Λsx , we are done. Hence, we can suppose that cy is the only isolated red 2-cell
in the carrier of Λsx . In that case Car(Λsx ) has the shape presented in Figure 13.
We know that y lies in the boundary of cy and y does not belong to Λsx . Hence
y = y1 or y = y2 . Recall that points s, x and y lie on γ. If y = y2 then there is
a segment of standard hypergraph bounded by s and y intersecting γ twice at its
ends, such that there is only one distinguished 2-cell in its carrier. This contradicts
Lemma 4.10 (3). If y = y2 we obtain analogous contradiction. Hence there must
be at least one more isolated red 2-cell in the carrier of Λsx , so we are done, since
two red 2-cells cannot share an edge.
Now consider situation 2), that is Λx is a standard hypergraph and there is only
one divided tile of Λsx and y belongs to this divided tile. In that case Car(Λsx ) has
the shape presented in Figure 14. We know that y lies in the boundary of cy but
y does not belong to Λsx . Moreover by 4.10 part (3) we know that y does not lie
on an internal edge of a divided tile. Hence y = y3 or y = y4 . If y = y3 then there
is a segment of a red hypegraph bounded by x and y intersecting γ twice with no
isolated red 2-cell in its carrier. This contradicts Lemma 4.10 part (1). If y = y4

CUBULATING RANDOM GROUPS IN THE SQUARE MODEL

25

y1
s

Λsx

...

y2

x
Figure 13. The carrier of Λsx in case where Λx is red.
y3
s

Λsx

...

y4

x
Figure 14. The carrier of Λsx in case where Λx is standard hypergraph.
we obtain the contradiction analogously. Hence, there must be at least two not
sharing an edge 2-cells in the carrier of Λsx .

e of length at
Theorem 4.16. Let γ be a geodesic edge-path in the 1-skeleton of X
least 21. Let E := {e−7 , e−6 , . . . , e0 , . . . , e7 } be the set of 15 consecutive edges of
e intersecting γ exactly once and such that this
γ. Then there is a hypergraph in X
intersection is the midpoint of one of the edges in E.

Proof. Denote the midpoint of the edge e0 by s. If one of the hypergraphs dual to
the edge e0 intersects γ only once, we are done. If not, by Lemma 4.10 we know
that there exists a hypergraph Λ, such that its segment Λsx intersects γ in two
consecutive points of γ: s and x and that the segment Λsx contains at least two
not sharing an edge distinguished 2-cells: ⌈1 and ⌈2 . We will consider two cases:
(1) There are at least seven 2-cells in Car(Λsx )
(2) There are at most six 2-cells in Car(Λsx ).
We will use slightly different methods to deal with each of these two cases.
4.1. Case 1: There are at least seven 2-cells in Car(Λsx ). Let c1 , c2 , c3 be
the 3-th, 4-th and 5-th 2-cells in Λsx respectively counted from s. According to
Lemma 4.2 at least one of them must be a regular 2-cell, call it c. Denote by Λc

26

TOMASZ ODRZYGÓŹDŹ

the standard hypergraph passing through 2-cell c and dual to Λ. By Lemma 4.14
Λc and Λ intersect only once. We will prove two assertions:
(a) Λc intersects some edge in E.
(b) Λc intersects γ exactly once.
We start with the proof of assertion (a). Let us resolve where is the point of
intersection of γ and Λc . If there is an edge ec of γ lying in the boundary of c then
Λc and γ intersect in the midpoint of ec . In this case denote by xc the midpoint of
e (1) that goes along the
ec , see Figure 15 a). In that case there is an edge-path in X
boundary of Car(Λ) of length at most 6, because there are at most five 2-cells in
Car(Λsx ) between s and c. Hence dγ (s, xc ) ≤ 6.
If there is no edge of γ lying in the boundary of c then, by Lemma 4.5 we know
that the 2-cell c lies in the house diagram presented in Figure 15 b) so Λc intersects
the edge ec from Figure 15 b). In that case we denote by the xc the midpoint of
e (1) that goes along the boundary of
ec . In this situation, there is an edge-path in X
Car(Λ) and a boundary of a house diagram containing c of length at most 7, because
there are at most five 2-cells in Car(Λsx ) between s and c. Hence dγ (s, xc ) ≤ 7.
This ends the proof of assertion (a).
c

c

Λc

Λc

Λ
γ

Λ

ec xc
γ

xc
ec

a)

b)

Figure 15. Two possible ways of intersection of Λc and γ
Now we will prove assertion (b). By Lemma 3.15 there are exactly two cone − Λ. Hence, we can split Λc into two parts:
nected components of X
e − Λ containing
• Λ+ which is the intersection of Λc with the component of X
xc
e − Λ not con• Λ− which is the intersection of Λc with the component of X
taining xc .

We will show that Λ− does not intersect γ and that Λ+ intersects γ only once
(in the point xc ).
Firstly, consider Λ+ . Suppose, on the contrary, that Λ+ intersects γ in some
point yc 6= xc . Suppose that yc is the nearest among what point to xc in the metric
dγ . Points xc and yc cannot both lie in the boundary of c since there is at most
one common edge of c and γ.
We will consider three cases:
(1) yc belongs to the segment γsx of γ bounded by s and x, , see Figure 16 (1)
(2) yc does not belong to γsx and points xc and yc lie in the different connected
e − Λ, , see Figure 16 (2)
components of X

CUBULATING RANDOM GROUPS IN THE SQUARE MODEL

27

(3) yc does not belong to γsx and points xc and yc lie in the same connected
e − Λ. , see Figure 16 (3)
component of X
Λ−

Λ
(1)

γ

s

c
yc

xc

x

Λ+
Λ−
Λ
(2)

γ

c

s

xc

x

yc

Λ+
Λ−
Λ
(3)

γ

s

c
z2
xc

z1

yc

Λ+
Figure 16. Intersections of Λ+ and γ.
1)If yc belongs to the segment γsx of γ bounded by s and x. Then by Lemma
4.9 applied to Λ1 = Λ and Λ2 = Λc we obtain that there are two common 2-cells of
the carriers of Λ and Λc , which is a contradiction with Lemma 4.14.
e − Λ then
2) If points xc and yc lie in the different connected components of X
there is an intersection of Λ+ which contradicts the fact that Λ and Λc intersect
only once ( Lemma 4.14).
e − Λ then Λ
3) If points xc and yc lie in the same connected component of X
intersects γsx at least twice in some points z1 , z2 .
If this two points do not lie in the boundary of the same 2-cell c′ in Car(Λc ) then
′
c 6= c. By Lemma 4.9 applied for Λ1 = Λc and Λ2 = Λ we obtain that there are
two different 2-cells in Car(Λ) ∩ Car(Λc ), which contradicts Lemma 4.14. If z1 and
z2 lie in the boundary of the same 2-cell c′ in Car(Λc ) then we know, that c′ 6= c,
since c shares at most one edge with γ. Hence, c′ , c ∈ Car(Λc ) ∩ Car(Λ), which
again contardicts 4.14. Hence, we proved that Λ+ does not intersect γ.
Let us now consider Λ− . Suppose, on the contrary, that Λ− intersects γ. Let tc
be the point of the intersection of Λ− and γ, which is the nearest to the point xc

28

TOMASZ ODRZYGÓŹDŹ

in the edge-path metric on Λ− (see Figure 17). Note, that tc lies in the connected
e − Λ not containing xc , since otherwise there will be a second
component of X
intersection of Λ and Λc which is not allowed, according to Lemma 4.14.

Λ−

Λ
γ
tc

c

s

xc

x

Λ+

Figure 17. Intersection of Λ− and γ
Let Λ′− be the hypergraph segment of Λc bounded by the points xc and tc . One
of the points {x, s} lies on γ between points xc and tc . Suppose first that this point
is s.
Since s lies on the geodesic segment, that intersects Λc twice, by Lemma 4.5 we
have two possibilities: s lies on the boundary of the 2-cell c (see Figure 18 a) ) or
s lies in the diagram presented in Figure 18 b).
c

c

Λ

Λ

Λc
γ

Λc

x
γ
a)

x

b)

Figure 18. Two possible locations of x
Note, that in both cases the segment of Λ joining the point s and the 2-cell
c consists of at most one 2-cell, which, if occurs, is a regular 2-cell. Remember
that between s and x in Car(Λ) was at least seven 2-cells and c is 3-rd, 4-th or
5-th of them. Hence there must be a least two 2-cells between c and s. This is a
contradiction, so Λ− does not intersect γ.
If x lies on γ between xc and tc the reasoning is analogous. This ends the proof
in Case 1.

CUBULATING RANDOM GROUPS IN THE SQUARE MODEL

29

4.2. Case 2: There are at most six 2-cells in Car(Λsx ). Now let us consider
the case, where there are at most six 2-cells in the carrier of Λsx . Let c be any
regular 2-cell in the carrier of Λsx that lies between ⌈1 and ⌈2 (recall that ⌈1 and
⌈2 were two not sharing an edge distinguished 2-cells in the segment Λsx ). Again,
we denote by Λc the hypergraph passing through c and dual to Λsx . Analogously
we state two assertions:
(a) Λc intersects some edge of the set E.
(b) Λc intersects γ exactly once.
To prove assertions (a) and (b) we first define the point xc as in Case 1.
Proof of assertion (a) is analogous as in Case 1.
Now, consider assertion (b). Again, we split Λc into two connected components:
e − Λ containing
• Λ+ which is the intersection of Λc with the component of X
xc
e − Λ not con• Λ− which is the intersection of Λc with the component of X
taining xc .

To prove that Λ+ intersects γ only once we can repeat the argument from Case
1.

Consider now Λ− . Suppose, on the contrary that Λ− intersects γ in a point
e − Λ not containing xc , so
tc . Note that tc lies in the connected component of X
the geodesic segment of γ bounded by xc and tc contains x or s. Without loss of
generality we can assume that this geodesic segment contains x.
Let Λ′− be the hypergraph segment of Λc bounded by the points xc and tc . The
same reasoning, as in previous case, shows that there is at most one 2-cell in Car(Λ)
between c and x, which, if occurs, is a regular 2-cell. This is a contraction since c
lies in Car(Λ) between two distinguished 2-cells, so there must be a distinguished
2-cell in Car(Λ) between c and x.

Thorem 4.1 is an immediate consequence of Theorem 4.16.
References
[Ago13] Ian Agol, The virtual Haken conjecture, Doc. Math. 18 (2013), 1045–1087. With an
appendix by Agol, Daniel Groves, and Jason Manning.
[KK13] Marcin Kotowski and Michał Kotowski, Random groups and property (T ): Żuk’s theorem revisited, J. Lond. Math. Soc. (2) 88 (2013), no. 2, 396–416.
[CMV04] Pierre-Alain Cherix, Florian Martin, and Alain Valette, Spaces with measured walls,
the Haagerup property and property (T), Ergodic Theory Dynam. Systems 24 (2004),
no. 6, 1895–1908.
[CN05] Indira Chatterji and Graham Niblo, From wall spaces to CAT(0) cube complexes, Internat. J. Algebra Comput. 15 (2005), no. 5-6, 875–885.
[Oll05] Yann Ollivier, A January 2005 invitation to random groups, Ensaios Matemáticos
[Mathematical Surveys], vol. 10, Sociedade Brasileira de Matemática, Rio de Janeiro,
2005.
, Some small cancellation properties of random groups, Internat. J. Algebra
[Oll07]
Comput. 17 (2007), no. 1, 37–51.
[Gro93] M. Gromov, Asymptotic invariants of inﬁnite groups, Geometric group theory, Vol. 2
(Sussex, 1991), London Math. Soc. Lecture Note Ser., vol. 182, Cambridge Univ. Press,
Cambridge, 1993, pp. 1–295.
[Oll07] Yann Ollivier, Some small cancellation properties of random groups, Internat. J. Algebra Comput. 17 (2007), no. 1, 37–51.

30

TOMASZ ODRZYGÓŹDŹ

[Oll04] Y. Ollivier, Sharp phase transition theorems for hyperbolicity of random groups, Geom.
Funct. Anal. 14 (2004), no. 3, 595–679.
[OW11] Yann Ollivier and Daniel T. Wise, Cubulating random groups at density less than 1/6,
Trans. Amer. Math. Soc. 363 (2011), no. 9, 4701–4733.
[MP15] John M. Mackay and Piotr Przytycki, Balanced walls for random groups, Michigan
Math. J. 64 (2015), no. 2, 397–419.
[Odr16] Tomasz Odrzygóźdź, The square model for random groups, Colloq. Math. 142 (2016).
, Nonplanar isoperimetric inequality for random groups, Note, aviable at:
[Odr14]
http://students.mimuw.edu.pl/∼to277393/web/ﬁles/nonplanar.pdf (2014).
Institute of Mathematics, Polish Academy of Sciences, Warsaw, Śniadeckich 8
E-mail address: tomaszo@impan.pl

