Tsung-Hsuan Tsai

Freiheitssatz and phase transition for the density model of random groups

, showing a phase transition phenomenon at density dr = min{ 1 2 , 1 -log 2m-1 (2r -1)} with 1 ≤ r ≤ m -1: we prove that for a random group with m generators at density d, if d < dr then the first r letters freely generate a free subgroup; whereas if d > dr then the first r letters generate the whole group. Contents 1 Introduction 2 Preliminaries on group theory 2.1 Stallings graphs (graphs generating subgroups) . . . . . . . . . . . .

Introduction

The Freiheitssatz (freedom theorem in German) is a fundamental theorem in combinatorial group theory. It was proposed by M. Dehn and proved by W. Magnus in his doctoral thesis [START_REF] Magnus | Über diskontinuierliche Gruppen mit einer definierenden Relation. (Der Freiheitssatz)[END_REF] in 1930 (see [START_REF] Lyndon | Combinatorial Group Theory[END_REF] II.5). The theorem states that for a group presentation G = x 1 , . . . , x m |r where the single relator r is a cyclically reduced word, if x m appears in r, then x 1 , . . . , x m-1 freely generate a free subgroup of G.

Random groups are groups obtained by a probabilistic construction. Its first mentions, in terms of "generic property" for finitely presented groups, appear in the works of V. S. Guba [START_REF] Guba | Conditions under which 2-generated subgroups in small cancellation groups are free[END_REF] and M. Gromov [START_REF] Gromov | Hyperbolic groups[END_REF] §0.2 in the late 1980s. The simplest model of random groups is the few relator model ( [START_REF] Ollivier | A January 2005 invitation to random groups[END_REF] Definition 1). A few relator random group is defined by a group presentation G ℓ = x 1 , . . . , x m |r 1 , . . . , r k where the set of generators X = {x 1 , . . . , x m } is fixed, and the relators r 1 , . . . , r k are chosen uniformly at random among all reduced words of X ± of length at most ℓ. The first well-known result of random groups ([13] §0.2) is that asymptotically almost surely (denoted by a.a.s., which means with probability converges to 1 when ℓ goes to infinity), a few relator random group G ℓ is non-elementary hyperbolic.

