A SHARP THRESHOLD FOR COLLAPSE
OF THE RANDOM TRIANGULAR GROUP

arXiv:1403.3516v2 [] 18 Nov 2016

SYLWIA ANTONIUK, EHUD FRIEDGUT, AND TOMASZ LUCZAK
Abstract. The random triangular group Γ(n, p) is the group
given by a random group presentation with n generators in which
every relator of length three is present independently with probability p. We show that in the evolution of Γ(n, p) the property of
collapsing to the trivial group admits a very sharp threshold.

1. Introduction
Let P = hS | Ri denote a group presentation, where S is the set
of generators and R is the set of relators. A group generated by a
presentation P is called a triangular group if R consists of cyclically
reduced words of length three over the alphabet S ∪ S −1 , that is if
R consists of words of the form abc such that a 6= b−1 , b 6= c−1 and
c 6= a−1 . Here we consider the random triangular group Γ(n, p) deﬁned
as a group given by a random triangular group presentation with n
generators and such that each cyclically reduced word of length three
over the alphabet S∪S −1 is present in R independently with probability
p = p(n).
We study the asymptotic properties of the random triangular group
when the number of generators n goes to inﬁnity. Thus, for a group
property P and a function p(n), we say that Γ(n, p(n)) has P asymptotically almost surely (a.a.s.), if the probability that Γ(n, p(n)) has
this property tends to 1 as n → ∞.
The notion of the random triangular group was introduced by Żuk
[11]. In particular, he showed that for every constant ǫ > 0, if p ≤
n−3/2−ǫ , then a.a.s. Γ(n, p) is an inﬁnite, hyperbolic group, while for
p ≥ n−3/2+ǫ , a.a.s. Γ(n, p) collapses to the trivial group (his result
is stated for a somewhat diﬀerent, yet equivalent, model of random
triangular group). Antoniuk, Luczak and Świa̧tkowski [2] improved
this result from one side and showed that there exists a constant C > 0
Date: March 13, 2014.
2010 Mathematics Subject Classification. Primary: 20P05; secondary: 05C80,
20F05.
Key words and phrases. random group, collapse, sharp threshold, torsion-free.
Sylwia Antoniuk is partially supported by NCN grant 2013/09/N/ST1/04251,
Ehud Friedgut is supported in part by I.S.F. grant 0398246, and BSF grant 2010247,
and Tomasz Luczak is partially supported by NCN grant 2012/06/A/ST1/00261.
1

2

SYLWIA ANTONIUK, EHUD FRIEDGUT, AND TOMASZ LUCZAK

such that for p ≥ Cn−3/2 a.a.s. Γ(n, p) collapses to the trivial group.
They also asked if there exists a constant c > 0 such that for p < cn−3/2
a.a.s. Γ(n, p) is inﬁnite.
Note that the property that a group is trivial is monotone, i.e. if
hS | Ri is trivial then for any R′ ⊇ R the group hS | R′ i is trivial
as well. Hence, by a well known argument of Bollobás and Thomason [3], there exists a ‘coarse’ threshold function for collapsibility i.e.
there exists a function θ(n) such that if p(n)/θ(n) → 0, then a.a.s.
Γ(n, p) is non-trivial, whereas for p(n)/θ(n) → ∞ a.a.s. Γ(n, p) collapses to the trivial group. However, the result of Antoniuk, Luczak
and Świa̧tkowski [2] and their conjecture we have just mentioned suggest that Γ(n, p) collapses more rapidly, i.e. that the collapsibility has
a ‘sharp’ threshold. Our main result states that this is indeed the case.
Theorem 1. Let h(n, p) denote the probability that Γ(n, p) is trivial.
There exists a function c̃(n) such that for any ǫ > 0,
lim h(n, (1 − ǫ)c̃(n)n−3/2 ) = 0 and lim h(n, (1 + ǫ)c̃(n)n−3/2 ) = 1.

n→∞

n→∞

