Schreier coset graph
From Wikipedia, the free encyclopedia
In the area of mathematics called combinatorial group theory, the Schreier coset graph is a graph associated with a group G, a generating set of G, and a subgroup of G. The Schreier graph encodes the abstract structure of the group modulo an equivalence relation formed by the cosets of the subgroup.
The graph is named after Otto Schreier, who used the term "Nebengruppenbild".[1] An equivalent definition was made in an early paper of Todd and Coxeter.[2]
Given a group G, a subgroup H ≤ G, and a generating set S = {si: i in I} of G, the Schreier graph Sch(G, H, S) is a graph whose vertices are the right cosets Hg = {hg: h in H} 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 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 of the group G itself is the Schreier coset graph for H = {1G}.[3]
A spanning tree of a Schreier coset graph corresponds to a Schreier transversal, as in Schreier's subgroup lemma.[4]
The book "Categories and Groupoids" listed below relates this to the theory of covering morphisms of groupoids. A subgroup H of a group G determines a covering morphism of groupoids and if S is a generating set for G then its inverse image under p is the Schreier graph of (G, S).
