A Geometric Form for the Extended Patience Sorting Algorithm Export

@misc{citeulike:247124, abstract = {Patience Sorting is a combinatorial algorithm that can be viewed as an iterated, non-recursive form of the Schensted Insertion Algorithm. In recent work the authors extended Patience Sorting to a full bijection between the symmetric group and certain pairs of combinatorial objects that are most naturally defined in terms of generalized permutation pattern and barred pattern avoidance. This Extended Patience Sorting Algorithm is very similar to the Robinson-Schensted-Knuth (or RSK) Correspondence, which is itself built from repeated application of the Schensted Insertion Algorithm. In this work we introduce a geometric form for the Extended Patience Sorting Algorithm that is in some sense a natural dual algorithm to G. Viennot's celebrated Geometric RSK Algorithm. We then discuss the relationship between this geometric algorithm and generalized permutation patterns.}, archivePrefix = {arXiv}, author = {Burstein, Alexander and Lankham, Isaiah}, citeulike-article-id = {247124}, citeulike-linkout-0 = {http://arxiv.org/abs/math.CO/0507031}, citeulike-linkout-1 = {http://arxiv.org/pdf/math.CO/0507031}, day = {2}, eprint = {math.CO/0507031}, keywords = {algorithm, extended, form, geometric, patience, sorting}, month = {Jul}, posted-at = {2008-11-10 22:24:50}, priority = {4}, title = {A Geometric Form for the Extended Patience Sorting Algorithm}, url = {http://arxiv.org/abs/math.CO/0507031}, year = {2005} }

TY - ELEC ID - citeulike:247124 L3 - citeulike-article-id:247124 N2 - Patience Sorting is a combinatorial algorithm that can be viewed as an iterated, non-recursive form of the Schensted Insertion Algorithm. In recent work the authors extended Patience Sorting to a full bijection between the symmetric group and certain pairs of combinatorial objects that are most naturally defined in terms of generalized permutation pattern and barred pattern avoidance. This Extended Patience Sorting Algorithm is very similar to the Robinson-Schensted-Knuth (or RSK) Correspondence, which is itself built from repeated application of the Schensted Insertion Algorithm. In this work we introduce a geometric form for the Extended Patience Sorting Algorithm that is in some sense a natural dual algorithm to G. Viennot's celebrated Geometric RSK Algorithm. We then discuss the relationship between this geometric algorithm and generalized permutation patterns. TI - A Geometric Form for the Extended Patience Sorting Algorithm KW - algorithm KW - extended KW - form KW - geometric KW - patience KW - sorting AU - Burstein, Alexander AU - Lankham, Isaiah PY - 2005/Jul/02/ UR - http://arxiv.org/abs/math.CO/0507031 ER -