6
$\begingroup$

Let $n>1$ be an integer and let $[n] = \{1,\ldots,n\}$. Let $S_n$ denote the set of all permutations (bijections) $\pi:[n]\to[n]$. We say that $\psi\neq\pi\in S_n$ are a cycle away from each other if there is an integer $k\in[n]$ and $k$ distinct integers $n_1,\ldots n_k\in[n]$ such that $$\psi = \pi \circ (n_1 \; n_2\;\cdots\; n_k) \text{ or } \psi = (n_1 \; n_2\;\cdots\; n_k) \circ \pi.$$

Let $E = \big\{\{\pi,\psi\}: \pi \neq \psi \in S_n\text{, and} \psi,\pi \text{ are a cycle away from each other}\big\}$. This makes $(S_n,E)$ into a connected finite, simple, undirected graph.

What is the maximal size of a clique in $(S_n, E)$, what is $\chi(S_n, E)$, and are these numbers equal?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Why 'or'? The relation 'the ratio of two permutations is a cycle' is symmetric $\endgroup$
    – Fedor Petrov
    Commented Oct 2, 2017 at 7:39
  • 1
    $\begingroup$ @PeterHeinig: what do you mean with "the number of transpositions of a permutation"? $\endgroup$
    – Martin Rubey
    Commented Oct 2, 2017 at 14:18
  • $\begingroup$ @MartinRubey: thanks for pointing out. This was a superficial typo/misspeaking, I mean nothing else than the usual 'number of cycles in the up-to-order-unique decomposition into disjoint cycles'. Briefly, 'cycle' was erroneously 'rendered' as 'transposition'. I will repost the comments. $\endgroup$
    – Peter Heinig
    Commented Oct 2, 2017 at 14:53
  • $\begingroup$ The problem-statement in this OP is almost flawless, yet I would prefer to add to it a verbal 'recapitulation' of what is being asked, which is rather easy to state after all. The OP is asking: what is the (0) clique number, and (1) the chromatic number, of the graph on the symmetric group which has edges between those permutations whose number of cycles in the cycle-decomposition differs by exactly 1. (One can ask this for symmetric groups on any cardinal, it still makes sense, restricting to permutations with finitely-many cycles; the OP is restricted to finite symmetric groups though.) $\endgroup$
    – Peter Heinig
    Commented Oct 2, 2017 at 14:55
  • $\begingroup$ Also: the OP's graph is a Cayley graph on the symmetric group (note that the set of cyclic permutations is closed under inversion, hence an eligible Cayley-set. (And Fedor Petrov's and Aaron Meyerowitz' comments about the redundant 'or' are correct: permutations are compositions of cycles, so any two can only differ by the number of cycles in them, not by any sort of 'direction' in which they so differ.) Needless to say, useful to point out: the OP is not asking whether this Cayley graph is a perfect graph, rather only whether it's in the less well-behaved class of graphs with $\omega=\chi$. $\endgroup$
    – Peter Heinig
    Commented Oct 2, 2017 at 14:56

1 Answer 1

Reset to default
5
$\begingroup$

It turns out that for the $S_5$ graph the clique number is $7$ but the chromatic number is $30.$ Details at the end.

The number of cycles is $c_n=\sum_{k=2}^{n}\binom{n}{k}(k-1)!$ The first few terms $(n-1)!+\frac{n(n-2)!}{2}+\frac{n(n-1)(n-3)!}3$ for cycles of length $n,n-1,n-2$ are the largest. This is actually the degree of every vertex in your graph. The problem can also be reduced to one on this many vertices, but with variable degrees. That would still be an advantage.

You need only consider multiplication on one side: If $\pi$ is a permutation and $\sigma$ is a cycle Then $\sigma'=\pi \circ \sigma \circ \pi^{-1}$ is another cycle of the same type and $\sigma' \circ \pi = \pi \circ \sigma.$

If $C$ is a clique so is $\{\alpha\circ\pi \mid \pi \in C\}$ where $\alpha$ is an arbitrary fixed permutation. So we could assume that the identity element $i$ is a member. This in turn means that every element is a cycle.

Here is a clique of size $13$ for $S_5$

$$ (12345)\ (12354)\ (12534)\ (13245)\ (13254)\ (14235)\ (15243)$$ $$ (132)\ (142)\ (145)\ (253)\ (345) $$ $$i$$

The cycles creating edges are exactly the $44$ cycles of type $(abc)$ and $(abcde).$ However some are used $7$ times, some $3$ and some just once.

Note that we could ask the same questions for alternating groups. This particular example lives entirely in $A_5.$ Perhaps there is a generalization.

I find an example of size $6$ in $S_4.$ One is $$i\ (12)\ (13)\ (14)\ (234)\ (243)$$

Since we can restrict to the $c_n$ vertices from cycles, just look at the induced graph on these. Perhaps first look for maximal cliques among the $n$-cycles, then the $n-1$-cycles then the $n-2$-cycles. These three graphs are regular and have a high symmetry. Then see how they might be combined.

LATER The graph for $S_3$ is $K_6$ so the clique number and chromatic number are the same $6.$

I gave a clique of size $6$ in the $S_4$ graph. For that graph (regular of degree $21$) to have chromatic number $6$ would require $6$ independent sets of size $4$. This occurs. The independent set of $\pi$ is $\{\pi,\pi(12)(34),\pi(13)(24),\pi(14)(23)\}.$

I leave the chromatic number of the $S_5$ graph to others. Since this graph on $120$ vertices is regular of degree $84,$ It might be easier to look for cliques in the complement which has degree $35$ than independent sets in the graph.

It is curious that the clique sizes go $1,2,6,6,7$ for $n=1,2,3,4,5.$

UPDATE I let Maple look for the chromatic number of the $S_5$ graph ($120$ vertices and $5040$ edges) but stopped it after several days. However it found a maximum independent set in the blink of an eye. $$i\ \ (12)(34)\ \ (13)(24)\ \ (14)(23).$$ So at least $30$ colors are needed. Since these four elements constitute a subgroup, the left cosets of this group provide a $30$-coloring.

Improve this answer
$\endgroup$

You must log in to answer this question.

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