For detailed surveys on random groups, see (in chronological order) [START_REF] Ghys | Groupes aléatoires (d'après Misha Gromov[END_REF] by E. Ghys, [START_REF] Ollivier | A January 2005 invitation to random groups[END_REF] by Y. Ollivier, [START_REF] Kapovich | On group-theoretic models of randomness and genericity[END_REF] by I. Kapovich and P. Schupp and [START_REF] Bassino | Random presentations and random subgroups: a survey[END_REF] by F. Bassino, C. Nicaud and P. Weil.

The density model of random groups

In 1993, Gromov introduced the density model of random groups in [START_REF] Gromov | Finitely presented groups. Asymptotic invariants of infinite groups[END_REF] 9.B. He considered a group presentation with a fixed set of m generators X = {x 1 , . . . , x m } and ⌊(2m -1) dℓ ⌋ randomly chosen relators, among the 2m(2m -1) ℓ-1 reduced words of X ± of length ℓ. The parameter d ∈ [0, 1] is called the density. Compare to the few relator model, the number of relators grows exponentially with the length ℓ. The main result of [START_REF] Gromov | Finitely presented groups. Asymptotic invariants of infinite groups[END_REF] 9.B is the phase transition at density one half: if d > 1 2 , then a.a.s. the group is trivial; if d < 1 2 , then a.a.s. the group is non-elementary hyperbolic. In a 1996 paper [START_REF] Arzhantseva | Ol'shanskii. The class of groups all of whose subgroups with lesser number of generators are free is generic[END_REF], G. Arzhantseva and A. Ol'shanskii proved a few relator random group version of the Freiheitssatz: a.a.s. every (m -1)-generated subgroup of a few relator random group G ℓ is free. Arzhantseva proved several free subgroup properties subsequently for the few relator model in [START_REF] Arzhantseva | On groups in which subgroups with a fixed number of generators are free (Russian)[END_REF], [START_REF] Arzhantseva | Generic properties of finitely presented groups and Howson's theorem[END_REF] and [START_REF] Arzhantseva | A property of subgroups of infinite index in a free group[END_REF]. Kapovich-Schupp [START_REF] Kapovich | On group-theoretic models of randomness and genericity[END_REF] showed the existence of a small positive density d(m) such that these results ( [START_REF] Arzhantseva | Ol'shanskii. The class of groups all of whose subgroups with lesser number of generators are free is generic[END_REF], [START_REF] Arzhantseva | On groups in which subgroups with a fixed number of generators are free (Russian)[END_REF], [START_REF] Arzhantseva | Generic properties of finitely presented groups and Howson's theorem[END_REF] and [START_REF] Arzhantseva | A property of subgroups of infinite index in a free group[END_REF]) can be generalized to a random group at any density d < d(m). It was showed in [START_REF] Tsai | Density of random subsets and applications to group theory[END_REF] that the "every (m -1)-generated subgroup is free" property [START_REF] Arzhantseva | Ol'shanskii. The class of groups all of whose subgroups with lesser number of generators are free is generic[END_REF] holds a.a.s. for a random group at any density d < 1 120m 2 ln(2m) . In 2003, Gromov defined the general notion of random groups in [START_REF] Gromov | Random walk in random groups[END_REF] and proposed in Section 1.9 the following general problem: determining asymptotic invariants and phase transition phenomena for random groups. Since then, several variants of the phase transition phenomena have been discovered. For instance, A. Żuk [START_REF] Żuk | Property (T) and Kazhdan constants for discrete groups[END_REF] showed the freeness-property (T ) phase transition for random triangular groups at density 1/3 (see also [START_REF] Antoniuk | Random triangular groups at density 1/3[END_REF] by Antoniuk-Łuczak-Świa ¸tkowski). Y. Ollivier proved in 2004 [START_REF] Ollivier | Sharp phase transition theorems for hyperbolicity of random groups[END_REF] the hyperbolicity-triviality transition for hyperbolic random groups, and in 2007 [START_REF] Ollivier | Some small cancellation properties of random groups[END_REF] the phase transition at density 1/5 for Dehn's algorithm. In 2015 [START_REF] Calegary | Random groups contain surface subgroups[END_REF], D. Calegary and A. Walker showed that a random group at density d < 1/2 contains surface subgroups.

As we shall see, the main result of this paper is to highlight a new phase transition phenomenon, giving an analogue of the Freiheitssatz in the density model of random groups. In particular, it partially answers Gromov's problem [START_REF] Gromov | Random walk in random groups[END_REF] 1.9 (iv): existence/nonexistence of non-free subgroups.

Main results

We say that a finite group presentation G = X|R satisfies the Magnus Freiheitssatz property if every subset of X of cardinality |X| -1 freely generates a free subgroup of G. In particular, by Arzhantseva-Ol'shanskii's result [START_REF] Arzhantseva | Ol'shanskii. The class of groups all of whose subgroups with lesser number of generators are free is generic[END_REF], a few-relator random group G ℓ has this property a.a.s.. We study the Magnus Freiheitssatz property in the density model of random groups.

Denote B ℓ as the set of cyclically reduced words of

X ± = {x ± 1 , . . . , x ± m } of length at most ℓ. Let G ℓ (m, d) = X|R ℓ
be a random group at density d. That is to say, R ℓ is a permutation invariant random subset of B ℓ with density d (see Section 3 or [START_REF] Tsai | Density of random subsets and applications to group theory[END_REF]). For example, it can be a uniform distribution on subsets of

B ℓ of cardinality ⌊|B ℓ | d ⌋, or a Bernoulli sampling on B ℓ of parameter |B ℓ | d-1 .
For any

1 ≤ r ≤ m -1, let d r = min 1 2 , 1 -log 2m-1 (2r -1) .
Theorem 1 (Phase transition at density d r , cf. Theorem 5.1). By symmetry, the set {x 1 , . . . , x r } can be replaced by any subset X r of X of cardinality r. In particular, if 0 ≤ d < d m-1 , then the group presentation G ℓ (m, d) = X|R ℓ has the Magnus Freiheitssatz property. More precisely for the first assertion, we prove that if d > d r then a.a.s. any generator x i equals to a reduced word of X ± r of length ℓ -1 in G ℓ (m, d). Therefore, any relator r i ∈ R ℓ can be replaced by a reduced word r ′ i of X ± r of length at most ℓ(ℓ -1). Construct R ′ ℓ by replacing every word of R ℓ , we have the following result. Remark 3. We emphasize that R ′ ℓ contains relators of lengths varying from ℓ to ℓ 2 . Such a presentation can not be studied using known methods in geometric or combinatorial group theory. Nevertheless, it gives us new examples of groups having the Magnus Freiheitssatz property.

Let r = r(m, d) be the maximal number such that a.a.s. x 1 , . . . , x r freely generate a free subgroup of G ℓ (m, d). By the phase transition at density

1 2 [14], if d > 1 2 then r(m, d) = 0. If d ≤ 1 2 , by Theorem 1 (2m -1) 1-d -1 2 ≤ r(m, d) ≤ (2m -1) 1-d + 1 2 . 0 0.2 0.4 0.6 0.8 1 0 2 4 6 8 10 d r (2m-1) 1-d +1 2 (2m-1) 1-d -1 2 r(m, d) r(m, d) with m = 10
As r(m, d) is an integer, there is only one choice when d is not 1/2 or one of d r . Note that the value of r(m, d) is not clear when d ∈ {d 1 , . . . , d m-1 , 1/2}.

Our main theorem (Theorem 5.1) is a generalized version of Theorem 1. In the second assertion, we can replace the set {x 1 , . . . , x r } by any set of r words of X ± of lengths at most dr-d 5r ℓ.

Outline of the paper

In Section 2, we first recall some essential tools in combinatorial group theory (Stallings graphs [START_REF] Stallings | Topology of finite graphs[END_REF] and van Kampen diagrams [START_REF] Van Kampen | On Some Lemmas in the Theory of Groups[END_REF]). We introduce distortion van Kampen diagrams to study the distortion of subgroups of a finitely presented group.

In order to give a concrete construction of random groups with density, we discuss probabilistic models of random subsets in Section 3 and recall the intersection formula by M. Gromov in [START_REF] Gromov | Finitely presented groups. Asymptotic invariants of infinite groups[END_REF]. Technical details are treated in [START_REF] Tsai | Density of random subsets and applications to group theory[END_REF].

Section 4 is dedicated to abstract van Kampen diagrams defined by Y. Ollivier in [START_REF] Ollivier | Sharp phase transition theorems for hyperbolicity of random groups[END_REF]. We apply his idea to distortion diagrams and define abstract distortion diagrams. The main technical lemma for our main theorem (Theorem 5.1) is to estimate the number of fillings of a given abstract distortion diagram (Lemma 4.12).

In the last section, we state a local result on distortion van Kampen diagrams (Lemma 5.2) and prove the main theorem by this lemma. The last subsection is then devoted to the proof of Lemma 5.2.

Acknowledgements. I would like to thank my supervisor, Thomas Delzant, for his patience and guidance, and for many interesting and helpful discussions on the subject.

Preliminaries on group theory

In this section, we fix a finite group presentation G = X|R where X is the set of generators and R is the set of relators. A word u in the alphabet X ± is called reduced if it has no sub-words of type xx -1 or x -1 x for any x ∈ X. If u and v are words that represent the same element in G, we denote u = G v.

We consider oriented combinatorial graphs and 2-complexes as defined in Chapter III.2. of Lyndon and Schupp [START_REF] Lyndon | Combinatorial Group Theory[END_REF].

Stallings graphs (graphs generating subgroups)

A graph is a pair Γ = (V, E) where V is the set of vertices (also called points) and E is the set of (oriented) edges. Every edge e ∈ E has a starting point α(e) ∈ V , an ending point ω(e) ∈ V and an inverse edge e -1 ∈ E, satisfying α(e -1 ) = ω(e), ω(e -1 ) = α(e) and (e -1 ) -1 = e. The vertices α(e) and ω(e) are called the endpoints of e. An undirected edge is a pair of inverse edges {e, e -1 }. The size |Γ| of a graph is the number of its undirected edges. The rank rk(Γ) is the rank of its fundamental free group, which equals to |Γ| -|V | + 1 by Euler's characteristic.

A path on a graph Γ is a non-empty finite sequence of edges p = e 1 . . . e k such that ω(e i ) = α(e i+1 ) for i ∈ {1, . . . k -1}. The starting point and the ending point of the path p are defined by α(p) = α(e 1 ) and ω(p) = ω(e k ). The inverse of p is the path p -1 = e -1 k . . . e -1 1 . A path is called reduced if there is no subsequence of the form ee -1 . A loop is a path whose starting point and ending point coincide. In this case α(p) = ω(p) is called the starting point of the loop. A loop p = e 1 . . . e k is cyclically reduced if it is a reduced path with e k = e -1

1 . An arc of a graph Γ is a reduced path passing only by vertices of degree 2, except possibly for its endpoints. A maximal arc is an arc that can not be extended to another arc. Note that the endpoints of a maximal arc are not of degree 2. The following elementary fact for finite connected graphs can be deduced by Euler's characteristic.

Lemma 2.1. Let Γ be a finite connected graph of rank r ≥ 1 with no vertices of degree 1.

1. The number of vertices of degree at least 3 is bounded by 2(r -1).

The number of maximal arcs of Γ is bounded by 3(r -1).

Lemma 2.2. The number of topological types of finite connected graphs of rank at most r with no vertices of degree 1 is bounded by (2r) 6r .

Proof. If r = 1 then the only topological type is a simple cycle. If r ≥ 2, we may draw a ≤ 3(r -1) arcs on a set of v ≤ 2(r -1) vertices. There are at most (v 2 ) a ≤ (2r) 6r ways.

A labeled graph (with respect to the alphabet X) is a graph Γ = (V, E) with a labelling function on edges by generators ϕ : E → X ± , satisfying ϕ(e -1 ) = ϕ(e) -1 . We denote briefly Γ = (V, E, ϕ). The labeling function ϕ extends naturally on the paths of Γ. If p = e 1 . . . e k is a path of Γ, then the word ϕ(p) = ϕ(e 1 ) . . . ϕ(e k ) is called the labeling word of p. We say that a word u is readable on a labeled graph Γ if there exists a path p of Γ whose labeling word is u.

Labeled graphs are considered by Stallings [START_REF] Stallings | Topology of finite graphs[END_REF] to represent subgroups of a free group. Let Γ = (V, E, ϕ) be a finite connected labeled graph. Labeling words of the loops starting at a vertex o ∈ V form a subgroup H of G = X|R , which is the image of the fundamental group π 1 (Γ, o) by the group homomorphism induced by ϕ. If H is a conjugate of the subgroup ϕ(π 1 (Γ, o)) in G for some o ∈ V , we say that H is generated by the labeled graph Γ.

Conversely, any finitely generated subgroup H can be generated by a labeled graph. One can choose a system of generators h 1 , . . . , h r of H, and label them on the wedge of r simple cycles of lengths |h 1 |, . . . , |h r |. A labeled graph is reduced if it has no pair of edges with the same label and starting point, and, it has no vertices of degree 1. By doing reductions on the construction above (see [START_REF] Arzhantseva | Ol'shanskii. The class of groups all of whose subgroups with lesser number of generators are free is generic[END_REF] and [START_REF] Margolis | Free inverse monoids and graph innersions[END_REF]), if H is a subgroup of rank r, then there is a reduced labeled graph of rank r that generates H.

Van Kampen diagrams

We consider van Kampen diagrams defined by Lyndon and Schupp in [START_REF] Lyndon | Combinatorial Group Theory[END_REF] Chapter III.9. A 2-complex is a triplet W = (V, E, F ), where (V, E) is a graph and F is the set of (oriented) faces. Every face f ∈ F has a boundary ∂f , which is a cyclically reduced loop of (V, E), and an inverse face

f -1 ∈ F satisfying ∂(f -1 ) = (∂f ) -1 and (f -1 ) -1 = f . An undirected face is a pair of inverse faces {f, f -1 }. The size |W | is the number of undirected faces.
Note that our definition is slightly more precise then [START_REF] Lyndon | Combinatorial Group Theory[END_REF]: Every face f ∈ F has a starting point and an orientation given by ∂f . If ∂f = e 1 . . . e k , we say that e i is attached to f and is the i-th boundary edge of f for 1 ≤ i ≤ k. In this case, we say that {e i , e -1 i } is attached to {f, f -1 }. An edge is called isolated if it is not attached to any face.

A van Kampen diagram (with respect to G = X|R ) is a finite, planar (embedded in R 2 ) and simply connected 2-complex D = (V, E, F ) with two compatible labeling functions, on edges by generators ϕ 1 : E → X ± and on faces by relators

ϕ 2 : F → R ± . Compatible means that (V, E, ϕ 1 ) is a labeled graph, ϕ 2 (f -1 ) = ϕ 2 (f ) -1 and ϕ 1 (∂f ) = ϕ 2 (f ). Note that if a diagram D has no isolated edges (for example, a disk), then ϕ 1 is determined by ϕ 2 . We denote briefly D = (V, E, F, ϕ 1 , ϕ 2 ).
According to [START_REF] Collins | Spherical Diagrams and Identities Among Relations[END_REF] p.159, a van Kampen diagram is either a disk or a concatenation of disks and segments. The boundary ∂D is the boundary of R 2 \D, which is a sub-graph of its underlying graph (V, E). A boundary path is a path on ∂D defined in a natural way in [START_REF] Lyndon | Combinatorial Group Theory[END_REF] p.150. A boundary word of D is then the labeling word of a boundary path, unique up to cyclic conjugations and inversions. The boundary length of D is the length of a boundary path, denoted |∂D|.

Let D = (V, E, F, ϕ 1 , ϕ 2 ) be a van Kampen diagram. A pair of faces f, f ′ ∈ F is reducible if they have the same label and there is a common edge on their boundaries at the same position. A van Kampen diagram is called reduced if there is no reducible pair of faces.

r r a reducible pair of faces

In 1933, E. van Kampen showed in [START_REF] Van Kampen | On Some Lemmas in the Theory of Groups[END_REF] that a word u of X ± is trivial in a finitely presented group G = X|R if and only if it is a boundary word of a van Kampen diagram of G. In [START_REF] Yu | Ol'shanskii. Geometry of Defining Relations in Groups[END_REF] §11.6, A. Ol'shanskii improved this result to reduced diagrams.

Lemma 2.3 (Van Kampen's lemma, Ol'shanskii's version).

A word w of X ± is trivial in G = X|R if and only if it is a boundary word of a reduced van Kampen diagram.

Distortion van Kampen diagrams

Let G = X|R be a group presentation. For any word u of X ± , we denote |u| its word length and u G the distance between the endpoints of its image in the Cayley graph Cay(G, X). Let Γ be a finite, connected and reduced labeled graph. Its universal covering Γ is an infinite, connected and reduced labeled tree, with a natural labelpreserving map Γ → Cay(G, X).

If the map Γ → Cay(G, X) is a λ-quasi isometric embedding with some λ ≥ 1 (in other words, every reduced word u readable on Γ satisfies |u| ≤ λ u G ), then any subgroup generated by Γ is a free group. To study this question, we introduce distortion van Kampen diagrams.

(D, p) of (G, Γ) satisfies |p| ≤ λ 1 + λ |∂D|, (⋆) then the map Γ → Cay(G, X) is a λ-quasi isometric embedding.
In particular, any subgroup generated by Γ is free.

Proof. Let u be a reduced word that is readable on Γ. Let v be a shortest word (whose image is a geodesic in G) such that uv = G 1. We shall check that |u| ≤ λ|v|.

By van Kampen's lemma (Lemma 2.3), there exists a reduced van Kampen diagram D whose boundary word is uv. If D is disk-like, then by the hypothesis (⋆) we have |u| ≤ λ 1+λ (|u| + |v|), which gives |u| ≤ λ|v|. Otherwise, we decompose D into disks and segments D 1 , . . . , D k (as in [START_REF] Collins | Spherical Diagrams and Identities Among Relations[END_REF] p.159). The path of v does not intersect itself because it is a geodesic in G. The path of u on D does not intersect itself. If it did, as u is reduced, there would be a disk-like subdiagram whose boundary word is readable on Γ, which is impossible because of (⋆).

Hence, for any 1 ≤ i ≤ k, there are exactly two vertices on ∂D i separating u and v, which are the only possible vertices of degree not equal to 2. The boundary word of D i is written as u i v i where u i is a subword of u and v i is a subword of v. If D i is a segment, then it is read once by u and once by v with opposite directions, so

|u i | = |v i | ≤ λ|v i |. If D i is a disk, then |u i | ≤ λ|v i | by (⋆). We conclude that |u| = k i=1 |u i | ≤ k i=1 λ|v i | = λ|v|.

Hyperbolic groups

In this subsection we recall several facts of hyperbolic groups defined by M. Gromov in [START_REF] Gromov | Hyperbolic groups[END_REF]. Let G = X|R be a finite group presentation. The Cayley graph Cay(G, X) with the usual length metric is δ-hyperbolic if each side of any geodesic triangle is δ-close to the two other sides ([10] Chapter 1). In this case, G is called a hyperbolic group.

We start by a criterion of hyperbolicity in [START_REF] Gromov | Hyperbolic groups[END_REF] Chapter 2.3. See also [START_REF] Short | Notes on word hyperbolic groups[END_REF] by H. Short and [10] Chapter 6. For a precise estimation of hyperbolicity constants, see [ Recall that a path p in Cay(X, R) is a λ-quasi-geodesic if every sub-path u of p satisfies |u| ≤ λ u G . It is a L-local λ-quasi geodesic if such an inequality is satisfied by every sub-path of length at most L. Here is the local-global principle for quasigeodesics in hyperbolic groups, stated by Gromov in [13] 7.2.A and 7.2.B. See [START_REF] Coornaert | Géométrie et théorie des groupes[END_REF] Chapter 3 for a proof. Theorem 2.8. Let G = X|R be a group presentation such that Cay(G, X) is δhyperbolic. Let λ ≥ 1, then 1. Every λ-quasi-geodesic is 100δ(1 + log λ) close to any geodesic joining its endpoints.

2. Every 1000λδ-local λ-quasi-geodesic is a (global) 2λ-quasi-geodesic.

Random subsets and random groups

In this section, we recall the definition of random groups with density by M. Gromov in [START_REF] Gromov | Finitely presented groups. Asymptotic invariants of infinite groups[END_REF]. Proofs of Proposition 3.2, Proposition 3.3, Theorem 3.4 and Theorem 3.5 are in [START_REF] Tsai | Density of random subsets and applications to group theory[END_REF].

Densable sequences of random subsets

A random subset A of a finite set E is a P(E)-valued random variable, where P(E) is the set of subsets of E. We say that A is permutation invariant if Pr(A = a) = Pr(A = σ(a)) for any permutation σ of E and any subset a of E.

In this subsection, we consider a sequence of finite sets

E = (E ℓ ) ℓ∈N with |E ℓ | ---→ ℓ→∞ ∞.
Let (Q ℓ ) be a sequence of events. We say that the event

Q ℓ holds asymptotically almost surely if Pr(Q ℓ ) ---→ ℓ→∞ 1.
We denote briefly a.a.s. Q ℓ . Note that the intersection of a finite number of events that hold a.a.s. is an event that holds a.a.s.. In addition, we have the following proposition.

Proposition 3.1. Let Q = (Q ℓ ), R = (R ℓ )
Pr(R ℓ ) = Pr(Q ℓ )Pr (R ℓ |Q ℓ ) + Pr(Q ℓ )Pr R ℓ Q ℓ ---→ ℓ→∞ 1. Let d ∈ {-∞} ∪ [0, 1]. A sequence of random subsets A = (A ℓ ) of E = (E ℓ ) is densable with density d if the sequence of real-valued random variables log |E ℓ | (|A ℓ |)
converges in probability (or in distribution) to the constant d. We denote

dens A = d.

By definition, dens

A = d if and only if ∀ε > 0 a.a.s. |E ℓ | d-ε ≤ |A ℓ | ≤ |E ℓ | d+ε .
In particular, dens A = -∞ if and only if a.a.s. A ℓ = Ø; dens A = 0 if and only if a.a.s.

A ℓ = Ø and |A ℓ | is sub-exponential.
Here is the main example of a densable sequence of permutation invariant random subsets. The proofs of Theorem 3.4 and Theorem 3.5 are much simpler in this model (see [START_REF] Tsai | Density of random subsets and applications to group theory[END_REF]). Proposition 3.2 (Bernoulli density model, [START_REF] Tsai | Density of random subsets and applications to group theory[END_REF] Proposition 1.12). Let 0 < d ≤ 1. Let A ℓ be a sequence of random subsets of E ℓ such that every element e ∈ E ℓ is taken independently with probability p ℓ = |E ℓ | d-1 . Then A = (A ℓ ) is a densable sequence of permutation invariant random subsets with density d.

Note that in the case d = 0, the Bernoulli model is not densable. If A ℓ is a Bernoulli sequence with density d > 0, then for any distinct elements e 1 , . . . , e k in E ℓ , we have Pr(e 1 , . . . , e 1) by independence. This property is, in general, not true for an arbitrary densable sequence of permutation invariant random subsets. Nevertheless, it can be approached asymptotically.

k ∈ A ℓ ) = p k ℓ = |E ℓ | k(d-
|E ℓ | k(d-1-2ε) ≤ Pr (e 1 , . . . , e k ∈ A ℓ |Q ℓ ) ≤ |E ℓ | k(d-1+2ε) .

The intersection formula

We recall here the intersection formula for random subsets. See [START_REF] Gromov | Finitely presented groups. Asymptotic invariants of infinite groups[END_REF] for the original version by M. Gromov, and [START_REF] Tsai | Density of random subsets and applications to group theory[END_REF] Section 2 for a proof.

Theorem 3.4 (The intersection formula). Let A = (A ℓ ), B = (B ℓ ) be independent densable sequences of permutation invariant random subsets.

If dens

A + dens B < 1, then a.a.s. A ℓ ∩ B ℓ = Ø.

If dens

A + dens B > 1, then A ∩ B := (A ℓ ∩ B ℓ ) is a densable sequence of
permutation invariant random subset and

dens(A ∩ B) = dens A + dens B -1.
In particular, a.a.s.

A ℓ ∩ B ℓ = Ø.
A fixed subset can be regarded as a constant random subset. The density of a sequence of fixed subsets can be defined by the same way. Note that a sequence of subsets F = (F ℓ ) of E = (E ℓ ) is densable with density d if and only if (1) .

|F ℓ | = |E ℓ | d+o
We consider also the intersection between a sequence of random subsets and a sequence of fixed subsets. See [START_REF] Tsai | Density of random subsets and applications to group theory[END_REF] Section 3 for a proof. Theorem 3.5 ([28] Theorem 3.7). Let A = (A ℓ ) be a densable sequence of permutation invariant random subsets of E. Let F = (F ℓ ) be a densable sequence of fixed subsets.

If dens

A + dens F < 1, then a.a.s. A ℓ ∩ F ℓ = Ø.

If dens

A + dens F > 1, then the sequence A ∩ F is densable in E, with density dens A + dens F -1.
In addition, A ∩ F is densable and permutation invariant in F , with density dens A + dens F -1 dens F .

The density model of random groups

Fix an alphabet X = {x 1 , . . . , x m } as generators of group presentations. Let B ℓ be the set of cyclically reduced words on

X ± = {x ± 1 , . . . , x ± m } of lengths at most ℓ. Note that |B ℓ | = (2m -1) ℓ+o(ℓ) .
We consider a sequence of random groups G(m, d) = (G ℓ (m, d)) defined by random presentations G ℓ (m, d) := X|R ℓ where R = (R ℓ ) is a densable sequence of permutation invariant random subsets of B = (B ℓ ) with density d. Such a sequence is called a sequence of random groups at density d.

The number of relators |R ℓ | is a real-valued random variable and is concentrated to (2m -1) dℓ . More precisely, for any ε > 0 a.a.s.

(2m -1) dℓ-εℓ ≤ |R ℓ | ≤ (2m -1) dℓ+εℓ .
We are interested in asymptotic behaviors of a sequence of random groups. In his book [START_REF] Gromov | Finitely presented groups. Asymptotic invariants of infinite groups[END_REF], Gromov observed that there is a phase transition at density 1/2. The proof of our main theorem (Theorem 5.1) is very similar to Ollivier's proof [START_REF] Ollivier | A January 2005 invitation to random groups[END_REF] for this theorem. We give here a proof for the first assertion and an idea of proof for the second assertion.

Proof of Theorem 3.6.1. Let S ℓ be the set of cyclically reduced words of length exactly ℓ. The sequence (S ℓ-1 ) is a fixed sequence of subsets of B = (B ℓ ) of density 1. By the intersection formula (Theorem 3.5), the two sequences (x 1 R ℓ ∩ x 1 S ℓ-1 ) and (R ℓ ∩ x 1 S ℓ-1 ) are both sequences of random subsets of (x 1 S ℓ-1 ) with density d. By the intersection formula between random subsets (Theorem 3.4), their intersection is a sequence of random subsets with density (2d -1) > 0, which is a.a.s. not empty. Thus, a.a.s. there exists a word w ∈ S ℓ-1 such that w ∈ R ℓ and x 1 w ∈ R ℓ , so a.a.s.

x 1 = 1 in G ℓ by canceling w.
The argument works for every generator x i ∈ X. By intersecting a finite number of a.a.s. events, a.a.s. G ℓ is isomorphic to the trivial group. By Theorem 2.6 and Theorem 2.7, to prove Theorem 3.6.2, it is sufficient to find a local isoperimetric inequality. See [START_REF] Ollivier | A January 2005 invitation to random groups[END_REF] for a proof by Y. Ollivier.

Lemma 3.7 (Local isoperimetric inequality

). Let s > 0. If d < 1/2, then for K = K 1 -2d -s 2 ,

Abstract van Kampen diagrams

Definition 4.1 (Abstract diagram, Ollivier [START_REF] Ollivier | A January 2005 invitation to random groups[END_REF]). An abstract van Kampen diagram D is a finite, planar and simply-connected 2-complex (V, E, F ) with a labeling function on faces by integer numbers ϕ 2 :

F → {1, 1 -, 2, 2 -, . . . , k, k -} satisfying ϕ 2 (f -1 ) = ϕ 2 (f ) -. We denote D = (V, E, F, ϕ 2 ),
By convention (i -) -= i for any 1 ≤ i ≤ k. The numbers {1, . . . , k} are called abstract relators of D.

Similarly to a van Kampen diagram, a pair of faces f, f ′ ∈ F is reducible if they have the same label, and they share an edge at the same position of their boundaries. An abstract diagram is called reduced if there is no reducible pair of faces.

Let D = (V, E, F, ϕ 1 , ϕ 2 ) be a van Kampen diagram of a group presentation G = X|R . Let {r 1 , . . . , r k } ⊂ R be the set of relators used in D. Define ϕ 2 :

F → {1, 1 -, . . . , k, k -} by ϕ 2 (f ) = i if ϕ 2 (f ) = r i .
(f ) = r i if and only if ϕ 2 (f ) = i gives a diagram D = (V, E, F, ϕ 1 , ϕ 2 ) of G. The k-tuple (r 1 , . . . , r k ) is called a filling of D. As we picked different relators, D is reduced if and only if a filled diagram D is reduced. 2 1 f illing ----→ D r 2 r 1

D

We assume that faces with the same label of D have the same boundary length, otherwise D would never be fillable. Denote ℓ i the length of the abstract relator i for 1 ≤ i ≤ k. Let ℓ = max{ℓ 1 , . . . , ℓ k } be the maximal boundary length of faces of D.

Notation. The pairs of integers (i, 1), . . . , (i, ℓ i ) are called abstract letters of i.

The set of abstract letters of D, denoted X, is then a subset of {1, . . . , k} × {1, . . . , ℓ}, endowed with the lexicographic order.

We decorate undirected edges of D by abstract letters and directions. Let f ∈ F labeled by i and let e ∈ E at the j-th position of ∂f . The edge {e, e -1 } is decorated, on the side of {f, f -1 }, by an arrow indicating the direction of e and the abstract letter (i, j). This decoration on {e, e -1 } is called the decoration from f at the position j. The number of decorations on an edge {e, e -1 } is the number of its adjacent faces {f, f -1 } with multiplicity (0, 1 or 2 when D is planar).

2 1 (2, 3) (1, 4)
For any filling (r 1 , . . . , r k ) of D, we construct the canonical function φ : X → X ± such that r i = φ(i, 1) . . . φ(i, ℓ i ) for any 1 ≤ i ≤ k. If an edge {e, e -1 } is decorated by two abstract letters (i, j), (i ′ , j ′ ), then φ(i ′ , j ′ ) = φ(i, j) if they have the same direction, or φ(i ′ , j ′ ) = φ(i, j) -1 if they have opposite directions. For example, the diagram above deduce ϕ(1, 4) = ϕ(2, 3) -1 .

Note that if D is reduced, then by definition an abstract letter can not be decorated twice on an edge with the same direction. If D is fillable (by the set of all relators), then an abstract letter (i, j) can not be decorated twice on an undirected edge with opposite directions, otherwise we have φ(i, j) = φ(i, j) -1 in the set of generators X.

1 1 (1, 4) (1, 4) 1 1
(1, 4) [START_REF] Antoniuk | Random triangular groups at density 1/3[END_REF][START_REF] Arzhantseva | Generic properties of finitely presented groups and Howson's theorem[END_REF] In the following we assume that D is fillable and reduced, so that the abstract letters decorated on an edge {e, e -1 } are all different. In particular, there exists a unique face {f, f -1 } (at a unique position) from which the decoration is (lexicographically) minimal. Whence the following two definitions. Definition 4.2 (Preferred face of an edge). Let {e, e -1 } be an edge of D. Let {f, f -1 } be the adjacent face of {e, e -1 } from which the decoration is minimal. Then {f, f -1 } is called the preferred face of {e, e -1 }. Definition 4.3 (free-to-fill). An abstract letter (i, j) of D is free-to-fill if, for any edge {e, e -1 } decorated by (i, j), it is the minimal decoration on {e, e -1 }.

Note that an abstract letter (i, j) is free-to-fill if and only if every face f labeled by i is the preferred face of its j-th boundary edge. In other words, if (i, j) is not free-tofill, then there exists an edge {e, e -1 } decorated by (i, j) that has another decoration (i ′ , j ′ ) < (i, j).

For example, in the abstract diagram below, (1, 4), (2, 1) and (2, 2) are not free-tofill. The other abstract letters are free-to-fill.

1 1 2 Denote F + = {f ∈ F | ϕ 2 (f ) ∈ {1, . . . , k}}.
It gives a preferred orientation for each undirected face of D = (V, E, F, ϕ 2 ). Let E be the set of undirected edges of D. Lemma 4.4. Let D be a reduced fillable abstract diagram without isolated edges. For every face f ∈ F + , let E f be the set of edges {e, e -1 } on the boundary of {f,

f -1 } such that {f, f -1 } is the preferred face of {e, e -1 }. Then E = f ∈F + E f .
Proof. For every edge {e, e -1 } there exists a unique face f ∈ F + such that {e, e -1 } ∈ E f . Hence the sets E f with f ∈ F + are pairwise disjoint. Their reunion is the set of edges because every edge is adjacent to at least one face.

Abstract distortion van Kampen diagrams

We generalize the idea of abstract diagrams to distortion van Kampen diagrams. In the following, an abstract distortion diagram ( D, p) is reduced, fillable and without isolated edges. Recall that X ⊂ {1, . . . , k}×{1, . . . , ℓ} is the set of abstract letters. Let p be the set of undirected edges given by p. In an abstract distortion diagram we distinguish between two types of free-to-fill abstract letters: those that decorate an edge of p and those that do not. Definition 4.6. Let (i, j) be an abstract letter of ( D, p).

(i) (i, j) is free-to-fill if it is free-to-fill for the abstract diagram D and it does not decorate any edge of p.

(ii) (i, j) is semi-free-to-fill if it is free-to-fill for the abstract diagram D and it decorates an edge of p.

(iii) Otherwise (i, j) is not free-to-fill.

Notation. Let i be an abstract relator of D. We denote α i the number of faces labeled by i, η i the number of free-to-fill abstract letters of i, and η ′ i the number of semi-freeto-fill abstract letters of i.

Note that ℓ

i -η i -η ′
i is the number of non free-to-fill edges. Lemma 4.7. Recall that E f is the set of edges on the boundary of f that prefers {f, f -1 }. Let i be an abstract relator. For any face f ∈ F with ϕ 2 (f ) = i, we have

η ′ i ≤ |E f ∩ p| and η i ≤ |E f | -|E f ∩ p|.
Proof. Let {e, e -1 } be the edge at the j-th position of ∂f . It is decorated by (i, j). If {f, f -1 } is not preferred by {e, e -1 }, then (i, j) is not free-to-fill because there is a smaller decoration on {e, e -1 }. Thus, if {e, e -1 } ∈ E f ∩ p then (i, j) is semi-free-to-fill, which gives the first inequality. Similarly, if {e, e -1 } ∈ E f \p, then (i, j) is free-to-fill and we have the second inequality. Lemma 4.8. Recall that E is the set of undirected edges. The following two inequalities hold.

k i=1 α i η ′ i ≤ |p|, k i=1 α i η i ≤ |E| -|p|.
Proof. By Lemma 4.7, for every

1 ≤ i ≤ k α i η ′ i ≤ f ∈F, ϕ2(f )=i |E f ∩ p|.
Apply Lemma 4.4,

k i=1 α i η ′ i ≤ f ∈F + |E f ∩ p| ≤ |p|.
We get the second inequality by replacing η ′ i by η i and |p| by |E\p|.

The number of fillings of an abstract distortion diagram

Recall that B ℓ is the set of cyclically reduced words on X ± = {x ± 1 , . . . , x ± m } of length at most ℓ. Let Γ be a graph labeled by X with rk(Γ) ≤ r.

Let ( D, p) be an abstract distortion diagram with k abstract relators. Assume that D is reduced, fillable and has no isolated edges. Let ℓ be the longest boundary length of faces of D.

Denote N ℓ ( D, p, Γ) the set of fillings (r 1 , . . . , r k ) of ( D, p) by (B ℓ , Γ). In this subsection, we give an upper bound of the number of fillings |N ℓ ( D, p, Γ)|.

Lemma 4.9. The number of reduced words u of length L that is readable on Γ is at most 2|Γ|(2r -1) L . By definition, there is an edge {e 1 , e -1 1 } decorated by (i, j) having a smaller decoration (i ′ , j ′ ) < (i, j). Let {f, f -1 }, {f ′ , f ′ -1 } be the faces attached by {e 1 , e -1 1 } such that f is labeled by i and f ′ is labeled by i ′ . Let {e 2 , e -1 2 } be the edge next to {e 1 , e -1 1 }, decorated by (i, j + 1) from the face {f, f -1 }. As the vertex between e 1 and e 2 is not distinguished, {e 2 , e -1 2 } is attached to the face {f ′ , f ′ -1 }. It is then decorated by (i ′ , j ′ +1) or (i ′ , j ′ -1) from {f ′ , f ′ -1 }. Because (i, j + 1) is free-to-fill, we have (i, j + 1) < (i ′ , j ′ + 1) or (i, j + 1) < (i ′ , j ′ -1). Both are impossible because (i, j) > (i ′ , j ′ ).

(i, j)

(i ′ , j ′ ) (i, j + 1) i i ′ case 2. (i, j) (i ′ , j ′ ) (i, j + 1) i i ′ case 3.
case 3. (i, j) is free-to-fill or semi-free-to-fill, and (i, j + 1) is not free-to-fill: By the same argument, there exists an abstract letter (i ′ , j ′ ) < (i, j + 1) such that (i, j) < (i ′ , j ′ + 1) or (i, j) < (i ′ , j ′ -1). The second one is obviously impossible. If the first one held, then (i ′ , j ′ ) < (i, j + 1) < (i ′ , j ′ + 2), so (i ′ , j ′ ) = (i, j), and there was an edge decorated by (i, j) and (i, j + 1) with opposite directions. The canonical function φ : X → X gives φ(i, j + 1) = φ(i, j) -1 , which is impossible because r i = φ(i, 1) . . . φ(i, ℓ i ) should be a reduced word. (ii) The number of elementary segments of an abstract letter i is at most 3| D| 2 .

Proof. The underlying 1-complex of D is a graph of rank | D| without isolated edges. By Lemma 2.1 there are at most 2(| D| -1) vertices of degree ≥ 3. We add k ≤ | D| starting points and 2 endpoints of p, there are at most 3| D| distinguished vertices on ( D, p).

The number of faces of D labeled by i is at most | D|. Every face brings at most 3| D| marked vertices to ∂i, so there are at most 3| D| 2 marked vertices on ∂i. Lemma 4.12. Let ( D, p) be a reduced abstract distortion diagram with no isolated edges and with k abstract relators. Let Γ be a labeled graph with rk(Γ) ≤ r. Recall that η i is the number of free-to-fill abstract letters of i and η ′ i is the number of semifree-to-fill abstract letters of i.

|N ℓ ( D, p, Γ)| ≤ 2m 2m -1 k (2|Γ|) 3| D| 2 k (2m -1) k i=1 ηi (2r -1) k i=1 η ′ i .
Proof. We fill abstract letters of D in lexicographic order. We shall prove that if the abstract relators 1, . . . , i -1 are filled, then there are at most 2m 2m -1 (2|Γ|) 3| D| 2 (2m -1) ηi (2r -1) η ′ i ways to fill the i-th abstract relator. By Lemma 4.10, we fill elementary segments of i in order. Let u be an elementary segment of i. If u is free-to-fill, then there are at most (2m -1) |u| ways to fill u, or at most 2m(2m -1) |u|-1 ways if u is the first segment of i. If u is semi-free-to-fill, then there are at most 2|Γ|(2r -1) |u| ways to fill u by lemma 4.9. If u is not free-to-fill there is only one choice.

The sum of the lengths of free-to-fill segments is η i , and the sum of the lengths of semi-free-to-fill segments is η ′ i . As the number of semi-free-to-fill segments is at most 3| D| 2 (Lemma 4.11), there are at most 2m(2m -1) ηi-1 (2|Γ|) 3| D| 2 (2r -1) η ′ i ways to fill the abstract relator i.

Freiheitssatz for random groups

Recall that B ℓ is the set of cyclically reduced words of X ± = {x ± 1 , . . . , x ± m }, and that |B ℓ | = (2m -1) ℓ+o(ℓ) . The set of cyclically reduced words on X

± r = {x ± 1 , . . . , x ± r } of length at most ℓ is of cardinality (2r -1) ℓ+o(ℓ) . Its density in B ℓ is c r = log 2m-1 (2r -1).
In this section, we prove that there is a phase transition at density In particular, a.s.s. every subgroup of G ℓ (m, d) generated by a reduced labeled graph Γ with rk(Γ) ≤ r and |Γ| ≤ dr-d 5 ℓ is a free group of rank r. In particular, a.a.s. x 1 , . . . , x r freely generate a free subgroup of G ℓ (m, d).

d r = min 1 2 , 1 -c r .

Statement of the theorem

Proof of theorem 5.1.1. We assume that d < 1/2, otherwise a.a.s. G ℓ (m, d) is trivial by Theorem 3.6. Recall that X = {x 1 , . . . , x m } and X r = {x 1 , . . . , x r }.

Let A ℓ be the set of words of type x r+1 w where w is a cyclically reduced word of X ± r of length ℓ -1. The density of (A ℓ ) in (B ℓ ) is c r . By hypothesis c r + d > 1.

Apply the intersection formula (Theorem 3.4), a.a.s. the intersection R ℓ ∩ A ℓ is not empty. Hence a.a.s. there exists a cyclically reduced word w r+1 of X ± r such that x r+1 w r+1 ∈ R ℓ , which implies x r+1 = G ℓ w r+1 .

Apply the same argument to the other generators x r+2 , . . . , x m . A.a.s. there are cyclically words w r+1 , . . . , w m of X ± r such that x i = G ℓ w i for any r + 1 ≤ i ≤ m. Hence a.a.s. every word of X ± equals to a word of X ± r in G ℓ .

The proof of the second assertion is similar to the proof of Theorem 3.6.2. We work first on a local result. Proof. We shall prove the lemma in four steps. We omit "for ℓ large enough" in every step. Recall that α i is the number of faces labeled by i, η i the number of free-to-fill abstract letters of i, and η ′ i the number of semi-free-to-fill abstract letters of i.

Step 1:

log 2m-1 P ≤ k i=1 (η i + c r η ′ i + (d -1 + 2ε d )ℓ) + 10K 3 log 2m-1 ℓ. (1)
According to Proposition 3. Hence the inequality (1) by applying log 2m-1 .

Step 2:

| D| log 2m-1 P -10K 3 log 2m-1 ℓ ≤ k i=1 α i (η i + c r η ′ i + (d -1 + 2ε d )ℓ). ( 2
)
Let D i be the sub-diagram of D consisting of the faces labeled by the first i abstract relators 1 ± , . . . , i ± and the edges attached to them. Apply (1) to D i , and denote P i the probability obtained. We have log 2m-1 P ≤ log 2m-1 P i ≤ ≥| D|(log 2m-1 P -10K 3 log 2m-1 ℓ).

Step 3: log 2m-1 P ≤ d - Combine with (2) we get the inequality (3)

Step 4: d -

1 2 + 2ε d ℓ + c r - 1 2 + ε d |∂ D| | D| ≤ -2ε d ℓ. (4)
Recall that c r = log 2m-1 (2r -1). Note that |∂ D| ≤ ℓ| D| and that d = d r -5ε d . There are two cases:

Corollary 2 .

 2 If d r < d < d r-1 , then a.a.s. the group G ℓ (m, d) = X|R ℓ admits a presentation with r generators X r |R ′ ℓ satisfying the Magnus Freiheitssatz property.

Definition 2 . 4 (ΓLemma 2 . 5 .

 2425 Distortion diagram). A distortion van Kampen diagram of (G, Γ) is a pair (D, p) where D is a van Kampen diagram of G and p is a cyclic sub-path ∂D whose labeling word is readable on Γ. p D Let λ ≥ 1. If every disk-like and reduced distortion van Kampen diagram

Theorem 2 . 7 .

 27 (Local-global principal of hyperbolicity) For any α > 0 and ε > 0, there exists an integer K = K(α, ε) such that, if every reduced disk-like diagram D with |D| ≤ K satisfies |∂D| ≥ αℓ|D|, then every reduced diagram D satisfies |∂D| ≥ (α -ε)ℓ|D|.

Proposition 3 . 3 (

 33 Similar to[START_REF] Tsai | Density of random subsets and applications to group theory[END_REF] Lemma 3.10). Let A = (A ℓ ) be a densable sequence of permutation invariant random subsets ofE = (E ℓ ) with density d. Let ε > 0. Denote Q ℓ the event |E ℓ | d-ε ≤ |A ℓ | ≤ |E ℓ | d+ε (we have a.a.s. Q ℓ by definition). Let e 1 , . . . , e k be distinct elements in E ℓ . For ℓ large enough,

Theorem 3 . 6 (

 36 Phase transition at density1/2). Let G(m, d) = (G ℓ (m, d)) = ( X|R ℓ )be a sequence of random groups at density d.1. If d > 1/2, then a.a.s. G ℓ (m, d) is a trivial group. 2. If d < 1/2,then a.a.s. G ℓ (m, d) is a hyperbolic group, and the Cayley graph Cay(G ℓ , X) is δ-hyperbolic with δ = 4ℓ 1-2d . In addition, for any s > 0, a.a.s. every reduced van Kampen diagram D of G ℓ (m, d) satisfies the isoperimetric inequality |∂D| ≥ (1 -2d -s)ℓ|D|.

  We obtain an abstract diagram D = (V, E, F, ϕ 2 ) with k abstract relators, called an underlying abstract diagram of D. An abstract diagram D is fillable by a group presentation G = X|R (or by a set of relators R) if there exists a van Kampen diagram D of G, called a filled diagram of D, whose underlying abstract diagram is D. That is to say, there exists k different relators r 1 , . . . , r k ∈ R such that the construction ϕ 2

Definition 4 . 5 (

 45 Abstract distortion diagram). An abstract distortion van Kampen diagram is a pair ( D, p) where D is an abstract diagram and p is a path on ∂ D. Let G = X|R be a group presentation and let Γ be a labeled graph. An abstract distortion diagram ( D, p) is fillable by the pair (G, Γ) (or by the pair (R, Γ)) if there exists a filled diagram D of D such that (D, p) is a distortion diagram of (G, Γ). The distortion diagram (D, p) is called a filled distortion diagram of ( D, p).

Lemma 4 . 11 .

 411 Let ( D, p) be an abstract distortion diagram with no isolated edges. (i) The number of distinguished vertices of ( D, p) is at most 3| D|.

Theorem 5 . 1 ( 2 .

 512 Phase transition at density d r ). Let G(m, d) = (G ℓ (m, d)) be a sequence of random groups at density d. 1. If d > d r , then a.a.s., G ℓ (m, d) is generated by x 1 , . . . , x r (or by any subset of X of cardinality r). If d < d r , then a.a.s., for every reduced labeled graph Γ with rk(Γ) ≤ r and |Γ| ≤ dr-d 5 ℓ, the canonical map Γ → Cay(G ℓ , X) is a 10 dr-d -quasi-isometric embedding.

Lemma 5 . 2 (

 52 Local diagrams). Let K > 0. Let (G ℓ ) = (G ℓ (m, d)) be a sequence of random groups with d < d r . Then a.a.s. for every reduced labeled graph Γ with rk(Γ) ≤ r and |Γ| ≤ dr-d 5 ℓ, every disc-like reduced distortion diagram (D, p) of(G ℓ , Γ) with |D| ≤ K satisfies |p| ≤ 1 -d r -d 5 |∂D|. (⋆)The proof of this lemma is in the next subsection.Proof of Theorem 5.1.2 by Lemma 5.2. By Lemma 3.1 and Theorem 3.6, we can assume that every diagramD of G ℓ (m, d) satisfies |∂D| ≥ (1 -2d)/2|D|ℓ and that G ℓ (m, d) is δ-hyperbolic with δ = 4ℓ1-2d . Let Γ be a reduced labeled graph with |Γ| ≤ dr-d 5 ℓ and rk(Γ) ≤ r. Let λ = 5 dr-d . By the local-global principle of quasi-geodesics (Theorem 2.8), in order to prove that Γ → Cay(X, G ℓ ) is a (global) 2λ-quasi-isometric embedding, we prove that every reduced word u readable on Γ is a 4000λℓ 1-2d -local λ-quasi-geodesic. Let u be a reduced word read on Γ with |u| ≤ 4000λℓ 1-2d . Let v be a geodesic in G ℓ joining endpoints of the image of u in G ℓ . We shall prove that |u| ≤ λ|v|. By van Kampen's lemma (Lemma 2.3) there exists a diagram D of G ℓ whose boundary word is uv. By the isoperimetric inequality (Theorem 3.6.2),|D| ≤ 2|∂D| (1 -2d)ℓ ≤ 4|u| (1 -2d)ℓ ≤ 50000λ (1 -2d) 2 . Apply Lemma 5.2 with K = 50000λ (1-2d) 2 = 250000 (1-2d) 2 (dr-d) . If D is disk-like, then by (⋆) we have |u| ≤ 1 -d r -d 5 (|u| + |v|) ≤ λ 1 + λ (|u| + |v|),which implies |u| ≤ λ|v|.Otherwise we decompose D into discs and segments. By the same argument of Lemma 2.5, because every disc-like sub-diagram is a distortion diagram satisfying (⋆), we still have |u| ≤ λ|v|.

5. 2 5 .Lemma 5 . 3 (

 2553 Proof of Lemma 5.2 Let (G ℓ ) = (G ℓ (m, d)) = ( X|R ℓ ) be a sequence of random groups with density d < d r . To prove Proposition 5.2, we work first on the fillability of an abstract distortion diagram. Denoteε d = d r -d Let Q ℓ be the a.a.s. event (2m -1) (d-ε d )ℓ ≤ |R ℓ | ≤ (2m-1) (d+ε d )ℓ . Fillability of an abstract distortion diagram). Let K > 0. Let Γ be a reduced labeled graph with rk(Γ) ≤ r and |Γ| ≤ ε d ℓ. Let ( D, p) be a disc-like abstract distortion diagram with | D| ≤ K that satisfies |p| > (1 -ε d ) |∂ D|.Then for ℓ large enough,P = Pr ( D, p) is fillable by (G ℓ , Γ) Q ℓ ≤ ℓ 10K 3 (2m -1) -2ε d ℓ .

  3, if (r 1 , . . . , r k ) is a filling of D by B ℓ , then for ℓ large enough Pr (r 1 , . . . , r k∈ R ℓ | Q ℓ ) ≤ (2m -1) k(d-1+2ε d )ℓ . Recall that N ℓ ( D, p, Γ) is the set of fillings of ( D, p) by (B ℓ , Γ).Apply Lemma 4.12 with |Γ| ≤ ε d ℓ and | D| ≤ K,Pr ( D, p) is fillable by (G ℓ , Γ) Q ℓ ≤ (r1,...,r k )∈N ℓ ( D,p,Γ) Pr (r 1 , . . . , r k ∈ R ℓ | Q ℓ ) ≤|N ℓ ( D, p, Γ)|(2m -1) k(d-1+2ε d )ℓ ≤ℓ 10K 3 (2m -1) k i=1 ηi (2r -1) k i=1 η ′ i (2m -1) k(d-1+2ε d )ℓ .

(

  η s +c r η ′ s +(d-1+2ε d )ℓ)+10K 3 log 2m-1 ℓ.Without loss of generality, we assume α 1 ≥ α 2 ≥ • • • ≥ α k . Note that log 2m-1 P is negative and that α 1 ≤ | D|. By Abel's summation formula, with convention α k+1 = 0,k i=1 α i (c r η ′ i + η i + (d -1 + 2ε d )ℓ) = k i=1 (α i -α i+1 ) i s=1 (c r η ′ s + η s + (d -1 + 2ε d )ℓ) ≥ k i=1 (α i -α i+1 )(log 2m-1 P -10K 3 log 2m-1 ℓ)≥α 1 (log 2m-1 P -10K 3 log 2m-1 ℓ)

1 2 + 2 + 2 |∂- 1 2 + 2ε d | D|ℓ + c r - 1 2 +

 22222 2ε d ℓ + c r -1 2 + ε d |∂ D| | D| + 10K 3 log 2m-1 ℓ. (3) Let ε ′ d > 0 such that |p| = (1 -ε ′ d )|∂ D|. By hypothesis ε ′ d < ε d . Because D is disc-likeand the boundary length of every face is ≤ ℓ, the number of undirected edges |E| is less then | D|ℓ-|∂ D| |∂ D|. Apply Lemma 4.8, we get k i=1α i η ′ i ≤ |p| = (1 -ε ′ d )|∂ D|, i = | D|. So we have k i=1 α i (c r η ′ i + η i + (d -1 + 2ε d )ℓ) ≤c r (1 -ε ′ d )|∂ D| + D| + (d -1 + 2ε d )| D|ℓ ≤ d ε d |∂ D|.

  9] Lemma 3.11 and Lemma 3.12 by C. Champetier. Theorem 2.6 (Isoperimetric inequality). Let ℓ be the longest relator length in R. The group G = X|R is hyperbolic if and only if there exists a real number β > 0 such that every reduced van Kampen diagram D satisfies the following isoperimetric inequality : |∂D| ≥ βℓ|D|. The local-global principle of hyperbolicity is due to M. Gromov in [13]. For other proofs, see [7] Chapter 8 by B. H. Bowditch or [25] by P. Papasoglu. We state here a sharpened version by Y. Ollivier in [23] Proposition 8.

	In this case, the Cayley graph Cay(G, X) is δ-hyperbolic with
	δ =	4ℓ β	.

  be sequences of events. If a.a.s. Q ℓ and a.a.s. "R ℓ under the condition Q ℓ ", then a.a.s. R ℓ .

Proof. Denote by Q ℓ the complement of Q ℓ . By the two hypotheses,

Pr(Q ℓ ) → 1 and Pr (R ℓ |Q ℓ ) → 1. Either Q ℓ is empty and Pr(R ℓ ) = Pr (R ℓ |Q ℓ ) → 1,

or by the formula of total probability

Proof. We estimate the number of paths p on Γ whose labeling word can be reduced. Take an oriented edge of Γ as the first edge of p, there are 2|Γ| choices. Every vertex is of degree at most 2r because rk(Γ) ≤ r. As p is reduced, every time we take the next edge, there are at most (2r -1) choices. Hence there are at most 2|Γ|(2r -1) L paths.

A vertex of ( D, p) is called distinguished if it is either of degree at least 3, or the starting point of a face, or an endpoint of p. Let i be an abstract letter of ( D, p). It can be regarded as a 2-complex with two inverse faces {i, i -} and 2ℓ i edges (i, 1), . . . , (i, ℓ i ) with their inverses, such that ∂i = (i, 1) . . . (i, ℓ i ).

A vertex of ∂i is marked if there exists a face f of D labeled by i such that the corresponding vertex is distinguished. Note that the starting point of ∂i is marked. Marked vertices divide the loop ∂i into segments, called elementary segments.

Consequently, an elementary segment is a sequence of abstract letters (i, j)(i, j + 1) . . . (i, j + t) such that, if a path e j . . . e j+t on D is decorated by (i, j) . . . (i, j + t), then it passes by no distinguished points except for its endpoints. Lemma 4.10. Let (i, j) . . . (i, j + t) be an elementary segment. The abstract letters (i, j), . . . , (i, j+t) are either all free-to-fill, or all semi-free-to-fill, or all not free-to-fill.

Proof. We shall check that if the vertex between two consecutive abstract letters (i, j) and (i, j + 1) is not marked, then they are of the same type.

Recall that if an edge {e 1 , e -1 1 } is decorated by (i, j) from the face {f, f -1 }, then there is an edge {e 2 , e -1 2 } next to {e 1 , e -1 1 }, decorated by (i, j + 1) from the same face {f, f -1 }. Assume that the vertex between (i, j) and (i, j + 1) is not marked so that the vertex between {e 1 , e -1 1 } and {e 2 , e -1 2 } is not distinguished. We suppose by contradiction that (i, j) and (i, j + 1) are not of the same type. There are 3 2 -3 = 6 cases, grouped into three cases. case 1. (i, j) is semi-free-to-fill and (i, j + 1) is free-to-fill, or inversely:

Recall that if (i, j) is semi-free-to-fill in the abstract distortion diagram ( D, p), then it decorates an undirected edge {e 1 , e -1 1 } on p. As (i, j + 1) is free-to-fill, the edge {e 2 , e -1 2 } decorated by (i, j + 1) from the same face is not on p. So the vertex between {e 1 , e -1 1 } and {e 2 , e -1 2 } is distinguished, contradiction.

case 2. (i, j) is not free-to-fill, and (i, j + 1) is free-to-fill or semi-free-to-fill:

By (3) and (4), for ℓ large enough log 2m-1 (P) ≤ -2ε d ℓ + 10K 3 log 2m-1 ℓ.

By Lemma 2.1 and Lemma 2.2, we have the following two results.

So the probability that there exists a reduced labeled graph Γ with rk(Γ) ≤ r, |Γ| ≤ ε d ℓ and there exists a disc-like reduced distortion diagram (D, p) of (G ℓ , Γ) with |D| ≤ K that satisfies |p| > (1 -ε d ) |∂ D| is bounded by (2m -1) -ε d ℓ+O(log ℓ) , which goes to 0 when ℓ goes to infinity. This completes the proof of Theorem 5.1.