7
$\begingroup$

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.

Improve this question
$\endgroup$
18
  • 1
    $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Commented Mar 9, 2021 at 14:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Commented Mar 9, 2021 at 14:54
  • 2
    $\begingroup$ 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? $\endgroup$
    – Mike
    Commented Mar 9, 2021 at 17:22
  • 1
    $\begingroup$ @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 $\endgroup$
    – vidyarthi
    Commented Mar 9, 2021 at 17:31
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mike
    Commented Mar 9, 2021 at 18:16

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ Are you one of the authors of this paper? $\endgroup$
    – Sam Hopkins
    Commented Mar 1 at 12:29
  • $\begingroup$ @SamHopkins you're close. I leave the answer open for anonymity. By the way, do you find the proof satisfactory, or can it be improved? $\endgroup$
    – vidyarthi
    Commented Mar 1 at 13:57
  • 1
    $\begingroup$ Well, if you know the authors, you might inform them that if they used ideas based on comments to this MO question, probably they should acknowledge that in their paper. $\endgroup$
    – Sam Hopkins
    Commented Mar 2 at 18:30
  • $\begingroup$ @SamHopkins As the paper is already published, do you think it is necessary to add reference to the comment as an addendum in coming issues? $\endgroup$
    – vidyarthi
    Commented Mar 3 at 2:35
  • 1
    $\begingroup$ It's not a big deal but just something to bear in mind going forward. $\endgroup$
    – Sam Hopkins
    Commented Mar 3 at 2:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .