In the area of mathematics called

combinatorial group theory In mathematics, combinatorial group theory is the theory of free groups, and the concept of a presentation of a group by generators and relations. It is much used in geometric topology, the fundamental group of a simplicial complex having in a nat ...

, the Schreier coset graph is a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

associated with a

group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...

''G'', a

generating set In mathematics and physics, the term generator or generating set may refer to any of a number of related concepts. The underlying concept in each case is that of a smaller set of objects, together with a set of operations that can be applied to ...

of ''G'', and a

subgroup In group theory, a branch of mathematics, given a group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ''H'' is a subgroup ...

''H'' ≤ ''G''. The Schreier graph encodes the abstract structure of a group modulo an equivalence relation formed by the

coset In mathematics, specifically group theory, a subgroup of a group may be used to decompose the underlying set of into disjoint, equal-size subsets called cosets. There are ''left cosets'' and ''right cosets''. Cosets (both left and right) ...

. The graph is named after

Otto Schreier Otto Schreier (3 March 1901 in Vienna, Austria – 2 June 1929 in Hamburg, Germany) was a Jewish-Austrian mathematician who made major contributions in combinatorial group theory and in the topology of Lie groups. Life His parents were the arch ...

, who used the term “Nebengruppenbild”. An equivalent definition was made in an early paper of Todd and Coxeter.

Description

The vertices of the graph are the right

s ''Hg'' = for ''g'' in ''G''. The edges of the graph are of the form (''Hg'', ''Hgx_i''). The

Cayley graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cay ...

of the group ''G'' with is the Schreier coset graph for ''H'' = . A spanning tree of a Schreier coset graph corresponds to a Schreier transversal, as in Schreier's subgroup lemma . The book "Categories and Groupoids" listed below relates this to the theory of covering morphisms of

groupoid In mathematics, especially in category theory and homotopy theory, a groupoid (less often Brandt groupoid or virtual group) generalises the notion of group in several equivalent ways. A groupoid can be seen as a: *'' Group'' with a partial func ...

s. A subgroup ''H'' of a group ''G'' determines a covering morphism of groupoids

p: K \rightarrow G

and if ''X'' is a generating set for ''G'' then its

inverse image In mathematics, the image of a function is the set of all output values it may produce. More generally, evaluating a given function f at each element of a given subset A of its domain produces a set, called the "image of A under (or through) ...

under ''p'' is the Schreier graph of (''G'', ''X'').

Applications

The graph is useful to understand coset enumeration and the

Todd–Coxeter algorithm In group theory, the Todd–Coxeter algorithm, created by J. A. Todd and H. S. M. Coxeter in 1936, is an algorithm for solving the coset enumeration problem. Given a presentation of a group ''G'' by generators and relations and a subgroup ''H'' ...

. Coset graphs can be used to form large

permutation representation In mathematics, the term permutation representation of a (typically finite) group G can refer to either of two closely related notions: a representation of G as a group of permutations, or as a group of permutation matrices. The term also refers ...

s of groups and were used by

Graham Higman Graham Higman FRS (19 January 1917 – 8 April 2008) was a prominent English mathematician known for his contributions to group theory. Biography Higman was born in Louth, Lincolnshire, and attended Sutton High School, Plymouth, winning a ...

to show that the

alternating group In mathematics, an alternating group is the group of even permutations of a finite set. The alternating group on a set of elements is called the alternating group of degree , or the alternating group on letters and denoted by or Basic pr ...

s of large enough degree are

Hurwitz group In mathematics, Hurwitz's automorphisms theorem bounds the order of the group of automorphisms, via orientation-preserving conformal mappings, of a compact Riemann surface of genus ''g'' > 1, stating that the number of such automorphisms ...

s, . Every vertex-transitive graph is a coset graph.

References

* * *
Schreier graphs of the Basilica group Authors: Daniele D'Angeli, Alfredo Donno, Michel Matter, Tatiana Nagnibeda
* Philip J. Higgins, Categories and Groupoids, van Nostrand, New York, Lecture Notes, 1971

{{algebra-stub Combinatorial group theory