A Robinson-Schensted algorithm for a class of partial orders
type: Item
instance of: scholarly article
title: A Robinson-Schensted algorithm for a class of partial orders
zbMATH Open document ID: 0882.05113
author: Thomas S. Sundquist
author: David G. Wagner
author: Julian West
published in: Journal of Combinatorial Theory. Series A
publication date: 1998-03-02T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05E05
Mathematics Subject Classification ID: 05E10
Mathematics Subject Classification ID: 05A99
zbMATH DE Number: 1076893
zbMATH Keywords: Robinson-Schensted algorithm
zbMATH Keywords: finite poset
zbMATH Keywords: chromatic symmetric function
zbMATH Keywords: incomparability graph
zbMATH Keywords: Schur functions
reviewed by: J. Neggers
MaRDI profile type: Publication
full work available at URL: jcta.1997.2769
OpenAlex ID: W2079700103
cites work: Duality of graded graphs
cites work: Schensted algorithms for dual graded graphs
cites work: Incomparability graphs of \((3+1)\)-free posets are \(s\)-positive
cites work: Recognizing bull-free perfect graphs
cites work: Longest Increasing and Decreasing Subsequences
cites work: A symmetric function generalization of the chromatic polynomial of a graph
cites work: Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
cites work: On immanants of Jacobi-Trudi matrices and permutations with restricted position
cites work: Q3218128
DOI: 10.1006/JCTA.1997.2769
Recommended article: The Robinson-Schensted and Schützenberger algorithms, an elementary approach
Recommended article: Q4253215
Recommended article: Some optimal algorithms for decomposed partially ordered sets
Recommended article: Q3740581
Recommended article: Q4132542
Recommended article: Algorithms over partially ordered sets
Recommended article: Q3975242
Recommended article: A New Class of Partial Orders
Recommended article: On algorithms to find \(p\)-ordering
Recommended article: A relation for domino Robinson-Schensted algorithms
description: scientific article; zbMATH DE number 1076893