Now let us prove Theorem 1.3.
Proof. Let G be a group with a presentation (1.1) and Δ be a diagram as in the statement of the theorem. Since Δ is a disc diagram, we can place it on the sphere. We construct the dual graph Φ to the 1-skeleton of the diagram Δ in the following way.
Place a vertex of the new graph Φ into each
The main idea of the proof is to study the dual graph Φ and to prove the necessary inequality by the reasoning of Euler characteristic of sphere.
First, note that among the faces of the graph Φ there are no 1-gons (because the boundary labels of the cells of the diagram Δ are cyclically irreducible) or 2-gons (because in the previous paragraphs we have constructed exactly one edge crossing every maximal boundary arc of Δ). Therefore every face of Φ is at least a triangle. Thus, denoting the number of vertices, edges and faces of the graph Φ by V, E and F respectively, and considering the usual Euler formula V − E + F = 2 we get the following inequality:
Now, suppose that the statement of the theorem does not hold. For each edge of the graph Φ connecting the vertices oi, oj lying in the cells Πi, Πj of the diagram Δ we attribute this edge to each of those vertices with the coefficient
Fix an arbitrary vertex o ≠ O. Denote the cell where the vertex o lies by Π and consider the following possibilities.
(1)Let the contour ∂Π consist only of interior arcs. Due to the
(2)Let there be exactly one exterior arc p. Since we suppose that |p| ≤
(3)Let the cell Π have two exterior edges p1, p2. Note that the end of the arc p1 cannot be the beginning of the arc p2 (and vice versa) and they cannot be separated by 0-edges only because otherwise we could cut the diagram Δ with edges f1, . . . , fl such that φ(fi) = 1 for all i = 1, . . . , l and due to van Kampen lemma obtain two proper subwords φ(q1), φ(q2) of the word φ(q) (where q is the contour of the diagram Δ) equal to 1 in the group G. That contradicts the condition of φ(q) being cyclically irreducible.
Therefore, the cell Π has at least two distinct interior boundary arcs and there are at least
(4)If the cell Π has at least three exterior arcs, there are at least three edges of the graph Φ attributed to the vertex o.
Considering those possibilities for all vertices of the graph Φ except the “exterior” vertex O we see that
and that contradicts the inequality (1.3). This contradiction completes the proof.
1.3Algorithmic problems and the Dehn algorithm
In this section we give a brief overview of two algorithmic problems in the combinatorial group theory which were already mentioned in the context of group diagrams — the word problem and the conjugacy problem.
Consider a group G given by its presentation (1.1) which is effective in the sense that for every word R we can algorithmically determine whether it lies in the set
(1)The word problem: is there an algorithm which for any pair of words U, V in the group alphabet determines whether those words are equal in the group G or not?
(2)The conjugacy problem: is there an algorithm which for any pair of words U, V in the group alphabet determines whether those words are conjugate in the group G or not?
Naturally the word problem can be reformulated in the form
“is there an algorithm which for any word W in the group alphabet determines whether W = 1 is in the group G or not?”
because U = V is in the group G if and only if UV−1 = 1 is in the group G.
It turns out that the small cancellation theory is a very useful instrument in the study of the word and conjugacy problems. In particular, the following algorithm (originally due to Dehn, see [Schupp, 1968]) solves the word problem in the groups with the condition C′(λ),
The Dehn algorithm. The algorithm is inductive, so we may assume that for any word V of the length less than n we can algorithmically determine whether V = 1 is in the group G or not.
Now
