4
$\begingroup$

I'm currently reading a review article called Dynamical Algebraic Combinatorics: Promotion, Rowmotion, and Resonance by Jessica Striker. In this article, Striker writes that there is a ''nice'' bijection between the set of noncrossing matchings of $2b$ points and $SYT(2 \times b)$, the set of standard Young tableaux of size $2 \times b$. Here are two examples of the bijection:

fig 7

Unfortunately, I cannot seem to understand how exactly this bijection works.

As can be seen in the figure, given any pair $(i, j)$ with $i<j$ in the noncrossing matching, we want to map this to this to a tableau with $i$ on the first row and $j$ on the second row. But it is neither clear to me why this map should be injective nor surjective.

$\endgroup$
  • 5
    $\begingroup$ They both correspond to Dyck paths (or Dyck words) of length 2b in an easy way. For noncrossing matchings write U when an arc starts at a number and D when an arc ends at a number- this gives a bijection to Dyck words. For SYT the U letters are in the first row and the D letters are in the second row. $\endgroup$ – Sam Hopkins May 29 '18 at 15:45
  • 1
    $\begingroup$ (There are Catalan number many of these objects.) $\endgroup$ – Sam Hopkins May 29 '18 at 15:45
  • $\begingroup$ I'll pm you on Facebook if you need to discuss the code in my answer below. Or we can meet in my office some day (KTH). $\endgroup$ – Per Alexandersson May 29 '18 at 18:22
  • $\begingroup$ Following up on @SamHopkins, here are the citations in Richard Stanley's Catalan Numbers (Cambridge, 2015). Two-row standard Young tableaux are interpretation 168 (p44) and non crossing matchings (drawn in a line) are number 61 (p28). $\endgroup$ – Brian Hopkins May 30 '18 at 12:36
1
$\begingroup$

If you can understand Mathematica, the following code does what you wish. It first convert the SSYT to a Dyck path (0 and 1), always starting with a 0, and then from there, convert to perfect matching.

SSYTToDyckWord[tab_List] := Module[{n = Length[tab[[1]]]},
   Table[Boole[! MemberQ[tab[[1]], k]], {k, 2 n}]
   ];
DyckWordToNoncrossingMatching[dw_List] := 
  Module[{n = Length@dw, dw2 = dw, pm = {}, rem, p},
   rem = Range[n];
   While[Length[dw2] > 0,
    p = Position[dw2, 0, 1][[-1, 1]];
    AppendTo[pm, {rem[[p]], rem[[p + 1]]}];
    rem = Delete[rem, {{p}, {p + 1}}];
    dw2 = Delete[dw2, {{p}, {p + 1}}];
    ];
   Sort@pm
   ];
DyckWordToNoncrossingMatching@
 SSYTToDyckWord[{{1, 2, 3, 4, 7}, {5, 6, 8, 9, 10}}]

This returns {{1, 10}, {2, 9}, {3, 6}, {4, 5}, {7, 8}}

$\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.