Timeline for Chromatic number of the insert-and-shift graph on $S_n$
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 27 at 9:50 | comment | added | Will Sawin | 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$. | |
| Mar 27 at 9:47 | comment | added | Will Sawin | @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. | |
| Mar 27 at 9:44 | comment | added | Will Sawin | @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. | |
| Mar 27 at 1:57 | comment | added | dbal | 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. | |
| Mar 26 at 9:07 | vote | accept | Dominic van der Zypen | ||
| Mar 25 at 19:12 | history | answered | Will Sawin | CC BY-SA 4.0 |