I'm interested in two 'natural bijections' that involve labeled forests and Young tableaux. Let me give the definition for labeled forests. By this, we mean a pair $\cal{F} = (F,f)$ where $F$ is an $n$-vertex forest, and $f$ is a labeling of its nodes from $1$ to $n$. We say that:

  • $\cal{F}$ is standard if $f$ is bijective,
  • $\cal{F}$ is sorted if the numbering is increasing along each root-to-leaf path,
  • $\cal{F}$ is subexcedant if for each node $u$, $f(u)$ is at most the number of nodes of the subtree rooted at $u$.

Let $T_n,O_n,U_n$ denote the sets arising from these three cases, for a fixed size $n$. It is not too difficult to show the existence of a bijection $Sort_n : T_n \rightarrow O_n \times U_n$, which implies a well-known 'hook length' formula due to Knuth. One unpleasant aspect of this bijection lies in its assymetry: we would like to get a pair of similar objects in order to get extra symmetry properties (e.g. what would happen if we switch the two objects and then apply the reverse bijection?)

Therefore, I'm asking naively if you think that the symmetry could be restored by considering more general structures. I'm not optimistic on this question though: there might be a positive but difficult answer that so far eludes me. A side remark: this bijection $Sort_n$ already enjoys some interesting symmetry properties in connection with the Schützenberger involution, but we would need something stronger to get an interesting algebraic object (possibly a Hopf algebra?)

  • $\begingroup$ One more thing: if there is an answer I expect it to be highly non-trivial (possibly involving complex objects such as crystal graphs) so the reader should be aware of the difficulties. Then again, algebra is precisely about the study of symmetries/asymetries, which is a very ancient question (probably dating back to the Sumerian/Assyrian civilizations if not earlier...) $\endgroup$
    – NisaiVloot
    Apr 13 '14 at 22:52

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.