11
$\begingroup$

Given a partition $\mu=(\mu_1,\mu_2...,\mu_d)$, define $\bar\mu=(\mu_1-\mu_d,\mu_1-\mu_{d-1},...,\mu_1-\mu_2,0)$, the complementary shape in the $d\times \mu_1$ rectangle. Then the number of skew standard Young tableaux with at most $d$ rows and skew part $\mu$ are (I believe) in bijection with those with skew part $\bar\mu$ (where they each have $n$ labels).

I have a proof for the case $\mu=(i+j,i,0)$, $\bar\mu=(i+j,j,0)$ but I heard the general case may have appeared in the literature. I have been unable to find the reference. It might work with jeu de taquin and I'd love to see the details.

Is anyone familiar with this paper?

EDIT: Equivalently, given a fixed lattice path from $(-\infty,0)$ to $(+\infty,d)$, we want to fill in $n$ labels of a standard Young tableau below the path and above the line $y=0$. The claim is that there's a bijection between these objects and the objects we get if we flip the lattice path over (180 degrees).

For example, if $n=6$, $d=3$, $\mu=(3,1,0)$, and $\bar\mu=(3,2,0)$, these two are paired up by my bijection:

SYT with skew symmetry

$\endgroup$
  • $\begingroup$ There is an easy bijection if you restrict the numbers to be between $1$ and $\mu_1$ - the column $i$ in $\bar{\mu}$ contains the complement of the elements in column $d-i$ in $\mu$, or did I misinterpret the question? $\endgroup$ – Per Alexandersson Apr 9 '16 at 11:16
  • $\begingroup$ The skew parts are complements in a rectangle, but there is no restriction on the shape of the rest of the tableaux (other they have at most $d$ rows). $\endgroup$ – Jordan Apr 9 '16 at 23:11
  • $\begingroup$ There must be some mistake in your formulation, $\mu_d - \mu_1$ is negative... but now I see what you mean... $\endgroup$ – Per Alexandersson Apr 10 '16 at 3:23
  • $\begingroup$ Typos fixed! Should say $\mu_1-\mu_d$ and the line is $y=0$. Sorry, thanks for catching them! $\endgroup$ – Jordan Apr 10 '16 at 18:31
  • $\begingroup$ I added an example to clarify. $\endgroup$ – Jordan Apr 10 '16 at 19:10
4
$\begingroup$

