https://en.formulasearchengine.com/api.php?action=feedcontributions&feedformat=atom&user=68.165.65.118formulasearchengine - User contributions [en]2026-05-02T02:46:32ZUser contributionsMediaWiki 1.43.0-wmf.28https://en.formulasearchengine.com/index.php?title=Connection_(algebraic_framework)&diff=24761Connection (algebraic framework)2013-12-09T07:55:31Z<p>68.165.65.118: </p>
<hr />
<div>In the area of [[mathematics]] called [[combinatorial group theory]], the '''Schreier coset graph''' is a [[graph (mathematics)|graph]] associated to a [[group (mathematics)|group]] ''G'', a [[Generating set of a group|generating set]] { ''x''<sub>''i''</sub> : ''i'' in ''I'' }, and a [[subgroup]] ''H'' ≤ ''G''. <br />
<br />
<br />
==Description==<br />
The [[vertex (graph theory)|vertices of the graph]] are the right [[coset]]s ''Hg'' = { ''hg'' : ''h'' in ''H'' } for ''g'' in ''G''. <br />
<br />
The [[edge (graph theory)|edges of the graph]] are of the form (''Hg'',''Hgx<sub>i</sub>''). <br />
<br />
The [[Cayley graph]] of the group ''G'' with { ''x''<sub>''i''</sub> : ''i'' in ''I'' } is the Schreier coset graph for ''H'' = { 1<sub>G</sub> },{{harv|Gross|Tucker|1987|p=73}}. <br />
<br />
A [[spanning tree]] of a Schreier coset graph corresponds to a Schreier transversal, as in [[Schreier's subgroup lemma]], {{harv|Conder|2003}}.<br />
<br />
The book "Categories and Groupoids" listed below relates this to the theory of covering morphisms of [[groupoid]]s. A subgroup ''H'' of a group ''G'' determines a covering morphism of groupoids <math> p: K \rightarrow G </math> and if ''X'' is a generating set for ''G'' then its inverse image under ''p'' is the Schreier graph of ''(G,X)''.<br />
<br />
==Name==<br />
The graph is named after [[Otto Schreier]]. <br />
==Applications==<br />
The graph is useful to understand [[coset enumeration]] and the [[Todd–Coxeter algorithm]]. <br />
<br />
Coset graphs can be used to form large [[permutation representation]]s of groups and were used by [[Graham Higman]] to show that the [[alternating group]]s of large enough degree are [[Hurwitz group]]s, {{harv|Conder|2003}}.<br />
<br />
Every [[vertex-transitive graph]] is a coset graph.<br />
<br />
== References ==<br />
* {{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. | id={{MathSciNet | id = 2051519}} | year=2003 | volume=304 | chapter=Group actions on graphs, maps and surfaces with maximum symmetry | pages=63–91}}<br />
* {{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 | id={{MathSciNet | id = 898434}} | year=1987}}<br />
* [http://arxiv.org/abs/0911.2915 Schreier graphs of the Basilica group Authors: Daniele D'Angeli, Alfredo Donno, Michel Matter, Tatiana Nagnibeda]<br />
[[Category:Combinatorial group theory]]<br />
<br />
* Philip J. Higgins, Categoriues 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] <br />
<br />
<br />
<br />
{{algebra-stub}}</div>68.165.65.118