Schreier coset graph
Encyclopedia
In the area of mathematics
called combinatorial group theory
, the Schreier coset graph is a graph
associated to a group
G, a generating set
{ xi : i in I }, and a subgroup
H ≤ G.
are the right coset
s Hg = { hg : h in H } for g in G.
The edges of the graph are of the form (Hg,Hgxi).
The Cayley graph
of the group G with { xi : i in I } is the Schreier coset graph for H = { 1G },.
A spanning tree
of a Schreier coset graph corresponds to a Schreier transversal, as in Schreier's subgroup lemma
, .
and the Todd–Coxeter algorithm.
Coset graphs can be used to form large permutation representations of groups and were used by Graham Higman
to show that the alternating groups of large enough degree are Hurwitz groups, .
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
called combinatorial group theory
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...
, the Schreier coset graph is a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
associated to a group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
G, a generating set
Generating set of a group
In abstract algebra, a generating set of a group is a subset that is not contained in any proper subgroup of the group. Equivalently, a generating set of a group is a subset such that every element of the group can be expressed as the combination of finitely many elements of the subset and their...
{ xi : i in I }, and a subgroup
Subgroup
In group theory, 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 of G if the restriction of * to H x H is a group operation on H...
H ≤ G.
Description
The vertices of the graphVertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
are the right coset
Coset
In mathematics, if G is a group, and H is a subgroup of G, and g is an element of G, thenA coset is a left or right coset of some subgroup in G...
s Hg = { hg : h in H } for g in G.
The edges of the graph are of the form (Hg,Hgxi).
The Cayley graph
Cayley graph
In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem and uses a specified, usually finite, set of generators for the group...
of the group G with { xi : i in I } is the Schreier coset graph for H = { 1G },.
A spanning tree
Spanning tree
Spanning tree can refer to:* Spanning tree , a tree which contains every vertex of a more general graph* Spanning tree protocol, a protocol for finding spanning trees in bridged networks...
of a Schreier coset graph corresponds to a Schreier transversal, as in Schreier's subgroup lemma
Schreier's subgroup lemma
Schreier's subgroup lemma is a theorem in group theory used in the Schreier–Sims algorithm and also for finding a presentation of a subgroup.-Definition:Suppose H is a subgroup of G, which is finitely generated with generating set S, that is, G = ....
, .
Applications
The graph is useful to understand coset enumerationCoset 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...
and the Todd–Coxeter algorithm.
Coset graphs can be used to form large permutation representations of groups and were used by Graham Higman
Graham Higman
Graham Higman FRS was a leading British mathematician. He is known for his contributions to group theory....
to show that the alternating groups of large enough degree are Hurwitz groups, .