Return to Answer

Definition. Let $G$ be a free group with basis $S$ and let $H$ be a subgroup of $G$. The Schreier coset graph $\operatorname{Schreier}_{G, S}(H)$ of $G$ in $H$ with respect to $S$ is the directed and labelled graph whose vertices are the right cosets $Hg$ for $g \in G$ and there is an edge labelled by $s$ from $Hg$ to $Hgs$ for every $g \in G$ and $s \in S$ (distinct labels yield distinct edges).

Proof of the Claim. We can assume, without loss of generality, that $G$ is a free group with basis $S$. By [1, Proposition III.3.1], the subgroup $H$ identifies with the fundamental group of $\Gamma = \operatorname{Schreier}_{G, S}(H)$ with base point $H = H \cdot 1$. Let $T$ be an affluent spanning tree of $\Gamma$ rooted at $H$ given by Lemma 2. For $v$ a vertex of $\Gamma$, we denote by $p_v$ the unique directed path joining $H$ to $v$ within $T$. Then $H$ is generated by the homotopy classes of the loops $\gamma(Hg, s) = p_{Hg} \cdot s \cdot p_{Hgs}^{-1}$ with $g \in G$ [1, Proof of Proposition III.2.1]. Now let $q_{Hg}$ denote a directed path from $Hgs$ to $Hg$ in $\Gamma$ of length at most $d - 1$. Then $H$ is also generated by the loops $\gamma(Hg, s) \cdot p_{Hgs} \cdot q_{Hg} = p_{Hg} \cdot s \cdot q_{Hg}$ and $p_{Hgs} \cdot q_{Hg}$ for $g \in G, s \in S$. As the latter generators are words over $S$ of length at most $2d - 1$, the proof is complete.

Definition. Let $G$ be a free group with basis $S$ and let $H$ be a subgroup of $G$. The Schreier coset graph $\operatorname{Schreier}_{G, S}(H)$ of $G$ in $H$ with respect to $S$ is the directed and labelled multi-graph whose vertices are the right cosets $Hg$ for $g \in G$ and there is an edge labelled by $s$ from $Hg$ to $Hgs$ for every $g \in G$ and $s \in S$ (distinct labels yield distinct edges).

Proof of the Claim. We can assume, without loss of generality, that $G$ is a free group with basis $S$. By [1, Proposition III.3.1], the subgroup $H$ identifies with the fundamental group of $\Gamma = \operatorname{Schreier}_{G, S}(H)$ with base point $H = H \cdot 1$. Let $T$ be an affluent spanning tree of $\Gamma$ rooted at $H$ given by Lemma 2. For $v$ a vertex of $\Gamma$, we denote by $p_v$ the unique directed path joining $H$ to $v$ within $T$. Then $H$ is generated by the homotopy classes of the loops $\gamma(Hg, s) = p_{Hg} \cdot s \cdot p_{Hgs}^{-1}$ with $g \in G$ [1, Proof of Proposition III.2.1]. Now let $q_{s, Hg}$ denote a directed path from $Hgs$ to $Hg$ in $\Gamma$ of length at most $d - 1$. Then $H$ is also generated by the loops $\gamma(Hg, s) \cdot p_{Hgs} \cdot q_{s,Hg} = p_{Hg} \cdot s \cdot q_{s,Hg}$ and $p_{Hgs} \cdot q_{s, Hg}$ for $g \in G, s \in S$. As the latter generators are words over $S$ of length at most $2d - 1$, the proof is complete.

Definition. Let $G$ be a free group with basis $S$ and let $H$ be a subgroup of $G$. The Schreier coset graph $\operatorname{Schreier}_{G, S}(H)$ of $G$ in $H$ with respect to $S$ is the directed and labelled graph whose vertices are the right cosets $Hg$ for $g \in G$ and whose edges are the pairs $(Hg, Hgs)$ with $g \in G$ and $s \in S$. We say that $s$ is a label of the edge $(Hg, Hgs)$.

The above definition almost coincides with the covering of a bouquet of circles labelled by the elements of $S$ considered in the proof of [2, Lemma 3.4]. If we consider, instead of a graph, the multigraph for which distinct labels yields a distinct edges, then the definitions coincide.

