Let $Y$ be a Young tableau of shape $\lambda:=(\lambda_1,\ldots,\lambda_n)$, where $\lambda_1\geq\lambda_2\geq\ldots\geq\lambda_n$ and $N:=|\lambda|:=\sum_i\lambda_i$. I'll be using the English notation for Young tableaux. Then the hook of a box $(i,j)$ is every box straight below and straight to the right of $(i,j)$, including $(i,j)$ itself.

The Greene-Nijenhuis algorithm generates a uniformly random Young tableau of the above shape as follows:

1) Set $k=N$.

2) Uniformly pick a random unoccupied cell in $Y$.

3) Do a hook walk algorithm till you reach the edge, and place $k$ there.

4) $k\leftarrow k-1$. Repeat steps 2-4 until $k=0$.

I'm wondering if you can generate a uniformly random Young tableau by running the Greene-Nijenhuis algorithm backwards? So set $k=1$, uniformly pick an unnocupied cell, and now perform a hook walk algorithm, except now the hooks are oriented left and up: the hook of $(i,j)$ is now $(i,j)$ and every box straight above and straight to the left. Obviously 1 ends up in the top-left corner. Now do the same for $k=2$, etc. Naively, I don't think the product of the reverse hooks necessarily equals the product of the usual hooks, so perhaps some sort of modification is required?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.