Schreier coset graph

In the area of mathematics called combinatorial group theory, the Schreier coset graph is a graph associated with a group G, a generating set {x_i : i in I} of G, and a subgroup H ≤ G. The Schreier graph encodes the abstract structure of a group modulo an equivalence relation formed by the coset.

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]

Description

The vertices of the graph are the right cosets Hg = { hg : h in H } for g in G.

The edges of the graph are of the form (Hg,Hgx_i).

The Cayley graph of the group G with {x_i : i in I} is the Schreier coset graph for H = {1_G} (Gross & Tucker 1987, p. 73).

A spanning tree of a Schreier coset graph corresponds to a Schreier transversal, as in Schreier's subgroup lemma (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\rightarrow G$ and if X is a generating set for G then its inverse image under p is the Schreier graph of (G,X).

Applications

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, (Conder 2003).

Every vertex-transitive graph is a coset graph.

References

Schreier, Otto (December 1927). "Die Untergruppen der freien Gruppen". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 5 (1): 161–183. doi:10.1007/BF02952517.
Todd, J.A; Coxeter, H.S.M. (October 1936). "A practical method for enumerating cosets of a finite abstract group". Proceedings of the Edinburgh Mathematical Society. 5 (1): 26–34. doi:10.1017/S0013091500008221. Retrieved 2018-03-05.

Magnus, W.; Karrass, A.; Solitar, D. (1976), Combinatorial Group Theory, Dover
Conder, Marston (2003), "Group actions on graphs, maps and surfaces with maximum symmetry", Groups St. Andrews 2001 in Oxford. Vol. I, London Math. Soc. Lecture Note Ser., 304, Cambridge University Press, pp. 63–91, MR 2051519
Gross, Jonathan L.; Tucker, Thomas W. (1987), Topological graph theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York: John Wiley & Sons, ISBN 978-0-471-04926-5, MR 0898434
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, Republished as TAC Reprint, 2005

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Schreier, Otto (December 1927). "Die Untergruppen der freien Gruppen". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 5 (1): 161–183. doi:10.1007/BF02952517.

[2] Todd, J.A; Coxeter, H.S.M. (October 1936). "A practical method for enumerating cosets of a finite abstract group". Proceedings of the Edinburgh Mathematical Society. 5 (1): 26–34. doi:10.1017/S0013091500008221. Retrieved 2018-03-05.