Proof of the Claim. We can assume, without loss of generality, that $G$ is a free group with basis $S$. By [1, Proposition III.3.1], the subgroup $H$ identifies with the fundamental group of $\Gamma = \operatorname{Schreier}_{G, S}(H)$ with base point $H = H \cdot 1$. Let $T$ be an affluent spanning tree of $\Gamma$ rooted at $H$ given by Lemma 2. For $v$ a vertex of $\Gamma$, we denote by $p_v$ the unique directed path joining $H$ to $v$ within $T$. Then $H$ is generated by the homotopy classes of the loops $\gamma(Hg, s) = p_{Hg} \cdot s \cdot p_{Hgs}^{-1}$ with $g \in G$ [1, Proof of Proposition III.2.1]. Now let $q_{Hg}$ denote a directed path from $Hgs$ to $Hg$ in $\Gamma$ of length at most $d$. Then $H$ is also generated by the loops $\gamma(Hg, s) \cdot p_{Hgs} \cdot q_{Hg} = p_{Hg} \cdot s \cdot q_{Hg}$ and $p_{Hgs} \cdot q_{Hg}$ for $g \in G, s \in S$. As the latter generators are words over $S$ of length at most $2d - 1$, the proof is complete.

Definition. Let $G$ be a free group with basis $S$ and let $H$ be a subgroup of $G$. The Schreier coset graph $\operatorname{Schreier}_{G, S}(H)$ of $G$ in $H$ with respect to $S$ is the directed and labelled graph whose vertices are the right cosets $Hg$ for $g \in G$ and there is an edge labelled by $s$ from $Hg$ to $Hgs$ for every $g \in G$ and $s \in S$ (distinct labels yield distinct edges).

The above definition agrees with the covering of a bouquet of circles labelled by the elements of $S$ which is considered in the proof of [2, Lemma 3.4].

Proof of the Claim. We can assume, without loss of generality, that $G$ is a free group with basis $S$. By [1, Proposition III.3.1], the subgroup $H$ identifies with the fundamental group of $\Gamma = \operatorname{Schreier}_{G, S}(H)$ with base point $H = H \cdot 1$. Let $T$ be an affluent spanning tree of $\Gamma$ rooted at $H$ given by Lemma 2. For $v$ a vertex of $\Gamma$, we denote by $p_v$ the unique directed path joining $H$ to $v$ within $T$. Then $H$ is generated by the homotopy classes of the loops $\gamma(Hg, s) = p_{Hg} \cdot s \cdot p_{Hgs}^{-1}$ with $g \in G$ [1, Proof of Proposition III.2.1]. Now let $q_{Hg}$ denote a directed path from $Hgs$ to $Hg$ in $\Gamma$ of length at most $d - 1$. Then $H$ is also generated by the loops $\gamma(Hg, s) \cdot p_{Hgs} \cdot q_{Hg} = p_{Hg} \cdot s \cdot q_{Hg}$ and $p_{Hgs} \cdot q_{Hg}$ for $g \in G, s \in S$. As the latter generators are words over $S$ of length at most $2d - 1$, the proof is complete.

Definition. Let $G$ be a free group with basis $S$ and let $H$ be a subgroup of $G$. The Schreier coset graph $\operatorname{Schreier}_{G, S}(H)$ of $G$ in $H$ with respect to $S$ is the directed and labelled graph whose vertices are the right cosets $Hg$ for $g \in G$ and whose edges are the pairs $(Hg, Hgs)$ with $g \in G$ and $s \in S$. We say that $s$ is the label of the edge $(Hg, Hgs)$.

The above definition coincides with the covering of a bouquet of circles labelled by the elements of $S$ considered in the proof of [2, Lemma 3.4].

Definition. Let $G$ be a free group with basis $S$ and let $H$ be a subgroup of $G$. The Schreier coset graph $\operatorname{Schreier}_{G, S}(H)$ of $G$ in $H$ with respect to $S$ is the directed and labelled graph whose vertices are the right cosets $Hg$ for $g \in G$ and whose edges are the pairs $(Hg, Hgs)$ with $g \in G$ and $s \in S$. We say that $s$ is a label of the edge $(Hg, Hgs)$.

The above definition almost coincides with the covering of a bouquet of circles labelled by the elements of $S$ considered in the proof of [2, Lemma 3.4]. If we consider, instead of a graph, the multigraph for which distinct labels yields a distinct edges, then the definitions coincide.