-2
$\begingroup$

For any $n\in\mathbb{N}$ let $[n] = \{1,\ldots,n\}$ and let $S_n$ be the set of all bijections (permutations) $\pi:[n]\to [n]$. For any set $X$ let $[X]^2 = \big\{\{x,y\}: x\neq y\in X\big\}$. We let $\pi,\psi\in S_n$ be connected by an edge if "they are one transposition away from each other", or more formally, set $$E_n = \big\{\{\pi,\psi\}\in [S_n]^2:\exists a<b\in[n]:\big(\psi = (a\;\;b)\circ\pi\big) \text{ or } \big(\psi = \pi\circ(a\;\; b)\big)\big\}.$$

Given any positive integer $n\in\mathbb{N}$, what is $\chi(S_n, E_n)$?

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ Maybe I misunderstand the question, but isn't $\chi(S_n,E_n)$ always $2$? Just color the permutations by their sign. $\endgroup$
    – Moritz Firsching
    Commented Aug 28, 2017 at 7:23
  • $\begingroup$ @MoritzFirsching Thanks for your comment - I believe you are right! Can you put this down as a short answer? $\endgroup$
    – Dominic van der Zypen
    Commented Aug 28, 2017 at 8:33

1 Answer 1

Reset to default
6
$\begingroup$

For $n\geq 2$, we have $$\chi(S_n, E_n) = 2.$$ It is at most $2$, since we can color permutations by their signs. It is obviously at least $2$.

Improve this answer
$\endgroup$

You must log in to answer this question.

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