Connected components of Schreier Graph $Sch(G,S,X)$ are exactly the orbits of the action of G on X.

40 Views Asked by At


I have difficulty proving a question:
Let $G$ be a group. $G$ acts on a set $X$, and $G=$ $\langle S \rangle$.
I am trying to prove that the connected components of $Sch(G,S,X)$ are exactly the orbits of the action of $G$ on $X$.
Reminder: $Sch(G,S,X)$, also called Schreier Graph, is the directed graph where $V$ = $X$, and $E$ = {$(x,s.x)$ | $x \in X, s \in S $ }.
I tried to prove it but failed. Both sides are very clear to me, but when I tried, for example, to prove that if $y \in O(x)$ (the orbit of x), then both are connected - I wasn't sure how to continue from that:
Since $y \in O(x)$, there exists $g \in G$ s.t. $y=g.x$. We can write $g=s_1^{e_1}...s_n^{e_n}$ where for $ \forall i\in[n]$, $s_i \in S$ and $e_i \in$ {$1,-1$}, and then $g=s_1^{e_1}...s_n^{e_n}$.x . Eventually, we need to show that those edges exist in $Sch(G,S,X)$. If $e_i=1$, it is clear, but what if $e_i=-1$? It's not clear for me how to continute from here.
The other direction of the proof (if both are connected, then they are on the same orbit) is easier to prove.
Thank you very much in advance!

1

There are 1 best solutions below

1
On

There are many options, as @JossevanDobbendeBruyn stated above:
1) If the graph is not directed, it is clear (since the opposite edges exist).
2) $G$ is finite, and then we can take ${s_i}^{ord({s_i})−1}$ instead of $s_i^{−1}$.
3) $S$ is closed under taking inverses. In that case, there is no problem with $s_i^{−1}$, since there exists some $s \in S$ s.t. $s_i^{−1}=s$.
Thanks again to @JossevanDobbendeBruyn for the help!