Schreier coset graph

Given a group G, a subgroup H ≤ G, and a generating set S = {s_i : 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 = {1_G} {{harv|Gross|Tucker|1987|p=73}}.

A spanning tree of a Schreier coset graph corresponds to a Schreier transversal, as in Schreier's subgroup lemma {{harv|Conder|2003}}.

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 $p:\; K\; \backslash rightarrow\; G$ and if S is a generating set for G then its inverse image under p is the Schreier graph of (G, S).

The graph is useful to understand coset enumeration 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 {{harv|Conder|2003}}.

Stallings' core graphsJohn R. Stallings. "Topology of finite graphs." Inventiones Mathematicae, 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 is a coset graph.

{{reflist}}

• {{Citation | last1=Magnus | first1=W. | last2=Karrass | first2=A. |last3=Solitar | first3=D. | title=Combinatorial Group Theory | publisher=Dover | year=1976 }}
• {{Citation | last1=Conder | first1=Marston |authorlink=Marston Conder| title=Groups St. Andrews 2001 in Oxford. Vol. I | publisher=Cambridge University Press | series=London Math. Soc. Lecture Note Ser. |mr=2051519 | year=2003 | volume=304 | chapter=Group actions on graphs, maps and surfaces with maximum symmetry | pages=63–91}}
• {{Citation | last1=Gross | first1=Jonathan L. | last2=Tucker | first2=Thomas W. | title=Topological graph theory | publisher=John Wiley & Sons | location=New York | series=Wiley-Interscience Series in Discrete Mathematics and Optimization | isbn=978-0-471-04926-5 |mr=898434 | year=1987}}
• [https://arxiv.org/abs/0911.2915 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, [http://www.tac.mta.ca/tac/reprints/articles/7/tr7abs.html Republished as TAC Reprint, 2005]

Category:Combinatorial group theory

{{algebra-stub}}