A Robinson-Schensted algorithm for a class of partial orders (Q1369676)

In going from existence proofs to algorithmic existence proofs it is often necessary if not desirable to sacrifice conceptual clarity and argumentative elegance for constructive robustness and intuitive solidity in a way which appears to sacrifice simplicity for complication and completeness for wider applicability. Often such apparent sacrifice leads to later gains both in theory and better understanding of the true potential of even the simpler original proof to areas of application more apparent through the constructive approach implicit in the development of good algorithms. It is this exception expressed by the authors as the reason for a very substantial effort expended in this paper to show that with the additional hypothesis that a finite poset \(P\) does not contain an induced subposet \(B=\{x> a< b< c>y\}\) (i.e., a poset \(N\) with diagonal \(C_3=\{a< b<c\}\) important elsewhere as well) they are able to reproduce Gasharov's result that if \(P\) does not contain an induced subposet \(C_3+1\), than Stanley's chromatic symmetric function \(X_G\) of the incomparability graph \(G\) of \(P\) has nonnegative coefficients when expanded in terms of the Schur functions. From the construction of the algorithm it becomes clear that it is not an unreasonable hope to expect that more is possible, including the softening of conditions on what subposets must be excluded, through a clever (yet unknown) enlargement of the classes upon which the critical bijection is algorithmically constructed.