1
$\begingroup$

Can the Schreier coset graphs can be seen as a subgraph of Cayley graph on the same groups(neglecting the loop edges) and, hence, have their chromatic numbers bounded by the chromatic numbers of the Cayley graphs on those groups with the same generating set?

Also, how much does the cardinality of the subgroup determine the gap between the chromatic number of schreier coset graphs and the Cayley graphs on those same groups with the same generating set. Like, if the subgroup with respect to which the cosets are taken is large, then is the gap between the chromatic numbers also proportionally large? Thanks beforehand.

Improve this question
$\endgroup$
18
  • 1
    $\begingroup$ If the subgroup is large, say the entire group, then the coset graph will have one vertex and chromatic number 1, which probably is not useful to you. $\endgroup$
    – Gordon Royle
    Mar 9, 2022 at 11:21
  • 1
    $\begingroup$ Could you clarify two things. 1) In what sense is the Schreier coset graph a subgraph of Cayley graph? These graphs have different sets of vertices. 2) The coset graph can have loops. How can we define the chromatic number in this case. $\endgroup$
    – kabenyuk
    Mar 11, 2022 at 4:42
  • 1
    $\begingroup$ @vidyarthi This is incorrect. If $G$ is a group, $H$ is a subgroup of $G$, $S$ is a symmetric generating set of $G$ that does not contain the identity element, then the set of vertices of the Cayley graph $\operatorname{Cey}(G,S)$ is $G$, and the set of vertices of cosets graph $\operatorname{Cey}(G/H,S)$ is the set cosets $$ G/H=\{Hx\mid x\in G\}. $$ Well, the graph $\operatorname{Cey}(G/H,S)$ may have loops in spite of the fact that $S$ contains no the identity element. Take $G=S_3$, $H=\operatorname{gr}(123)$, $S=\{(123),(12)\}$. $\endgroup$
    – kabenyuk
    Mar 11, 2022 at 7:14
  • 1
    $\begingroup$ @vidyarthi the Schreier graph is not a subgraph of the Cayley graph. Take $G= C_{3n}$ (cyclic groups on $3n$ elements). Let $S$ be a generator of this cyclic group, then $Cay(G,S)$ is a $3n$-cycle (in particular it contains no 3-cycles for $n>1$. There is a [normal] subgroup $H$ in $G$ which is isomorphic to $C_n$. Then $G/H \cong C_3$. So $Sch(G/H,S)$ is $Cay(G/H,S)$ which is a 3-cycle. You could also do this by replacing $3$ with an arbitrary integer $k>2$. $\endgroup$
    – ARG
    Mar 11, 2022 at 9:59
  • 1
    $\begingroup$ @vidyarthi yes, if one applies it to $C_{kn}$ with $k$ odd and $n$ even, then $C_{kn}/C_{n} \cong C_k$ so that the chromatic of the $C_{kn}$ is 2 while that of the $C_k$ is 3. There are probably many other examples. Also the ratio $kn/n = k$ so that it could be as large as you want (or stay by 3, while $nk \to \infty$). $\endgroup$
    – ARG
    Mar 11, 2022 at 10:33

2 Answers 2

Reset to default
2
$\begingroup$

Here's a good example.

Let $G=S_n$, $S=\{(i,j)\mid 1\leq i<j\leq n \}$. Then $\operatorname{Cay}(G,S)$ is a bipartite graph and so its chromatic number is $2$. Let $H=\{g\in S_n\mid g(n)=n\}$. It is easy to check that $\operatorname{Sch}(G/H,S)$ is a complete graph (if we forget about loops) and hence its chromatic number is $n$.

Improve this answer
$\endgroup$
1
$\begingroup$

As requested by the OP, here is a simple example of the fact that the chromatic number may go up, and that the Schreier graph is not a subgraph of the Cayley graph.

Let $k>2$ be odd and $n>1$ be even. Let $G = C_{kn}$ (the cyclic groups on $kn$ elements, it is $\cong \mathbb{Z}/kn\mathbb{Z}$). Let $S = \lbrace -1, 1\rbrace$ be a [symmetric] generating set of this cyclic group. Then $\mathrm{Cay}(G,S)$ is a cycle of length $kn$ (in particular it contains no odd cycles, since $n>1$). There is a [normal] subgroup $H$ in $G$ which is isomorphic to $C_n$ (this is the subgroup generated by $k \in \mathbb{Z}$). It is fairly standard exercise to check that $G/H \cong C_k$. By normality $\mathrm{Sch}(G/H,S)$ is isomorphic $\mathrm{Cay}(G/H,S)$ which itself is a cycle of length $k$.

The Schreier Graph $\mathrm{Sch}(G/H,S)$, being an odd cycle, has chromatic number 3 and is not isomorphic to any subgraph of $\mathrm{Cay}(G,S)$ (which is an even cycle with chromatic number 2).

Furthermore, by fixing $k$ an letting $n \to \infty$, the ratio $\frac{\# \text{Vertices of } \mathrm{Cay}(G,S)}{\#\text{Vertices of } \mathrm{Sch}(G/H,S)}$ tends to infinity. By fixing $n$ and letting $k \to \infty$, the ratio remains constant, while the cardinalities tend to infinity.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.