groups graphs and surfaces

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



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 first 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.



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 reflected in the Cayley graphs. Definition 2.1. Let G be a group, with S = {s1 , s2 , . . . } a subset of the element set of G. Define S −1 = {s−1 , s−1 , . . . } A word w in S is a finite product a1 · · · an , where for all 1

1 ≤ i ≤ n, ai ∈ S ∪ S −1 . We say S generates G if every element of G is a finite 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. Definition 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 defined as FS quotiented by the normal closure of R. G has presentation < S|R > if G is isomorphic to < S|R >.

Definition 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. Define φ : 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-defined, 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-definedness 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 identified 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 finite group if and only if the deletion of all edges colored h in Λ(G, S) leaves a strongly connected directed graph.


We can also find 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
Continue Reading

Please join StudyMode to read the full document

You May Also Find These Documents Helpful

  • Graph Theory Essay
  • Essay on Graphs: Graph Theory and Vertex
  • Graph Theory Essay
  • Graphs Essay
  • Graph Theory Essay
  • Graphs Essay
  • Surface Essay
  • Graph Theory Essay

Become a StudyMode Member

Sign Up - It's Free