# groups graphs and surfaces

Topics: Presentation of a group, Free group, Group Pages: 16 (4198 words) Published: December 9, 2013
Graphs, Groups and Surfaces

1

Introduction

In this paper, we will discuss the interactions among graphs, groups and surfaces. For any given graph, we know that there is an automorphism group associated with it. On the other hand, for any group, we could associate with it a graph representation, namely a Cayley graph of presentations of the group. We will ﬁrst describe such a correspondence. Also, a graph is always embeddable in some surface. So we will then focus on properties of graphs in terms of their relation to surfaces. Thus, by using the Cayley graphs to describe a group, we can talk about the embeddability of a group. In this way, we see that we can talk about the geometries of a group by looking at their Cayley graphs. Another useful geometric tool to analyze groups is the Dehn diagram. Therefore, in the last section, we will give some comments on how graph theory may be helpful to Dehn diagrams of Coxeter groups.

1

2

Cayley Graph of Group Presentations

In this section we will see how Cayley graphs correspond to a particular presentation of a group and how the properties of a group are reﬂected in the Cayley graphs. Deﬁnition 2.1. Let G be a group, with S = {s1 , s2 , . . . } a subset of the element set of G. Deﬁne S −1 = {s−1 , s−1 , . . . } A word w in S is a ﬁnite product a1 · · · an , where for all 1

2
1 ≤ i ≤ n, ai ∈ S ∪ S −1 . We say S generates G if every element of G is a ﬁnite product in S and each element of S is a generator for G. A relation is an equality between two words in S. A relator is a word that equals the identity element of G. Deﬁnition 2.2. Let S be a set and let FS be the free group on S. Let R be a set of words on S. < S|R > id deﬁned as FS quotiented by the normal closure of R. G has presentation < S|R > if G is isomorphic to < S|R >.

Deﬁnition 2.3. For every group presentation there is an associated Cayley graph Λ(G, S): • Every vertex is labelled an element of G.
• Each edge is colored by a generator in S.
• There is a directed edge from g to h if and only if there is a generator s such that h = gs.
Below we will list some elementary properties of Cayley graphs: A walk gives a word. Succession of walks gives the multiplication of elements. A closed walk gives a trivial word. A cycle is a cyclically reduced trivial word.

It also turns out a Cayley graph is vertex transitive and we can label any vertex as the trivial element. This result is derived from the theorem below. 2

Theorem 2.1. Let Λ(G, S) be a Cayley graph for a group G. Then any automorphism group A(Λ(G, S)) of Λ(G, S) is isormophic to G,
Proof. Deﬁne φ : G → A(Λ(G, S)) by φ(g) = θg , where θg is the permutation on V (Λ(G, S)) by θg (gi ) = ggi . It is clear that θg is a permutation. To show it is well-deﬁned, notice θg (gi h) = g(gi h) = (ggi )h = θg (gi )h.

Now we want to show φ is a homomorphism. φ(gh)(u) = θgh (u) = ghu = θg (hu) = θg (θh (u)) = φ(g)φ(h)(u).
φ is also one-to-one, since θg (h) = h if and only if g = e. We are left to show φ is onto. Let θ ∈ A(Λ(G, S)) such that θ(e) = g. By the well-deﬁnedness of θ, for any h ∈ G, θ(h) = θ(eh) = θ(e)h = gh = θg (h) = φ(g)(h). There are other properties of groups and their presentations which translate into properties of Cayley graphs. Theorem 2.2. G is abelian if and only if for every pair of generators g and h, the walk ghg −1 h−1 is closed.

Proof. G is abelian if and only if its commutator subgroup is trivial if and only if for every pair of generators ghg −1 h−1 = e.
Redundant generators can also be identiﬁed by check whether the deletion of edges of a generator color still results in a Cayley graph for the group. Theorem 2.3. A generator s is redundant for a ﬁnite group if and only if the deletion of all edges colored h in Λ(G, S) leaves a strongly connected directed graph.

3

We can also ﬁnd sub-generated subgroups from the Cayley graph by looking at the components of the graph obtained by deleting all the edges of a particular...

References: [1] A. White, Graphs, Groups and Surfaces, Elsevier, New York, 1984.
[2] L. Beineke and R. Wilson, Topological Group Theory, Selected Topics in Graph Theory 1 (1978), 15 –49.
[3] J. Youngs, Minimal Imbeddings and the Genus of a Graph, Indiana Univ. Math. J. 12 (1963), no. 2, 303
–315.
16