Towards a Robinson-Schensted algorithm for (3+1)-free posets

Tim Chow (Tellabs Research Center)

The Robinson-Schensted algorithm converts a linear order into a pair of standard Young tableaux. It is conjectured that there is a generalization of this algorithm to (3+1)-free posets, i.e., posets that do not contain the disjoint union of a three-chain and a one-chain as an induced subposet. (Magid announced a solution but his proof appears to be incorrect.) Sundquist, Wagner and West developed an algorithm that works for some (3+1)-free posets---the "beast-free" posets---but fails for others. We show that the sought-for algorithm, like the usual R-S algorithm, ought to respect descents. This gives us some guidance in deciding how to amend the Sundquist-Wagner-West algorithm.

I will do my best to give adequate background and motivation. This conjecture has not been worked on much, and the talk should give enough background to enable the enthusiastic researcher to start working on it almost immediately.