Unfortunately, the argument we use does not give any information
on the asymptotic behaviour of c̃(n). Nonetheless we strengthen the
conjecture from [2] and predict that c̃(n) tends to a limit.
Conjecture. There exists a constant c > 0 such that for every constant
ǫ > 0 the following holds.
(i) If p ≤ (c − ǫ)n−3/2 , then a.a.s. Γ(n, p) is infinite and hyperbolic.
(ii) If p ≥ (c + ǫ)n−3/2 , then a.a.s. Γ(n, p) is trivial.
As we have already remarked it was shown in [2] that
lim sup c̃(n) < ∞ .
Although we cannot verify the conjecture and prove that
lim inf c̃(n) > 0,
we show however that c̃(n) cannot tend to 0 too quickly.
Theorem 2. Let ω and p be functions of n such that ω(n) → ∞ as
n → ∞, and
1/3
p(n) = n−3/2−ω/ log n .
Then a.a.s. Γ(n, p) is infinite, torsion-free, and hyperbolic.
The structure of the paper is the following. In the next section
we prove Theorem 1. The argument is based on a result of the second
author [6] which, up to our knowledge, has never been used to show that
properties of random groups have sharp thresholds. It states, roughly,
that if a property does not admit a sharp threshold then it is ‘local’,
i.e. its probability can be signiﬁcantly changed by a local modiﬁcation
of the random structure (see Lemma 3 below). We show that it is not
the case with the collapsibility. In particular, we show that adding

COLLAPSE OF RANDOM TRIANGULAR GROUP

3

to R a few more specially selected relators aﬀects the probability of
collapsing less than a tiny increase of the probability p, which in turn
corresponds to adding to R a small number of random relators. Hence,
a local modiﬁcation of the random structure cannot have large impact
on the probability of the property in question.
Then we prove Theorem 2. We follow closely the argument of Ollivier
who in [8] showed that the assertion holds for some function p(n) =
n−3/2+o(1) . This result was initially stated by Gromov [5] however it
seems that Ollivier was the ﬁrst one who gave a complete proof of this
statement. We basically rewrite Ollivier’s argument (who, following
Żuk, used a slightly diﬀerent model of the random triangular group)
to replace o(1) in the power by some explicit function.
2. Proof of Theorem 1
As mentioned in the introduction, the tool we use in order to prove
the sharpness of the threshold, as expressed in Theorem 1, is a result
from Friedgut [6]. In [6] the author gives a general necessary condition
for a property to have a coarse threshold, namely that it can be well
approximated by a local property. Although the main theorem in that
paper refers to graphs, the proof extends to hypergraph-like settings
where the number of isomorphism types of bounded size is bounded.
This includes random hypergraphs, random SAT Boolean formulae,
and also the model of random groups that we are addressing in the
current paper. A diﬀerent, but very similar tool that can be used
here is Bourgain’s theorem that appears in the appendix of [6], which
has a weaker conclusion, but does not assume the symmetry of the
property in question, such as we have in our current problem. To
make things simpler we will use the ”working-mathematicians-version”
of these theorems, as described in Friedgut [7]. We present below the
lemma we will use, stated in terms of the problem at hand, but ﬁrst let
us introduce some notation. For each value of n we denote by S the set
Sn of generators, and assume that Sn ⊂ Sn+1 , so that any ﬁxed relator
is meaningful for all suﬃciently large values of n. Next, let Γ(n, p) be
given by a presentation P = hS | Ri, where R is random, and let R∗
be a set of relators. We use the notation
h(n, p|R∗ ) := Pr[hS | R ∪ R∗ i is trivial].
We will use this notation both for R∗ = Rfixed = {r1 , . . . , rk }, a ﬁxed
set of cyclically reduced relators of length three, and for R∗ = Rǫp , a
random set of relators chosen from Sn with probability ǫp (in which case
the probability is over both the choice of R and of R∗ ). The following
is an adaptation of theorems 2.2, 2.3, and 2.4 from [7] to the current
setting.
Lemma 3. Assume that there exists a function p = p(n), and constants
0 < α, ǫ < 1, such that there exist infinitely many values of n for which

