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:

Yet another definition of the Schur functions

I continue to be amazed at the multitude of different contexts in which the Schur functions naturally appear.

In a previous post, I defined the Schur symmetric functions combinatorially, via the formula \[s_\lambda=\sum_{|\mu|=|\lambda|}K_{\lambda\mu} m_\mu\] where $K_{\lambda\mu}$ is the number of semistandard Young tableaux of shape $\lambda$ and content $\mu$ and $m_\mu$ is the monomial symmetric function of shape $\lambda$. I also defined them as the ratio \[s_\lambda=\frac{a_{\lambda+\delta}}{a_\lambda}\] where $a_\lambda$ is the elementary antisymmetric function.

And, in another post, I pointed out that the Frobenius map sends the irreducible characters of the symmetric group $S_n$ to the Schur functions $s_\lambda$. This can be taken as a definition of the Schur functions:

Early Easter Egg

It’s not springtime just yet, but I found myself nerd sniped this week by an easter egg in my favorite LaTeX editor, TeXStudio.

I had to reinstall it recently, and my customized advanced configurations were set back to the defaults. So I opened the Options -> Configure TeXStudio menu, and tried to click on the “Show advanced options” checkbox. This is what popped up:

That’s right, a “Riddle” window popped up with the following problem:

Combinatorial species

Just last month, I took my Ph.D. qualifying exam at Berkeley. It was a grueling three-hour oral exam, but from it came a gemstone that simply must be shared!

The very first question I was asked was from my advisor, Mark Haiman: ``Enumerate [count] the labeled plane trees on $n$ vertices.’’

More precisely, let $n$ be a positive integer, and define a labeled plane tree to be a tree with vertices labeled $1,2,\ldots,n$, along with a cyclic ordering of the branches attached to each vertex. (The name ``plane tree’’ refers to the fact that the orderings of the branches determine an embedding of the tree into Euclidean space up to homotopy equivalence.) For instance, say we had the following trees drawn in the plane:

They are isomorphic as graphs but not as plane trees, because the branches around the vertex $1$ have different clockwise cyclic orderings.

So how do we count these trees?

What happens in characteristic p?

There is a reason that the real numbers and complex numbers are so popular. They have the nice property that $1+1+1+\cdots+1$ is not equal to zero, no matter how many times you add $1$ to itself.

Strange things happen in fields of prime characteristic $p\neq 0$, such as the field $\mathbb{Z}/p\mathbb{Z}$ of integers taken modulo $p$. In these fields, $1+1+\cdots+1=0$ for any number of $1$’s which is a multiple of $p$. We get non-intuitive but strangely beautiful identities like $(x+y)^p=x^p+y^p$, since the coefficient $\binom{p}{i}$ is divisible by $p$ for $1\le i\le p-1$.

And, we get a representation of the symmetric group which is indecomposable but not irreducible. Allow me to explain.