Here is another solution, based on the paper "Robinson-schensted algorithms for skew tableaux" by Sagan and Stanley (Darij Grinberg was the one who suggested that this algorithm might work, I'm just filling in the details in a pretty straightforward fashion).

Fix integers $k$ and $n$, and denote $[n]=\{1,2,\dots,n\}$. We say that $$\pi=\begin{pmatrix}i_1 & \dots & i_m\\ j_1 & \dots & j_m\end{pmatrix}$$ is a partial two-line array if the integers $i_1,\dots,i_m$ are distinct elements of $[n]$, the same is true for $j_1,\dots,j_m$, and $i_1<\dots<i_m$.

Also, fix some partition $\mu$ with at most $k$ rows, and assume all parts of $\mu$ are much bigger than $n$ (the correct way is to think of $\mu$ as a lattice path inside an infinite horizontal strip of height $k$).

We say that an SYT $P$ with at most $k$ rows has right boundary $\mu$ if it has shape $\mu/\nu$ for some $\nu$. A similar definition goes for SYT with left boundary $\mu$, and the original conjecture becomes $$\#\mathrm{SYT}_k^n(\mu/*)=\#\mathrm{SYT}_k^n(*/\mu)$$ where the LHS denotes the number of SYTs with $n$ boxes with at most $k$ rows and right boundary $\mu$ while the RHS denotes the number of SYTs with $n$ boxes with at most $k$ rows and left boundary $\mu$.

One more definition: a partial SYT with entry set $S$ is just a Young tableau (i.e. the entries increase along rows and columns) with distinct entries such that the set of its entries is $S$. For example, an SYT with $n$ boxes is a partial SYT with entry set $[n]$.

We are going to describe a bijection $(\pi,T,U)\leftrightarrow (\tau,P,Q)$ where

  • $\pi=\begin{pmatrix}i_1 & \dots & i_s\\ j_1 & \dots & j_s\end{pmatrix},\quad \tau=\begin{pmatrix}i'_1 & \dots & i'_t\\ j'_1 & \dots & j'_t\end{pmatrix}$ are partial two-line arrays;

  • $T,U$ are partial SYT's of the same shape $\mu/\lambda$ with entry sets $[n]\setminus \{j_1,\dots,j_s\}$ and $[n]\setminus \{i_1,\dots,i_s\}$;

  • $P,Q$ are partial SYT's of the same shape $\nu/\mu$ with entry sets $[n]\setminus \{j'_1,\dots,j'_t\}$ and $[n]\setminus \{i'_1,\dots,i'_t\}$.

This bijection is going to work in exactly the same way as in Sagan-Stanley's paper, so we're going to redefine their internal and external insertions.

Let $R$ be a partial SYT with entry set $S$, and let $q$ be an integer not belonging to $S$. Then define the external insertion of $q$ into $R$ to be the new partial SYT denoted $R\leftarrow q$ and defined by the following algorithm: we first row-insert $q$ into the first row of $R$, then it bumps out some element $q_1$ which we then insert into the second row of $R$, and so on until either $q_i$ is just appended on the right to the row $i+1$ of $R$ (i.e. nothing is bumped) or we reach $k$-th row of $R$ in which case we get one extra entry $q_k$ of $R$ which we memorize.

Similarly, let $(i,j)$ be an inner (that is, left) corner of $R$. Define the internal insertion of $(i,j)$ into $R$ to be the new partial SYT denoted $(i,j)\to R$: remove the entry $q$ from $(i,j)$ and insert it into the next row $i+1$ of $R$. It bumps out some entry $q_{i+1}$ which we then insert into row $i+2$ of $R$ and so on until either nothing is bumped or we reach row $k$ in which case we memorize the extra entry $q_k$ that we get.

Now, here is the RSK algorithm that is going to solve the problem:

  • initially, set $P=T$, $Q=\mu/\mu$ an empty tableau and $\tau:=\begin{pmatrix} \\ \end{pmatrix}$ an empty partial two-line array;
  • for each $q=1,2,\dots,n$, do the following:
  • if $q$ belongs to the entry set of $U$, then $q$ lies in an inner corner $(i,j)$ of $U$, so remove it from $Q$ and replace $P$ by $(i,j)\to P$;
  • otherwise, if $q$ is equal to $i_m$ for some $m$, replace $P$ by $P\leftarrow j_m$;
  • if we memorize an extra entry $p$ of $P$ as a result of our insertion, append $\begin{pmatrix}q\\ p \end{pmatrix}$ to $\tau$;
  • otherwise, append $q$ to $Q$ in the box that was added to $P$ at the final step of the insertion.

It is easy to see that this is indeed a bijection. Another property that can be proved analogously to Theorem 3.3 in Sagan-Stanley's paper is the following symmetry of the algorithm:

if $(\pi,T,U)\leftrightarrow (\tau,P,Q)$ then $(\pi^{-1},U,T)\leftrightarrow (\tau^{-1},Q,P)$.

Here $\pi^{-1}$ is obtained from $\pi$ by first switching $i_m$ with $j_m$ for all $m$ and then sorting the columns so that the first row would be increasing. As a corollary of that, we see that the triples $(\pi,T,T)$ where $\pi=\pi^{-1}$ is an involution correspond to the triples $(\tau,P,P)$ where $\tau$ is an involution (Sagan-Stanley, Corollary 3.4). Therefore the following formula is true: $$\sum_{s=0}^n \mathrm{Inv}(n,s) \#\mathrm{SYT}_k^{n-s}(\mu/*)=\sum_{t=0}^n \mathrm{Inv}(n,t) \#\mathrm{SYT}_k^{n-t}(*/\mu),$$ where $\mathrm{Inv}(n,s)$ is the number of involutions $\pi$ with $s$ columns and with entries from $[n]$. This recurrence immediately implies the result by induction on $n$.

One can consider the semistandard version (the Knuth version) of this RSK algorithm which shows the following identity: $$\sum_{\lambda\subset \mu} s_{\mu/\lambda}=\sum_{\mu\subset \nu} s_{\nu/\mu},$$ where the sums are infinite and taken over all partitions $\lambda,\nu$ with at most $k$ parts (that are respectively to the left and right of $\mu$ in this infinite horizontal strip of height $k$). Of course, this is a stronger statement since the number of SYT's is recovered by taking the coefficient of $x_1\dots x_n$ on both parts. The stronger identity was conjectured by Alex Postnikov.

$\endgroup$
  • $\begingroup$ Can that last identity be seen as a consequence of the $S_3$-symmetry of the Littlewood-Richard coefficients $c_{\nu,\mu}^{\lambda}$? $\endgroup$ – Sam Hopkins Apr 15 '16 at 20:13
  • 1
    $\begingroup$ Good question, I tried that but didn't succeed. If you take inner product of both sides with $s_\kappa$ and then use the fact that skewing by $\mu$ is adjoint to multiplying by $s_\mu$, you get that the sum of L-R coefficients $C^\lambda_{\mu,\kappa}$ over all $\lambda$ equals the sum of L-R coefficients $C^\lambda_{\mu^\vee,\kappa}$ over all $\lambda$ ($\mu^\vee$ denotes rotation). But even though the sums are the same, for certain values of $\mu$ and $\kappa$ you get different lists of numbers. $\endgroup$ – Pavel Galashin Apr 15 '16 at 23:34
  • $\begingroup$ Huh, very interesting. $\endgroup$ – Sam Hopkins Apr 15 '16 at 23:39
1
$\begingroup$

At first, we reformulate your problem. Denote $m_i=\mu_i-i$, then $m_1>m_2>\dots>m_d$. Consider $d$ bugs $B_1,\dots,B_d$ initially sitting in corresponding points $m_i$ on $\mathbb{Z}$. When we fill a box in $i$-th row, let bug $B_i$ move from its place $x$ to $x+1$. For example, in your first figure the sequence of movements is $(B_3,B_2,B_3,B_1,B_2,B_2)$. Young tableaux condition on bugs language is that no two bugs are allowed to meet. Your claim is that the number of admissible bugs movements consisting given number of $n$ steps does not change if we ask bugs move to the left instead of moving to the right.

Fix $n$. Denote, say, by $W(25,28,34)$ the number of bugs movements with $n$ steps for which $B_5$ meets $B_2$, $B_8$ meets $B_2$, $B_4$ meets $B_3$. We may write inclusion-exclusion formula for the number of not-admissible bug movements. Say, for three bugs the number of not-admissible bug movements is $W(12)+W(23)-W(12,23)$. Of course two fist summands do not change if we change direction of bugs (bijection for the first summand is just changing behaviour of $B_1$ and $B_2$). As for the third summand, the trick is that it equals $W(13)$, that also does not change after bugs reversing. For the proof of equality $W(12,23)=W(13)$ we use induction on $n$. If after first step no two bugs meet, use induction proposition. If, say, $B_2$ meets $B_1$, than the number of continuations of the movement for which $B_3$ meets $B_2$ is of course the same as the number of continuations of the movement for which $B_3$ meets $B_1$. In other words, relation $W(12,23)=W(13)$ is obvious if $B_1$ and $B_2$ have just already met. Analogous formula, but more involved, works for $W(12,23,\dots,(k-1)k)$ (everything reduces to this case after applying initial inclusion-exclusion to $W(12),W(13),\dots$).

For example, $W(12,23,34)=W(14)-W(14,23)+W(13,24)$. For proving this we again induct on $n$ and wee that it suffices to prove in the case when $B_i,B_{i+1}$ already met. In this case it reduces either to already considered case of three bugs (if $i=1$ or $i=3$) or is obvious by the very same argument, if $i=2$.

Now I formulate the formula for $W(12,23,\dots,(k-1)k)$ with general $k$. Consider all sets of segments $[a_1,b_1], [a_2,b_2],\dots,[a_m,b_m]$ with mutually distinct $2m\leqslant k$ endpoints, which cover $[1,k]$. Denote by $T$ the number of pairs of linking segments in this collection (linking is inequality $a_i<a_j<b_i<b_j$). The coefficient of $W(a_1b_1,a_2b_2,\dots,a_mb_m)$ equals $(-1)^{T+\sum a_i+\sum b_i+k-1}$. The proof is induction on $n$. Base $n=0$ consists of checking that sum of coefficients equals 1. This may be proved by additional induction on $k$. If we do not use $k-1$ as an endpoint for no $i$, this is induction proposition. If we do, then interchanging endpoints $k-1,k$ is a sign-changing involution, so such coefficients cancel. Next, we need to prove this identity in the case when some two bugs, say, $B_s$ and $B_{s+1}$ have just already met. If there is a segment $[a_i,b_i]$ such that $a_i<s<s+1<b_i$, we may add or remove the segment $[s,s+1]$, or replace role of $s,s+1$. This is sign-changing involution. If there is no such segment, we are reduced to induction proposition for $[1,s]$ and $[s+1,k]$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.