4

SYLWIA ANTONIUK, EHUD FRIEDGUT, AND TOMASZ LUCZAK

it holds that
α < h(n, p) < h(n, (1 + ǫ)p) < 1 − α.
Then there exists a fixed (finite, independent of n but possibly dependent
on α and ǫ) set Rfixed = {r1 , . . . , rk } of cyclically reduced relators of
length three, and a constant δ > 0 such that for all such n
(i) h(n, p|Rfixed ) > h(n, p) + 2δ
(ii) h(n, p|Rǫp ) < h(n, p) + δ
We will now see how this lemma, together with the fact that Γ(n, p)
collapses when p = n−3/2+o(1) (see either Olliver [8], or Antoniuk,
Luczak and Świa̧tkowski [2] and Theorem 2) implies Theorem 1.
Proof of Theorem 1. Assume, by way of contradiction, that Theorem 1
does not hold. Then the assumptions of Lemma 3 are met. Indeed,
let pc = pc (n) be deﬁned so that h(n, pc ) = 1/2. Then speciﬁcally
Theorem 1 does not hold with the choice of c̃(n)n−3/2 = pc . Hence
there exists an ǫ0 > 0 and a positive constant α < 1/2 such that for
inﬁnitely many values of n either one has h(n, (1 + ǫ0 )pc ) < 1 − α,
or h(n, (1 − ǫ0 )pc ) > α. In the ﬁrst case p = pc , α, ǫ = ǫ0 meet the
assumptions of Lemma 3, in the latter one can take p = (1 − ǫ0 )pc , α,
and ǫ = ǫ0 /(1 − ǫ0 ).
Now, let Rfixed be the set of relators guaranteed by Lemma 3, and let
Z := {z1 , z2 , . . . , zℓ } be the set of all generators involved in Rfixed and
all of their inverses. Let Rstrong be the following relation: z1 = z2 =
. . . = zℓ = e, where e is the identity. Clearly
h(n, p|Rstrong ) ≥ h(n, p|Rfixed ).
Next, consider the graph G = (V, E), where V = (S ∪ S −1 ) \ Z, and E
consists of all pairs xy such that there is a relator in R which involves
x, y and an element of Z (implying x = y −1 , since all elements in Z
are set by Rstrong to be equal to the identity). The probability that
a given pair xy forms an edge is less than 6ℓp, and these events are
independent, so G can be coupled with the Erdős-Rényi random graph
G(2n−ℓ, q) with q = O(n−3/2+o(1) ). Elementary ﬁrst moment estimates
imply that a.a.s. G has fewer than n0.6 non-trivial components each of
them consisting of at most two edges. Indeed, the expected number of
connected subgraphs with exactly 3 edges is bounded by
(2n)3 q 3 + 16(2n)4 q 3 = O(n−0.5),
hence by Markov’s inequality a.a.s. there are no such subgraphs and
isolated edges and paths of length two are the only non-trivial components. Moreover, the expected number of edges in G can be bounded
by
(2n)2 q = O(n0.5 ),
and again by Markov’s inequality a.a.s. there are at most n0.6 of them.
Let R′ be the set of relators in R that are disjoint from Z. Slightly

COLLAPSE OF RANDOM TRIANGULAR GROUP

5

abusing the notation we will also use E to denote the set of relators
{xy : {x, y} ∈ E}. We have
(1)

h(n, p|Rstrong ) = Pr[hS \ Z | R′ ∪ Ei is trivial] + o(n−0.4 ),

