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.

Improve this question
$\endgroup$
4
  • 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
    Commented May 29, 2018 at 15:45
  • 1
    $\begingroup$ (There are Catalan number many of these objects.) $\endgroup$
    – Sam Hopkins
    Commented May 29, 2018 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
    Commented May 29, 2018 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
    Commented May 30, 2018 at 12:36

1 Answer 1

Reset to default
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}}

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .