Cayleygraph

In mathematics, a Cayleygraph is a graph describing the structure of a (usually finitely generated ) group. It depends on a given, usually finite set of generators of the group.

Arthur Cayley in 1878 has used first graphs to represent groups figuratively; an approach of Max Dehn (1911 ), Otto Schreier (1927) and others have changed. Because Dehns great contributions Cayley were sometimes ( Dehnsche ) called group pictures. Today Cayley are a central tool of geometric group theory.

  • 8.1 Cayleykomplexe
  • 8.2 Schreier graphs

Definition

Let G be a group and S a generating set. The Cayleygraph Γ = Γ (G, S) is colored and directed graph is constructed as follows:

  • Each element g of G is assigned a node: The node set V ( Γ ) of Γ is identified with G.
  • Each producer s of S is assigned a color cs.
  • For g ∈ G, s ∈ S, the nodes that belong to the elements g and gs, connected to a directed edge of the color cs. The edge set E ( Γ ) therefore consists of pairs of the form (g, gs ), where s ∈ S determines the color.

In the geometric group theory is usually assumed that the set S is finite and symmetrical, that is, S = S 1, and the neutral element of the group does not contain. In this case, the Cayleygraph, apart from the color, an ordinary graph: Its edges are not oriented, and it does not contain loops.

Examples

  • Let G = Z, the infinite cyclic group, and the set S consists of the standard generator 1 and its inverse (-1 in additive notation). The associated Cayleygraph is then an infinite chain.
  • The picture is similar when G = Zn the finite cyclic group of order n and S is again consists of two elements, the standard generator 1 of G and its inverse; then the Cayleygraph the n -cycle Cn.
  • The Cayleygraph of the direct product of groups is the Cartesian product of the respective Cayley. The Cayleygraph the free abelian group Z2 with a generating set consisting of the four elements (± 1, ± 1), is an infinite lattice in the plane R2, while the Cayleygraph for the direct product Zn × Zm with analog producers a finite n forms × m grid on the torus.
  • The Cayleygraph the dihedral group D4 with two generators a ( 90 ° clockwise rotation) and b ( horizontal mirroring) is shown on the right. Since b is its own inverse, which are the blue edges, which stand for the execution of b, drawn undirected. This choice of a and b corresponds to the presentation of
  • The relations of the group to this choice of generators can be found in Cayleygraph as cycles again, for example, provides a4 a closed path in the graph, also aba -3b.
  • Cayleygraph of the free group with two generators A and B and the set S = {a, b, a-1, b- 1} is shown on top in the article, where e denotes the neutral element. On an edge to go right corresponds to the right multiplication by a, while representing to go up multiplication by b. Since the free group has no relations, this graph contains no cycles.

Characterization

The question which may arise as Cayley graphs of a group G, can be answered as follows: The group G acts by left multiplication on itself (see also Cayley ). This effect also provides an action of G on its Cayley. Specifically sends an element h ∈ G a node g ∈ V ( Γ ) on the node hg ∈ V ( Γ ). The set of edges of the graph is respected by this effect, for an edge ( g, gs ) is mapped to the edge ( Hg, HGS). The effect of left multiplication of any group on itself is simply transitive. Accordingly, a Cayleygraph is knotentransitiv. This leads to the following characterizing Cayley:

To reconstruct the color of the graph by the group G and the generator set S, it selects a node v1 ∈ V ( Γ ) and labeled it with the neutral element of the group. Each node v of Γ is then the unique element g of G denotes that maps v1 to v. The set S of generators of G which delivers Γ as Cayley then, is the set of labels of the nodes that are adjacent to the selected node v1. The generator set is just finally, if the graph is finite locally, ie each node to a finite number of edges is adjazent.

However, it is not true that every knotentransitive graph occurs as Cayleygraph, and otherwise the above statement does not answer all the questions, of course, the structure of Cayley. For example, the assumption that each Cayleygraph contains a Hamilton cycle, known as the Lovász conjecture, unproved.

Simple properties

The Cayleygraph Γ (G, S) depends essentially on the choice of the generator set S. If, for example, S has k elements, so each node has of Γ k incoming and k outgoing edges. If S is chosen symmetrically, so Γ is a regular graph of degree k

Cycles, ie closed paths in Cayley represent relations ( see presentation of a group) between the elements of S. In

If a surjective group homomorphism, which is on the generator set S ' of G' is injective, then f induces a superposition of graphs

This is especially the case when a group G generated by k elements, all of order equal to 2, and the set S from these producers and their inverses is. Then the Cayleygraph Γ (G, S) is superimposed on the infinite regular tree of degree 2k, which is part of the free group over the same producers. Such a tree is then a universal covering of the Cayley and also means Cayleybaum or Bethe lattice.

Even if the set S is not generated, the group G, a graph Γ (G, S) can be constructed. However, he will not be contiguous and is not considered Cayleygraph. In this case, each connected component corresponds to a coset of the group generated by P.

Applications in group theory

Through the study of Cayley insights about the structure of the group can be obtained. Among other things, it is interesting to examine the adjacency matrix, which transmits in particular by means of the spectral theory of graphs, the geometric statements, which are obtained from the spectrum of linear operators in a discrete context.

Geometric Group Theory

For infinite groups is the rough geometry ( coarse geometry ) of the Cayley, or its equivalence class up to quasi- isometry, fundamental to the field of geometric group theory. For a finitely generated group is independent of the choice of a finite set S of generators, ie, an intrinsic property of the group. This is only interesting for infinite groups, since all finite groups - for S = G can be chosen - quasiisometrisch are to a point.

The Cayleygraph in this context is a metric picture of the group with the word metric is determined by the choice of producers.

Word metric

The word metric on the Cayley is given by the definition that will have all the edges of the graph length 1. Equivalent may be the distance between two group elements g, h, defined as the minimum number of factors from the given set of generators, which can be decomposed into so.

The word metric depends (as well as the Cayleygraph itself) from the generating set S. For several finite systems of generators but you get quasi- isometric Cayley. All given up to quasi- isometry geometric properties of graphene thus correspond to properties of groups.

In geometric group theory one tries to translate algebraic properties of groups in geometric properties of Cayley. A spectacular example of this is Gromows set that a group is virtually nilpotent if and only if it has polynomial volume growth Cayleygraph, ie the volume of balls of radius R is bounded by a polynomial in R upwards.

Word - hyperbolic groups

A group is called word - hyperbolic if it is δ - hyperbolic Cayleygraph for a δ > 0. This means that in each geodesic triangle, each lying on an edge of point distance < δ of at least one of the other two edges. This definition is (up to the exact value of the constant δ ) is invariant under quasi- isometry and therefore independent of the chosen system of generators.

Examples of word - hyperbolic groups are finite groups, virtually cyclic groups, finitely generated free groups, fundamental groups of compact surfaces of negative Euler characteristic and general fundamental groups of compact, negatively curved manifolds. In a way, random groups are word - hyperbolic.

Boundary at infinity

The Cayleygraph has an edge at infinity, formally defined as the set of equivalence classes of geodesic rays, where two rays are equivalent if and only if they have finite distance. The effect of the group on the boundary at infinity is a " chaotic " dynamical system and encodes many properties of the group.

Examples: for free groups is the edge at infinity a Cantor set, for fundamental groups of compact negatively curved n -manifolds of the boundary at infinity is a sphere, for " most" word - hyperbolic groups of the border at infinity is but a Menger sponge.

History

Cayley looked at the graph named after him in 1878 initially only for finite groups. In his unpublished notes on group theory, 1909-10 Max Dehn led the Cayley under the name " group image " field. Its main application was the solution of the word problem for fundamental groups of surfaces of genus ≥ 2 with geometric methods that today are part of the theory of hyperbolic groups. ( This is equivalent to solve the topological problem, let the curves that in the area tend to shrink to a point. ) This work was the beginning of today's geometric group theory.

Related constructions

From a presentation of a discrete group the Cayley several related objects can be formed.

Cayleykomplexe

The Cayleykomplex is the Cayley very similar construction. It is a cell complex that has the Cayley than 1 skeleton in addition, however, 2- cells to be glued. For the 2 cells in addition to the group G, and the generating amount of S is also a choice of ratios R are required, that is a presentation of G. Each R in relation provides for each node in a Cayley Cycles, along each of which a 2- cell is glued.

The Cayleykomplex the group Z2 with the presentation, for example, a tiling of the plane with unit squares whose 1- skeleton of the Cayleygraph of Z2 described above.

Schreier graphs

When are chosen as nodes instead of elements of the group G right cosets of a fixed subgroup H ⊂ G, we obtain a related construction, the Schreier graph Σ (G, H, S ), where S is a generator set of G again. If H is the trivial subgroup, so Σ (G, H, S ) is simply the back Cayleygraph Γ (G, S).

Pictures of Cayleygraph

171159
de