---
tag: X1PQ8J2R10
kind: definition
name: Schreier coset graph
msc: ["20F65", "05C25"]
defines: HV2QBDHTDD
uses: [G5S1M9, 0X1JXT47GA, 0NE1DK7H4T, 0KFYGSHHF5]
sources:
  - url: https://en.wikipedia.org/wiki/Schreier_coset_graph
---

## Definition

Let $G$ be a [[group|G5S1M9]], let $H$ be a [[subgroup|0X1JXT47GA]] of $G$, and let $S$ be a subset of $G$.
The *Schreier coset graph* of $(G, H, S)$ is the [[directed graph|0KFYGSHHF5]] with labelled edges such that:

1. its vertices are the [[right cosets|0NE1DK7H4T]] $Hg$ of $H$ in $G$;
2. for each vertex $Hg$ and each $s \in S$, there is one edge with label $s$ from $Hg$ to $Hgs$.

## Remarks

The rule is well defined: if $Hg = Hg'$, then $g' = hg$ for some $h \in H$, so $Hg's = Hhgs = Hgs$.
The number of vertices is the index of $H$ in $G$, and every vertex has exactly one outgoing edge with each label.
If $S$ generates $G$, the graph is connected.
For $H = \set{1}$ it is the [[Cayley graph|0GYQK9NDJF]] of $G$ with respect to $S$.

Example: let $G = \Z$, $H = 3\Z$ and $S = \set{1}$.
The vertices are $3\Z$, $1 + 3\Z$ and $2 + 3\Z$, and the edges go $3\Z \to 1 + 3\Z \to 2 + 3\Z \to 3\Z$, since adding $1$ moves each coset to the next one.
The graph is a directed cycle of length $3$.

Non-example: the rule with left cosets $gH$ and edges $gH \to gsH$ is not well defined in general.
In $S_3$, with composition from right to left, take $H = \set{1, (1\,2)}$ and $s = (2\,3)$.
Then $1 \cdot H = (1\,2) H$, but $(2\,3) H = \set{(2\,3), (1\,3\,2)}$ and $(1\,2)(2\,3) H = (1\,2\,3) H = \set{(1\,2\,3), (1\,3)}$ are different cosets.