In the area of

mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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 iden ...

''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 In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each 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 arc ...

, 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 Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed by ...

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

of the group ''G'' with is the Schreier coset graph for ''H'' = . A

spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...

of a Schreier coset graph corresponds to a Schreier transversal, as in

Schreier's subgroup lemma In mathematics, Schreier's lemma is a theorem in group theory used in the Schreier–Sims algorithm and also for finding a presentation of a subgroup. Statement Suppose H is a subgroup of G, which is finitely generated with generating set S, tha ...

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

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 In mathematics, coset enumeration is the problem of counting the cosets of a subgroup ''H'' of a group ''G'' given in terms of a presentation. As a by-product, one obtains a permutation representation for ''G'' on the cosets of ''H''. If ''H'' has ...

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'' of ...

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

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

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 In the mathematical field of graph theory, a vertex-transitive graph is a graph in which, given any two vertices and of , there is some automorphism :f : G \to G\ such that :f(v_1) = v_2.\ In other words, a graph is vertex-transitive i ...

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