# Three coloring the elements of symmetric group

Is it possible to $$3$$-color the elements of the symmetric group $$S_n\ n\ge3$$ such that all color classes have the same number of elements ($$\frac{n!}{3}$$); and, when elements in any color class are acted by the set of transpositions $$\{(12), (13), \ldots, (1n)\}$$ we get no element in the same class; or, to be precise, when we act to the right by a transposition on any element to a color class, we get neighbors in both of the other color classes; and in addition, we can get a perfect matching from any two color classes.

Precisely, it is like $$3$$- coloring the bipartite cayley graph formed by the generating set $$\{(12), (13), \ldots, (1n)\}$$ on the group $$S_n$$, such that all color classes have same cardinality and any two color classes have a regular nontrivial(degree $$\ge$$ $$1$$) bipartite subgraph of order $$2\frac{n!}{3}$$.

It is easy to see this true for $$n=3$$. The color classes being given by $$[e, (13)(12)(13)=(23)];[(12), (13)(12)]; [(13), (12)(13)]$$. However as $$n$$ rises, I don't see a way to get this done. Specifically, I think we have to produce $$\frac{n!}{6}$$ $$6$$-cycles in the Cayley graph mentioned. But, how can this be effectively done? Can induction work here? Any hints? Thanks beforehand.

• Interesting question. There can't be any local obstacles (meaning small non-3-colorable subgraphs) because the Cayley graph as a whole is bipartite (using the cosets of the alternating group as the colors). I wonder if a randomized strategy could work. Commented Mar 9, 2021 at 14:51
• I'm not sure what your idea about $6$-cycles is, but the cosets (left or right? I'll let you figure it out) of the subgroup $\langle (12),\ (13) \rangle$ are disjoint $6$-cycles. Commented Mar 9, 2021 at 14:54
• This problem looks interesting but the exposition could be clearer. The text at the end of the 1st paragraph: "when elements in any color class are acted by the set of transpositions.....we get no element in the same class" is quite confusing and ambiguous. What does this mean precisely? That if say, $\pi \in S_n$ is in the 1st color class, then $\tau\pi$ [or $\pi\tau$] is in either the 2nd or 3rd color class for each such transposition $\tau$? Or that there for each $j\in \{2,3\}$ exists such a transposition $\tau_j$ so that $\tau_j\pi$ [or $\pi\tau_j$] is in the $j$-th color class?
– Mike
Commented Mar 9, 2021 at 17:22
• @Mike Your second question is the one intended, that is when we act to the right by a transposition on any element to a color class, we get neighbors in both of the other classes Commented Mar 9, 2021 at 17:31
• Alright I saw your previous comment. But that is still a stronger condition than $\{\pi\} + \{\pi\tau$; $\tau$ a transposition of the form $\tau = (1,k)\}$ intersecting all color classes.
– Mike
Commented Mar 9, 2021 at 18:16

Yes, it is possible to $$3$$-color the elements of the Symmetric group in the way stated. The proof can be found in Theorem 1 of MDPI Symmetry Paper.
The proof uses a similar idea given in the comments of @DavidSpyer of taking cosets of $$S_{n-1}$$ with respect to $$S_n$$, and using induction, by knowing that the base case of $$S_3$$ is true.