3.1 Coset graph and quotient graph

Coset graph

Definition

Coset graph $\Gamma =Cos(X,X_{\omega },X_{\omega }g{X}_{\omega })$ is a graph with vertex set $\Omega =[X:X_{\omega }]$ and $(X_{\omega }x,X_{\omega }y)\in E$ iff $y^{-1}x\in X_{\omega }g{X}_{\omega }$.

Proposition

$X$ is transitive on the vertex set $\Omega$ and transitive on the arc set $\{(x{X}_{\omega },y{X}_{\omega }):y^{-1}x\in X_{\omega }g{X}_{\omega }\}$.

\begin{proof} Consider the set of vertices which are adjacent to $X_{\omega }$, denoted as $L$. Note $(a{X}_{\omega },X_{\omega })$ is an arc if $a\in X_{\omega }g{X}_{\omega }$, so $L=\{h_{i}g{X}_{\omega }:h_i\in X_{\omega }\}$. Since $X_{\omega }$ acting on $L$ transitively, $G$ acting on arc set transitively. \end{proof}

Remark. Coset graph is a particular case of Sabidussi graph.

Proposition

$|\Omega |=|X|/|X_{\omega }|$ and the valency of $\Gamma$ is $|X_{\omega }|/|X_{\omega }\cap X_{\omega }^g|$.

\begin{proof} For any fixed vertex $x{X}_{\omega }$, the valency of $x{X}_{\omega }$ is

$$|\{y:y\in X,y^{-1}x\in X_{\omega }g{X}_{\omega }\}|/|X_{\omega }|.$$

By $|x^{-1}{X}_{\omega }g{X}_{\omega }|=|g^{-1}{X}_{\omega }g{X}_{\omega }|=|X_{\omega }^g{X}_{\omega }|=|X_{\omega }{|}^2/|X_{\omega }\cap X_{\omega }^g|$, we know the valency of $x{X}_{\omega }$ is $|X_{\omega }|/|X_{\omega }\cap X_{\omega }^g|$ and so for $\Gamma$. \end{proof}

Proposition

$\Gamma$ is connected iff $⟨X_{\omega },g⟩=X$.

\begin{proof} Assume $\Gamma$ is connected. Then for any $x{X}_{\omega }$ and $X_{\omega }$, there exists $u_1,\cdots ,u_n$ such that $u_1^{-1}x,u_2^{-1}{u}_1,\cdots ,u_n^{-1}{u}_{n-1},u_n\in X_{\omega }g{X}_{\omega }$ and $(x{X}_{\omega },u_1{X}_{\omega }),(u_1{X}_{\omega },u_2{X}_{\omega }),\cdots ,(u_n{X}_{\omega },X_{\omega })$ are in the arc set. Then $x\in \prod X_{\omega }g{X}_{\omega }$ for all $x\in X$. It deduces that $X\subset \prod X_{\omega }g{X}_{\omega }$ and so $X=⟨X_{\omega },g⟩$.

Conversely, if $X$ can be generated by $X_{\omega }$ and $g$, any $x\in X$ can be written as $x={\omega }_{1}g{\omega }_{2}g\cdots {\omega }_{n}g$. Then $(x{X}_{\omega },({\omega }_{1}g{\omega }_{2}g\cdots {\omega }_n)X_{\omega })$, $(({\omega }_{1}g{\omega }_{2}g\cdots {\omega }_n)X_{\omega },({\omega }_{1}g{\omega }_{2}g\cdots {\omega }_{n-1})X_{\omega })$, $\cdots$, $(({\omega }_{1}g{\omega }_2)X_{\omega },{\omega }_1{X}_{\omega })$ are arcs. Note that ${\omega }_1{X}_{\omega }=X_{\omega }$, $x{X}_{\omega }$ and $X_{\omega }$ are connected and so for $\Gamma$. \end{proof}

Proposition

$\Gamma$ is undirected iff $g^2\in X_{\omega }$.

\begin{proof} Assume that $g^2\in X_{\omega }$. For any $y^{-1}x\in X_{\omega }g{X}_{\omega }$, $x^{-1}y\in X_{\omega }{g}^{-1}{X}_{\omega }=X_{\omega }{g}^2{g}^{-1}{X}_{\omega }=X_{\omega }g{X}_{\omega }$. Thus $\Gamma$ is undirected.

Conversely, assume that $\Gamma$ is undirected. Then for any $x\in X_{\omega }{g}^{-1}{X}_{\omega }$, we have $x^{-1}=e^{-1}{x}^{-1}\in X_{\omega }g{X}_{\omega }$ and $xe=x\in X_{\omega }g{X}_{\omega }$. Thus $X_{\omega }{g}^{-1}{X}_{\omega }\subset X_{\omega }g{X}_{\omega }$. Symmetrically, $X_{\omega }g{X}_{\omega }\subset X_{\omega }{g}^{-1}{X}_{\omega }$ and so $X_{\omega }g{X}_{\omega }=X_{\omega }{g}^{-1}{X}_{\omega }$. Note that $X_{\omega }{g}^2{g}^{-1}{X}_{\omega }=X_{\omega }{g}^{-1}{X}_{\omega }$ yields $X_{\omega }{g}^2=g^{-1}{X}_{\omega }g$. Thus $1\in g^{-1}{X}_{\omega }g=X_{\omega }{g}^2$ and $g^{-2}\in X_{\omega }$. Therefore, $g^2\in X_{\omega }$. \end{proof}

Quotient graph

quotient graph

Let $\Gamma =(V,E)$. Let $\mathcal{B}$ be a partition of $V$, say $V={\bigsqcup }_{i=1}^m{B}_i$. Define a graph $\Sigma$ with vertex set $\mathcal{B}$ such that $B_i\sim B_j$ iff there exists $v_i\in B_i$ and $v_j\in B_j$ such that $v_i\sim v_j$ in $\Gamma$.

Lemma

Suppose $\Gamma =(V,E)$. Let $\mathcal{B}$ be a block system for $G$ on $V$. i.e. $\mathcal{B}$ is a $G$-invarient partition. Then:

• if $\Gamma$ is $G$-vertex transitive, then ${\Gamma }_{\mathcal{B}}$ is also $G$-vertex transitive.
• if $\Gamma$ is a connected $G$-arc transitive graph, then ${\Gamma }_{\mathcal{B}}$ is also $G$-arc transitive.

Remark. $G⩽\mathrm{Aut}\Gamma$ does not yield $G⩽\mathrm{Aut}{\Gamma }_{\mathcal{B}}$. For example, consider Example 2, $X=A_5\times Z_2\le \mathrm{Aut}\Gamma$, but $X/⩽S_6$ and so $X/⩽\mathrm{Aut}\Sigma$.

cover

If each vertex in $B_i$ is adjacent to exactly one vertex in $B_j$ whenever $B_i\sim B_j$ in ${\Gamma }_{\mathcal{B}}$, $\Gamma$ is called a cover of ${\Gamma }_{\mathcal{B}}$.

Remark. Consider cover instead of quotient graph is important. See here.