1
$\begingroup$

Let $S_n$ be the collection of bijections $\varphi:\{1,\ldots,n\}\to \{1,\ldots,n\}$. In an earlier question, the insert-and-shift graph structure was introduced on $S_n$ and the resulting graph is called $\newcommand{\Gn}{\mathbf{G}_n}\Gn$.

It turns out that $\Gn$ is not bipartite except for small values of $n$. So the question is whether $\chi(\Gn)$ is bounded as $n\to\infty$. If not: what is $$\lim\inf_{n\to\infty}\frac{\chi(\Gn)}{n}?$$

Improve this question
$\endgroup$
4
  • $\begingroup$ For those who struggle with the wordy description: Is it the Cayley graph of $S_n$ for the generating set {all cycles of the form $i \mapsto i+1 \mapsto i+2 \mapsto \cdots \mapsto j$ with $i \leq j$}? $\endgroup$
    – darij grinberg
    Commented Mar 25 at 19:12
  • 1
    $\begingroup$ If so, I think you can get a proper $n$-coloring by letting the color of each permutation $\sigma$ to be the remainder of the number of inversions of $\sigma$ upon division by $n$. The reason for this is that the number of inversions increases by at most $n-1$ when you compose $\sigma$ with any cycle of the above form. But I see no reason why this should be optimal. $\endgroup$
    – darij grinberg
    Commented Mar 25 at 19:18
  • $\begingroup$ @darijgrinberg Yes, this is the Cayley graph, but the inversion idea doesn't work. The cycle $(123)$, which is of the form you describe, satisfies $(123)(23)=(12)$ but both $(12)$ and $(23)$ have one inversion. The problem is that the number of inversions can both increase and decrease, and the increases and decreases can cancel. $\endgroup$
    – Will Sawin
    Commented Mar 25 at 20:20
  • $\begingroup$ Ah, right! @WillSawin $\endgroup$
    – darij grinberg
    Commented Mar 25 at 20:29

1 Answer 1

Reset to default
6
$\begingroup$

$\mathbf G_n$ contains the complete graph $K_n$. Consider the set of all permutations where the elements $1,\dots, n-1$ are in the usual order in the sense that $\sigma(1) < \dots < \sigma(n-1)$, but $n$ may be out of place. Each permutation in this set is connected to each other one by a single edge, since we may remove $n$ from wherever it is and shift it to any other location. The set has size $n$, giving the complete graph $K_n$.

This gives a lower bound of $n$ for the chromatic number, and a lower bound of $1$ for the lim inf.

The only upper bound I see is $(n-1)^2+1$ (coming from the degree of each vertex).

Improve this answer
$\endgroup$
4
  • $\begingroup$ I think one could probably use this tau.ac.il/~nogaa/PDFS/logf4.pdf to show that it is O(n^2 / log n). The only edges in the neighborhood correspond to products of consecutive cycles which result in consecutive cycles. Seems like there shouldn't be too many of these. $\endgroup$
    – dbal
    Commented Mar 27 at 1:57
  • 1
    $\begingroup$ @dbal Indeed. The number of pairs of consecutive cycles where the element moved is the same one is at most $n(n-1)(n-1)$. A permutation is a consecutive cycle if and only if there is an element where deleting it gives the identity, and deleting an element from a consecutive cycle gives a consecutive cycle or the identity. If the product of two consecutive cycles is the consecutive cycle, then deleting an element makes those two consecutive cycles inverses. $\endgroup$
    – Will Sawin
    Commented Mar 27 at 9:44
  • 1
    $\begingroup$ @dbal If the two cycles don't move the same element (in the case of transpositions, which give two choices of which element is moved, if this happens for neither choice) then the element deleted can't be either of them, as this would make one the identity and one not. Then the consecutive cycles after deleting must be inverses that move different elements so must be inverse transpositions swapping two adjacent elements. Since the originals can't be transpositions swapping those two (as then they would move the same ones) they must be 3-cycles involving the deleted element. $\endgroup$
    – Will Sawin
    Commented Mar 27 at 9:47
  • 1
    $\begingroup$ The number of possibilities for this is 2(n-2) since there are 2(n-2) choices of the first 3-cycle and the second 3-cycle has to be supported on the same points but can't be the inverse which would move the same element back. So the total number of edges in the neighborhood is at most $n(n-1)^2+ 2(n-2)$ which indeed with the result you cite gives $\approx n^2/\log n$. $\endgroup$
    – Will Sawin
    Commented Mar 27 at 9:50

You must log in to answer this question.

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