where the o(n−0.4 ) accounts for the case where there exists in R a relator
involving two elements of Z. Note that both E and R′ are random.
Now let us consider the eﬀect of Rǫp . First let us choose arbitrarily a
set M, |M| = m = ⌊n1.9 ⌋, of pairs of generators {a, b}, a, b ∈ S ∪ S −1 .
Deﬁne a graph G′ = (V ′ , E ′ ) with V ′ = (S ∪ S −1 ) \ Z and E ′ consisting
of all pairs xy such that Rǫp includes two relators of the form abx and
aby −1 , where {a, b} ∈ M. Note that the existence of such two relators
clearly implies that x = y −1 . Let X denote the number of paths of
length two in G′ = (V ′ , E ′ ). It is easy to see that for the expectation
of X we have
EX ≥ 0.5(2n)3 m2 (ǫp)4 = 4n3 n3.8 n4(−3/2+o(1)) = 4n0.8−o(1) ≥ 4n0.75 .
It is also easy to check that the standard deviation of X is also of order
O(n3 m2 p4 ), so from Chebyshev’s inequality we infer that a.a.s. the
number of such paths is larger than 3n0.75 . On the other hand, let Y
be the number of pairs of paths which share at least one vertex. The
expectation of Y is dominated by the number of pairs which share one
edge and is bounded from above by
EY ≤ (2n)4 m3 (ǫp)6 = 16n4 n5.7 n6(−3/2+o(1)) = 16n0.7+o(1) .
Thus, from Markov’s inequality, a.a.s. the number of such pairs is of
order smaller than n0.75 . Consequently, a.a.s. G′ = (V ′ , E ′ ) contains
at least n0.75 ≫ n0.6 disjoint paths of length two.
Now
(2)

h(n, p|Rǫp ) = Pr[hS \ Z | R′ ∪ E ′ i is trivial] − o(n−0.4 ) ,

where the term o(n−0.4 ) accounts for the fact that even if the group
generated by S \ Z collapses there are the generators in Z to account
for. However, if all generators in S \ Z are set to be equal to the
identity it suﬃces that for each element z ∈ Z there will be in R a
relator involving z and two elements of S \ Z. The probability of this
event is at least as large as 1 − o(n−0.4 ) as n tends to inﬁnity.
We have shown that G′ contains at least n0.1 edge-disjoint subgraphs
isomorphic to the graph spanned by the edges of G, i.e. there is a coupling which shows that E ′ ⊇ E. Thus, the equations (1) and (2)
contradict the items 1 and 2 in the conclusion of Lemma 3. Consequently, the hypothesis of the lemma cannot hold, and the property in
question must have a sharp threshold.

3. Proof of Theorem 2
In order to show Theorem 2 we need to introduce a number of somewhat technical deﬁnitions. Let P = hS | Ri be a group presentation.

6

SYLWIA ANTONIUK, EHUD FRIEDGUT, AND TOMASZ LUCZAK

