Homework for Week 5

Part 1

  1. Carefully define and prove the bijection between plane trees with half-edges and non-crossing matchings.
  2. Carefully define and prove the bijection between non-crossing matchings and Young diagrams with two rows of size (n,n). (You may use results from previous homework sets if you want, though you don't have to.)

Part 2

  1. Draw the graph whose vertices are given by non-crossing matchings on the integers 1,2,3,4,5,6 and whose edges are given by pairs of NCMs related by a simple transposition (i,i+1). Draw the graph whose vertices are given by row-strict Young tableaux of size (3,3) and whose edges are given by pairs of Young tableaux related by a simple transposition (i,i+1). Compare these graphs. Compare them to the graphs you found in HW4.
  2. If you map plane trees in T3 to noncrossing partitions, which pairs of noncrossing partitions correspond to pairs of plane trees associated by local moves? Do you have any general conjectures for Tn?
  3. If you map noncrossing matchings on 1,2,3,4,5,6 to noncrossing partitions, which pairs of noncrossing partitions correspond to pairs of NCMs associated by simple reflections (i,i+1)? Do you have any general conjectures for NCMs on 1,2,...,2n?