Timeline for Difference in chromatic number between Schreier coset graphs and Cayley graphs
Current License: CC BY-SA 4.0
25 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 16, 2022 at 8:48 | comment | added | ARG | said question has been posted there | |
| Mar 14, 2022 at 7:10 | comment | added | ARG | @vidyarthi I'm not sure what is the group-theoretic condition on $G$ and $H$ so that the corresponding graph is vertex-transitive. Perhaps there is something about the nomraliser and/or the automorphisms of $G$ (or automorphisms of $G$ fixing $H$). That might be an interesting question. I would post it, but please do so first if you wish. | |
| Mar 13, 2022 at 16:10 | comment | added | vidyarthi | @ARG thanks! When is it the case that a Schreier coset graph is not even vertex transitive? | |
| Mar 13, 2022 at 15:59 | vote | accept | vidyarthi | ||
| Mar 13, 2022 at 8:00 | comment | added | ARG | @vidyarthi when the subgroup H is normal, this only means that the Schreier graph will just be the same as a Cayley graph. In particular it will be vertex-transitive. This is not the case for generic Schreier graphs (in fact almost any regular graph is a Schreier graph, see here for some infos. | |
| Mar 12, 2022 at 19:35 | comment | added | ARG | By the way I just notices that the discussion above uses the notation $G/H$ while the cosets in the Schreier graph are $Hx$. I think you should write the cosets as $xH$ (if you are using $G/H$) or write the quotient as $H \backslash G$ (if you are using the cosets $Hx$) | |
| Mar 12, 2022 at 19:32 | comment | added | ARG | @vidyarthi I posted an answer, as requested. The Schreier graph of $G/H$ will definitively have loops when the subgroup $H$ contains elements of the generating set. More generally, there is a loop if there is a $s \in S$ so that $Hxs = Hx$. This is $\iff H xsx^{-1} = H \iff xsx^{-1} \in H$. In other words, a Schreier graph will have loops iff the subgroup $H$ intersect the conjugacy classes of the generating set. | |
| Mar 12, 2022 at 19:25 | answer | added | ARG | timeline score: 1 | |
| Mar 11, 2022 at 14:34 | answer | added | kabenyuk | timeline score: 2 | |
| Mar 11, 2022 at 14:24 | comment | added | vidyarthi | @ARG so if the subgroup is normal, there will be no loops right, but what happened in the previous example of kabenyuk? | |
| Mar 11, 2022 at 10:39 | comment | added | vidyarthi | @ARG you could write down your comments as an answer which might be good. | |
| Mar 11, 2022 at 10:33 | comment | added | ARG | @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$). | |
| Mar 11, 2022 at 10:22 | comment | added | vidyarthi | @ARG Thanks, so your example shows that the schreier coset graph may have chromatic number beyond that of the cayley graph on the same generating set | |
| Mar 11, 2022 at 10:21 | history | edited | vidyarthi | CC BY-SA 4.0 |
deleted 6 characters in body
|
| Mar 11, 2022 at 9:59 | comment | added | ARG | @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$. | |
| Mar 11, 2022 at 9:33 | comment | added | vidyarthi | @kabenyuk what if we neglect the loop edges? Can we prove that the coset graphs are subgraphs of Cayley graphs on the same generating set now. And, by the way, your $S$ missed the element $(132)$ to make it symmetric | |
| Mar 11, 2022 at 9:32 | history | edited | vidyarthi | CC BY-SA 4.0 |
added 27 characters in body
|
| Mar 11, 2022 at 9:25 | comment | added | vidyarthi | @kabenyuk Thanks, I got your point. | |
| Mar 11, 2022 at 7:14 | comment | added | kabenyuk | @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)\}$. | |
| Mar 11, 2022 at 6:32 | comment | added | vidyarthi | @kabenyuk I hope the set of vertices of Coset graphs are actually a subset of the set of vertices of Cayley graph. If we exclude the identity element in the generating set of the graph, we actually can avoid loops, right? | |
| Mar 11, 2022 at 4:42 | comment | added | kabenyuk | 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. | |
| Mar 9, 2022 at 11:34 | comment | added | vidyarthi | @GordonRoyle so then, it seems the gap is sort of directly proportional to the cardinality of the subgroup | |
| Mar 9, 2022 at 11:21 | comment | added | Gordon Royle | 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. | |
| Mar 9, 2022 at 8:36 | history | edited | YCor | CC BY-SA 4.0 |
removed capitals, added tag
|
| Mar 9, 2022 at 5:55 | history | asked | vidyarthi | CC BY-SA 4.0 |