A van Kampen diagram with respect to the presentation P is a ﬁnite
planar 2-cell complex D given with an embedding D ⊆ R2 and satisfying the following conditions.
• D is connected and simply connected,
• For each edge e and one of its orientations we assign a generator
s ∈ S. If we change the orientation of e to the opposite one, we
replace the generator s by s−1 .
• Each 2-cell c is assigned a relator r ∈ R, the number of edges
on the boundary of c is equal to the length of the relator r,
• For each 2-cell c there is a vertex v such that the word read
from v in some direction of the boundary of the cell is the
relator r ∈ R assigned to c.
For a van Kampen diagram D the size of the diagram, denoted by
|D|, is the number of faces (2-cells) of D. The boundary of D, denoted
by ∂D, is the boundary of the complement of D in R2 and |∂D| denotes
its size, that is the number of edges in ∂D. The boundary word is any
word read from some vertex in ∂D in one of the directions around the
boundary. In particular, the length of this word is precisely |∂D|.
A van Kampen diagram is said to be reduced if there is no pair of
cells c and c′ sharing at least one edge e, which are assigned the same
relator r, and are such that if we read the word r on the boundaries of c
and c′ the edge e has the same orientation and corresponds to the same
letter in the relator with respect to the starting point. A van Kampen
diagram is said to be minimal if it is reduced and no other reduced van
Kampen diagram with smaller number of faces has the same boundary
word.
Let Γ be the group given by a presentation P = hS | Ri. In order to
verify whether Γ is hyperbolic it is enough to consider minimal reduced
van Kampen diagrams with respect to the presentation P and to show
that they fulﬁll a certain geometric condition. In particular, it is known
that a group generated by a presentation P = hS | Ri is hyperbolic
if and only if there exists a coeﬃcient δ > 0 such that every minimal
reduced van Kampen diagram D with respect to the presentation P
satisﬁes the linear isoperimetric inequality |D| ≤ δ|∂D| (cf. [1]).
However, verifying that every reduced van Kampen diagram satisﬁes
a certain isoperimetric inequality may turn out fairly hard since it
requires showing that this inequality holds for all of them. At this
point, the so called local to global principle for hyperbolic geometry
(or Cartan-Hadamard-Gromov-Papasoglu theorem) (cf.[9]) comes to an
aid. This principle states that it is enough to verify the isoperimetric
inequality for a ﬁnite family of van Kampen diagrams.
Theorem 4 (Cartan-Hadamard-Gromov-Papasoglu). Let P = hS | Ri
be a triangular group presentation. Assume that for some integer K >
0 every minimal reduced van Kampen diagram D w.r.t. P and of size

COLLAPSE OF RANDOM TRIANGULAR GROUP

7

K 2 /2 ≤ |D| ≤ 240K 2 satisfies the inequality
K
|∂D|.
200
Then for every minimal reduced van Kampen diagram w.r.t. P the following isoperimetric inequality is true
|D| ≤

