Knuth equivalence on a necklace

Lately, I’ve been working on some open problems related to a Young tableau operation called catabolism, which involves some interesting tableaux combinatorics. While working the other day, I encountered a simple and beautiful fact that I never would have expected.

Suppose we have a word $w$ whose letters are from the alphabet $\{1,\ldots,n\}$ (allowing repeated letters). A Knuth move is one of the following:

  1. Given three consecutive letters $xyz$ with $x>y$ and $x\le z$, replace $xyz$ with $xzy$, or vice versa (replace $xzy$ with $xyz$).
  2. Given three consecutive letters $xyz$ with $z\ge y$ and $z\lt x$, replace $xyz$ with $yxz$, or vice versa (replace $yxz$ with $xyz$).

In other words, if you have three consecutive letters and either the first or the third lies between the other two in size, the end letter acts as a pivot about which the other two letters switch places. Visually:


In the case of a tie, think of the repeated letters as getting larger as you go to the right. For instance, in the word $211$, the rightmost $1$ is “larger” than the middle $1$, so $211$ can be replaced with $121$ by switching the left $1$ and the $2$.

If two words can be reached from each other by a sequence of Knuth moves, we say they are Knuth equivalent. For instance, $12143$ is equivalent to $24113$ via the sequence of moves:


In addition, not all words on the same letters are equivalent: the word $123456$, for instance, has no valid Knuth moves and so it is only equivalent to itself.

Since the moves are invertible, Knuth equivalence sorts all words into Knuth equivalence classes. In 1970, Donald Knuth realized that these equivalence classes are in one-to-one correspondence with semistandard Young tableaux, which has made them very useful in algebraic combinatorics.

Recently, I needed to understand what happens when you allow the Knuth moves to “wrap around at the edge”. In other words, think of the word as being on a necklace or counterclockwise-oriented circle, and allow the same Knuth moves as before. For instance, $123456$ is now equivalent to $623451$ since the $5$ is between the next two letters, $1$ and $6$.

Now, we get “cyclic” Knuth equivlance classes. How do these relate to the original Knuth equivalence classes? It turns out that there is only one cyclic Knuth equivalence class for any given collection of letters. That is, for any two arrangements of the same collection of letters around a necklace, there is a sequence of cyclic Knuth moves that takes one to the other.

It’s a nice fact – can you see why it’s true?

54 thoughts on “Knuth equivalence on a necklace

  1. Your comment on cyclic Knuth classes reminds me of something I thought about a while ago. Consider cyclic orderings of [n] with the move that we are allowed to do ki…j… –> ik….j… with i<j 132 and 231 —> 213, but not allowing 2 to be somewhere else in the cyclic word. I also don’t know if you are thinking of the moves as directed, or just thinking about equivalence classes.

    Anyway, let me know if it seems interesting!

    • Your blog ate the formatting of my reply. Let’s see if the usual WordPress syntax works better: Consider circular orderings of $[n]$, where we can change $ki\cdots j \cdots$ to $ik \cdots j \cdots$ for $i \lt j \lt k$. In other words, we can move $k$ past $i$ as long as $j$ occurs somewhere in the word. That is clearly more general than your cyclic Knuth, as you only allow $kij \to ikj$ and $jki \to jik$.

      It turns out that the set of cyclic orders of [n] becomes a graded poset of length $\binom{n}{3}$ under this operation, with unique minimal element $n(n-1) \cdots 21$ and unique maximal element $12\cdots (n-1)n$. See for a more general statement related to an arbitrary affine Coxeter group, and see 2010 USAMO Problem 2 for a fun restatement.

      Let me know if this seems inteeresting/useful to you!

      • Hi David,

        I think I fixed your formatting… not sure why it was giving you trouble before! That is super interesting, I wasn’t aware of these generalized “cyclic Knuth” moves, thanks for sharing!


  2. Pingback: My Homepage

  3. Pingback: expense reporting software

  4. Pingback: ตู้ล่าม

  5. Pingback: فيس تسجيل الدخول

  6. Pingback:

  7. Pingback: travel expense management

  8. Pingback:

  9. Pingback: replica rolex

  10. Pingback: buy dumps good balance

  11. Pingback: 여우코믹스

  12. Pingback: 마루마루

  13. Pingback: security services company

  14. Pingback: cvv shop high balance

  15. Pingback: Check This Out

  16. Pingback: شارژ حساب بت فوروارد

  17. Pingback: stockX

  18. Pingback: aecasino

  19. Pingback: Kimber Handguns For Sale Online

  20. Pingback: Tile Contractor

  21. Pingback: gay flag cornhole

  22. Pingback: malay tiger clenox

  23. Pingback: Kimber guns for sale online

  24. Pingback: Rescue Tow Paramount CA

  25. Pingback: Forest Oaks plumbing contractor

  26. Pingback: cheap dumps with pin

  27. Pingback: Beställ OxyNorm i Sverige

  28. Pingback: cvv fullz

  29. Pingback: Köp OxyContin I sverige

  30. Pingback: buy crabs wholesale

  31. Pingback: hop over to this website

  32. Pingback: Casino

  33. Pingback: thick sex dolls

  34. Pingback: โกง

  35. Pingback: Sex Cams

  36. Pingback: Gėlės Lentvaryje

  37. Pingback: Best Cordless Lawn Mower Guide

  38. Pingback: relx

  39. Pingback: Outdoor Spielzeug Onlineshop

  40. Pingback: little nightmares 2

  41. Pingback: 541-556-8260

  42. Pingback: USA online gun broker

  43. Pingback: sex assignment at birth definition

  44. Pingback: health insurance

  45. Pingback: Best Bathroom Remodel in Atlanta/Click Here

  46. Pingback: 메이저토토

  47. Pingback: Novelty Toys for Kids

  48. Pingback: price of metformin in canada

  49. Pingback: cheap propecia

  50. Pingback: ed treatments

  51. Pingback: canadian king pharmacy

  52. Pingback: canadian pharmacy drugs online

Leave a Reply

Your email address will not be published. Required fields are marked *