A Robinson-Schensted algorithm for a class of partial orders
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.
- The Robinson-Schensted and Schützenberger algorithms, an elementary approach
- scientific article; zbMATH DE number 1322084
- Some optimal algorithms for decomposed partially ordered sets
- scientific article; zbMATH DE number 3974734
- scientific article; zbMATH DE number 3559589
- Algorithms over partially ordered sets
- scientific article; zbMATH DE number 17892
- A New Class of Partial Orders
- On algorithms to find \(p\)-ordering
- A relation for domino Robinson-Schensted algorithms
- A symmetric function generalization of the chromatic polynomial of a graph
- Duality of graded graphs
- Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
- scientific article; zbMATH DE number 3884163 (Why is no real title available?)
- Incomparability graphs of \((3+1)\)-free posets are \(s\)-positive
- Longest Increasing and Decreasing Subsequences
- On immanants of Jacobi-Trudi matrices and permutations with restricted position
- Recognizing bull-free perfect graphs
- Schensted algorithms for dual graded graphs
- Descents, quasi-symmetric functions, Robinson-Schensted for posets, and the chromatic symmetric function
- Chromatic posets
- Robinson-Schensted correspondence for unit interval orders
- A \(q\)-weighted version of the Robinson-Schensted algorithm
- Lollipop and lariat symmetric functions
- scientific article; zbMATH DE number 4120214 (Why is no real title available?)
- Counting domino tilings of rectangles via resultants
- RSK for 3-free posets
- Noncommutative Schur functions for posets
This page was built for publication: A Robinson-Schensted algorithm for a class of partial orders
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1369676)