|D| ≤ K 2 |∂D|.
Following Ollivier [8], in order to simplify the veriﬁcation of the
isoperimetric condition for van Kampen diagrams, we introduce a klabeled decorated abstract van Kampen diagram (davKd). For simplicity, we do it only for groups with triangular presentations. A k-labeled
b given with an embedding
davKd is a ﬁnite planar 2-cell complex D
b ⊆ R2 and satisfying the following conditions:
D
b is connected and simply connected,
• D
• each 2-cell c is a triangle with a label i from {1, . . . , k}, with
a marked vertex on its boundary and an orientation at this
vertex,
• for all i ∈ {1, . . . , k} and for any 2-cell c labeled by i, starting
from the marked vertex and going around according to prescribed orientation at this vertex, the edges of c get abstract
labels i1 , i2 , i3 .
Now, let P = hS | Ri be a triangular presentation and consider a
b
one-to-one map φ : {1, . . . , k} → R which assigns relators to faces of D.
Let φ1 (i), φ2 (i), φ3 (i) be the generators appearing on the ﬁrst, second
and third position of the relator φ(i) respectively. Then φ induces
a map φe : {ir }1≤i≤k,1≤r≤3 → S which assigns to each abstract label
e r ) = φr (i). The map φ is called
ir a generator from S, namely φ(i
a fulfillment map, if additionally whenever there is an edge with two
e r ) = φ(j
e s ). We say that a given davKd
abstract labels ir , js , then φ(i
b is fulfillable with respect to the presentation P = hS | Ri if there
D
b
exists a fulﬁllment map φ : {1, . . . , k} → R for D.
A davKd is said to be reduced if there is no pair of faces sharing at
least one edge, which are assigned the same label i and have opposite
orientations, and such that the common edge gets the same abstract
label ir from both faces. A davKd is said to be minimal if there is
no other davKd with smaller number of faces and having the same
boundary word (with respect to the abstract labels of edges).
Our aim is to show that for a function f = f (n) = ω/ log1/3 n, where
ω = ω(n) → ∞ and p = n−3/2−f , a.a.s. all minimal reduced van Kampen diagrams D with respect to the random presentation in Γ(n, p) satisfy the isoperimetric inequality with a coeﬃcient δ = δ(n) = (200/f )2 .
But to do it, it is enough to verify this inequality for all minimal reduced
k-labeled davKd’s, so we show that the following statement holds.

8

SYLWIA ANTONIUK, EHUD FRIEDGUT, AND TOMASZ LUCZAK

Lemma 5. Let ω = ω(n) → ∞, ω < log log n, f = f (n) = ω/ log1/3 n,
and p = p(n) = n−3/2−f . Then a.a.s. for each minimal reduced kb fulfillable w.r.t. Γ(n, p), we have
labeled davKd D,

b ≤ 200/f 2 |∂ D|.
b
|D|
In particular, a.a.s. each minimal reduced van Kampen diagram D
w.r.t. Γ(n, p) satisfies the linear isoperimetric inequality
2
|D| ≤ 200/f |∂D|.

Proof. Let f = f (n) = ω/ log1/3 n. From Theorem 4 it is enough to
b of size at most |D|
b ≤ 240(200/f )2
show that a.a.s. each given davKd D
satisﬁes the linear isoperimetric inequality with the coeﬃcient 1/f . We
b with size
do it in two steps. First, we show that for any davKd D
2
b
bounded by |D| ≤ 240(200/f ) one of the following two possibilities
holds:
b satisﬁes the isoperimetric inequality with the coeﬃcient 1/f ;
(i) D
b is fulﬁllable by Γ(n, p) is bounded from
(ii) the probability that D
−f /2
above by n
.
Using this dichotomy, we then show that the probability that there is
b not satisfying the isoperimetric ina bounded size fulﬁllable davKd D
equality in question goes to 0 with n → ∞. Hence, a.a.s. all suﬃciently
small fulﬁllable davKd’s satisfy this inequality.
b be a davKd with m = |D|
b faces having k distinct labels and
Let D
b boundary edges. If each face
with l1 internal edges and l2 = |∂ D|
b corresponds to a difis assigned a diﬀerent label, i.e. each cell of D
b is fulﬁllable is bounded above
ferent relator, the probability that D
l1 +l2 m
by n
p . This is in fact a rather easy case and showing that for
all diagrams with diﬀerent labels and fulﬁllable in Γ(n, p) a.a.s. an
isoperimetric inequality holds with a coeﬃcient 1/f is rather straightb the isoperimetric inequalforward. Indeed, assume that for a given D
b > |∂ D|
b = l2 . Notice also that
ity does not hold, that is f m = f |D|
3m = 2l1 + l2 ≥ 2l1 + 1 as there is at least one edge in the boundb Then the probability that D
b is fulﬁllable is bounded by
ary of D.
l1 +l2 m
l1 +l2 (−3/2−f )m
−1/2
n
p =n
n
≤n
. Moreover, as we will show later,
b
b ≤ 240(200/f )2 is of order
the number of diﬀerent davKd’s D with |D|
much smaller than n1/2 , hence a.a.s. there are no such diagrams which
are fulﬁllable and at the same time do not satisfy the isoperimetric
inequality.
The main challenge is to deal with diagrams where some of the labels
may appear more than once. On one hand, this reduces the number of
distinct relators used to fulﬁll the diagram. On the other hand, this also
imposes some restrictions on the generators used in this assignment.
To control the inﬂuence of these two factors we follow an approach of

COLLAPSE OF RANDOM TRIANGULAR GROUP

9

Ollivier from [8]. To this end let mi denote the number of faces labeled
with i. Without loss of generality we may assume that m1 ≥ m2 ≥
b is fulﬁllable with
. . . ≥ mk . We want to count the probability that D
respect to the random presentation given by Γ(n, p). We introduce an
b which captures all the constraints resulting
auxiliary graph G = G(D)
from the structure of the davKd. The vertices of the graph G are the
abstract labels {ir }1≤i≤k,1≤r≤3 and two vertices ir , js are adjacent if
b carrying labels ir and js . We also deﬁne a family
there is an edge in D
of induced subgraphs G1 ⊂ G2 ⊂ . . . ⊂ Gk of G, where Gl is a subgraph
of G induced by vertices {ir }1≤i≤l,1≤r≤3. Let us remark that the main
reason why this approach to davKd is so convenient is the fact that G
contains no loops if and only if davKd is reduced.
Now, the number of connected components in the graph G is the
total number of distinct generators which can appear in relators used
b In some sense, this gives us the number
in the fulﬁllment map φ for D.
of degrees of freedom we have while choosing relators for the fulﬁllment
map. Indeed, if two vertices are adjacent in G, then the corresponding
b are mapped by φe to the same generator. Therefore,
abstract labels in D
if we denote the number of connected components in the graph G by
C, then we obtain the estimate
b is fulﬁllable) ≤ nC pk .
Pr(D
A similar argument works for the graphs Gl , which correspond to a
partial assignment, namely we assign relators to faces bearing labels
1, . . . , l. Let Cl denote the number of connected components in Gl .
Then
b is fulﬁllable) ≤ nCl pl = nCl −l(3/2+f ) ,
Pr(D

therefore putting

dl = Cl − l(3/2 + f )
we get the estimate
b is fulﬁllable) ≤ nmin dl .
Pr(D
Thus, if for some l we have dl < −f /2, then
b is fulﬁllable) ≤ n−f /2 .
Pr(D
On the other hand, we claim that in the case of min dl ≥ −f /2, the
b satisﬁes the isoperimetric inequality with the coeﬃcient
diagram D
1/f . Indeed, as was observed by Ollivier [8] (see p.613) one gets that
b ≥ 3|D|(1
b − 2d) + 2
|∂ D|

k
X
l=1

dl (ml − ml+1 ),

10

SYLWIA ANTONIUK, EHUD FRIEDGUT, AND TOMASZ LUCZAK

where the parameter d is the density of the random triangular group,
which in our notation is equal to 1/2 − f /3. Thus
b ≥ 2f |D|
b +2
|∂ D|

k
X

dl (ml − ml+1 ).

l=1

Next, observe that ml − ml+1 ≥ 0 for every l and
if min dl ≥ −f /2, then
b ≥ 2f |D|
b −f
|∂ D|

k
X
l=1

P

b Hence,
ml = |D|.

b
(ml − ml+1 ) ≥ f |D|,

and we arrive at the desired isoperimetric inequality
b ≤ 1 |∂ D|.
b
(3)
|D|
f
To complete our argument we use the local to global principle. In
our case the coeﬃcient K from Theorem 4 is equal to 200/f . We
need to show that the probability that there exists a diagram of size
at most 240(200/f )2 violating the isoperimetric inequality (3) tends
to 0. If this is the case, then the random presentation in the Γ(n, p)
model a.a.s. meets the assumptions of the local to global principle,
hence a.a.s. each diagram satisﬁes the isoperimetric inequality with
the coeﬃcient (200/f )2.
First, we need to count the number of all possible davKd’s with
precisely m faces. To do this we take the number of all possible triangulations of a polygon which consist of exactly m triangles, and then
for each triangle we choose the orientation in 2 ways, the starting point
in 3 ways and the label of this face in m ways.
A triangulation of a polygon with m triangles has at most m + 2
vertices. Thus, the number of such triangulations is bounded from
above by the number of distinct triangulations t(N) of a 2-dimensional
sphere with N vertices, where N ≤ m+3, which in turn we bound from
above by αm for some absolute constant α > 0 (see Tutte [10]). Hence,
the total number of davKd’s with exactly m faces can be bounded by
αm · 6m · mm /m! ≤ β m , where β > 0 is an appropriate constant. Therefore, the probability that a fulﬁllable davKd of size at most 240(200/f )2
violates the isoperimetric inequality (3) is at most
X
γ
β m n−f /2 ≤ β f 2 n−f /2 ,
m≤240(200/f )2

for some constant γ > 0. It is easy to verify that the right hand side of
this inequality tends to 0 as n → ∞ provided f = f (n) = ω/ log1/3 n.
b with |D|
b ≤ 240(200/f )2 fulﬁllable in
Hence, a.a.s. for every davKd D
Γ(n, p) the isoperimetric inequality holds with a coeﬃcient 1/f and so
the assertion follows from Theorem 4.


COLLAPSE OF RANDOM TRIANGULAR GROUP

11

Proof of Theorem 2. As the group properties in question are monotone
1/3
decreasing, it is enough to consider p(n) = n−3/2−ω/ log n with ω <
log log n. Observe ﬁrst that a.a.s. Γ(n, p) is aspherical, i.e. there exists
no reduced spherical van Kampen diagram with respect to the random
presentation Γ(n, p). Indeed, such a spherical reduced van Kampen
diagram has zero boundary, which violates the isoperimetric inequality
proved in Lemma 5. Since Γ(n, p) is aspherical, it is torsion-free (see,
for instance, Brown [4], p. 187). Consequently, a.a.s. Γ(n, p) is an
inﬁnite, hyperbolic group.


Let us conclude with a remark that in order to show the conjecture
we have to prove Theorem 2 with τ (n) = O(1/ log n) instead of τ (n) =
ω/(log n)1/3 . Such an improvement seems to require a new approach
and, perhaps, a stronger version of Theorem 4.

References
[1] J. Alonso, T. Brady, D. Cooper, V. Ferlini, M. Lustig, M. Mihalik, M. Shapiro,
and H. Short et al., Notes on word hyperbolic groups, Group Theory from a Geometrical Viewpoint, (E. Ghys, A. Haeﬂiger, and A. Verjovsky, eds.) World Scientiﬁc, Singapore, 1991, 3–63.
[2] S. Antoniuk, T. Luczak, and J. Świa̧tkowski, Collapse of random triangular
groups: a closer look , Bull. Lond. Math. Soc. 46,4 (2014), 761–764.
[3] B. Bollobás and A. Thomason, Threshold functions, Combinatorica 7 (1987),
35–38.
[4] K. Brown, ”Cohomology of groups”, Graduate Texts in Mathematics 87,
Springer, 1982.
[5] M. Gromov, Asymptotic invariants of infinite groups. Geometric Group Theory,
London Math. Soc. Lecture Note Ser. 182 (1993), 1–295.
[6] E. Friedgut, Sharp thresholds of graph properties, and the k-sat problem. With
an appendix by Jean Bourgain. Journal of the American Math. Soc. 12,4 (1999),
1017–1054.
[7] E. Friedgut, Hunting for sharp thresholds, Random Struct. Algorithms 26
(2005), 37–51.
[8] Y. Ollivier, Sharp phase transition theorems for hyperbolicity of random groups,
Geom. Funct. Anal. 14 (2004), 595–679.
[9] P. Papasoglu, An algorithm detecting hyperbolicity, (Minneapolis, MN and New
Brunswick, NJ, 1994) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol.
25, Amer. Math. Soc., Providence, RI (1996), 193–200.
[10] W. T. Tutte, A census of planar triangulations, Canad. J. Math. 14 (1962),
21–38.
[11] A. Żuk, Property (T) and Kazhdan constants for discrete groups, Geom. Funct.
Anal. 13 (2003), 643–670.

12

SYLWIA ANTONIUK, EHUD FRIEDGUT, AND TOMASZ LUCZAK

Adam Mickiewicz University, Faculty of Mathematics and Computer
Science ul. Umultowska 87, 61-614 Poznań, Poland
E-mail address: antoniuk@amu.edu.pl
Weizmann Institute of Science, Faculty of Mathematics and Computer Science 234 Herzl St. Rehovot 7610001, Israel
E-mail address: ehud.friedgut@weizmann.ac.il
Adam Mickiewicz University, Faculty of Mathematics and Computer
Science ul. Umultowska 87, 61-614 Poznań, Poland
E-mail address: tomasz@amu.edu.pl

