1
$\begingroup$

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?

$\endgroup$

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.