In the area of

mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

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

, 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 discret ...

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, a subset of a group G is a subgroup of G if the members of that subset form a group with respect to the group operation in G. Formally, given a group (mathematics), group under a binary operation ...

of ''G''. The Schreier graph encodes the abstract structure of the 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. A simpler example is equ ...

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

s of the subgroup. 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 "". An equivalent definition was made in an early paper of Todd and Coxeter.

Description

Given a group ''G'', a subgroup ''H'' ≤ ''G'', and a generating set ''S'' = of ''G'', the Schreier graph Sch(''G'', ''H'', ''S'') is a graph whose vertices are the right

s ''Hg'' = for ''g'' in ''G'' and whose edges are of the form (''Hg'', ''Hgs'') for ''g'' in ''G'' and ''s'' in ''S''. More generally, if ''X'' is any ''G''-set, one can define a Schreier graph Sch(''G'', ''X'', ''S'') of the

action Action may refer to: * Action (philosophy), something which is done by a person * Action principles the heart of fundamental physics * Action (narrative), a literary mode * Action fiction, a type of genre fiction * Action game, a genre of video gam ...

of ''G'' on ''X'' (with respect to the generating set ''S''): its vertices are the elements of ''X'', and its edges are of the form (''x'', ''xs'') for ''x'' in ''X'' and ''s'' in ''S''. This includes the original Schreier coset graph definition, as ''H''\''G'' is a naturally a ''G''-set with respect to multiplication from the right. From an algebraic-topological perspective, the graph Sch(''G'', ''X'', ''S'') has no distinguished vertex, whereas Sch(''G'', ''H'', ''S'') has the distinguished vertex ''H'', and is thus a pointed graph. 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 (discrete mathematics), graph that encodes the abstract structure of a group (mathematics), group. Its definition is sug ...

of the group ''G'' itself 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 no ...

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

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

p: K \rightarrow G

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

inverse image In mathematics, for a function f: X \to Y, the image of an input value x is the single output value produced by f when passed x. The preimage of an output value y is the set of input values that produce y. More generally, evaluating f at each ...

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

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

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

to show that the

alternating group In mathematics, an alternating group is the Group (mathematics), 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 ...

s of large enough degree are Hurwitz groups . Stallings' core graphsJohn R. Stallings. "Topology of finite graphs." ''

Inventiones Mathematicae ''Inventiones Mathematicae'' is a mathematical journal published monthly by Springer Science+Business Media. It was established in 1966 and is regarded as one of the most prestigious mathematics journals in the world. The current (2023) managing ...

'', vol. 71 (1983), no. 3, pp. 551–565 are retracts of Schreier graphs of free groups, and are an essential tool for computing with subgroups of a free group. Every

vertex-transitive graph In the mathematics, mathematical field of graph theory, an Graph automorphism, automorphism is a permutation of the Vertex (graph theory), vertices such that edges are mapped to edges and non-edges are mapped to non-edges. A graph is a vertex-tr ...

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

Combinatorial group theory {{algebra-stub