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:

- Given three consecutive letters $xyz$ with $x>y$ and $x\le z$, replace $xyz$ with $xzy$, or vice versa (replace $xzy$ with $xyz$).
- 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:

**121**43

**211**43

21**143**

21**413**

2**141**3

2**411**3

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?

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 https://arxiv.org/abs/0909.5324 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!

Maria

Pingback: My Homepage

Pingback: expense reporting software

Pingback: ตู้ล่าม

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

Pingback: http://www.2qiuqiu99.club/

Pingback: travel expense management

Pingback: https://www.gradewatches.com

Pingback: replica rolex

Pingback: buy dumps good balance

Pingback: 여우코믹스

Pingback: 마루마루

Pingback: security services company

Pingback: cvv shop high balance

Pingback: Check This Out

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

Pingback: stockX

Pingback: aecasino

Pingback: Kimber Handguns For Sale Online

Pingback: Tile Contractor

Pingback: gay flag cornhole

Pingback: malay tiger clenox

Pingback: Kimber guns for sale online

Pingback: Rescue Tow Paramount CA

Pingback: Forest Oaks plumbing contractor

Pingback: cheap dumps with pin

Pingback: Beställ OxyNorm i Sverige

Pingback: cvv fullz

Pingback: Köp OxyContin I sverige

Pingback: buy crabs wholesale

Pingback: hop over to this website

Pingback: Casino

Pingback: thick sex dolls

Pingback: โกง

Pingback: Sex Cams

Pingback: Gėlės Lentvaryje

Pingback: Best Cordless Lawn Mower Guide

Pingback: relx

Pingback: Outdoor Spielzeug Onlineshop

Pingback: little nightmares 2

Pingback: 541-556-8260

Pingback: USA online gun broker

Pingback: sex assignment at birth definition

Pingback: health insurance

Pingback: Best Bathroom Remodel in Atlanta/Click Here

Pingback: 메이저토토

Pingback: Novelty Toys for Kids

Pingback: price of metformin in canada

Pingback: cheap propecia

Pingback: ed treatments

Pingback: canadian king pharmacy

Pingback: canadian pharmacy drugs online