2005/07/02 by Alexander Burstein, Burstein, Alexander, Isaiah Lankham +1
Engineering · Mathematics · #05A05 #05A18 (Primary) 05E10 (Secondary) #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Random Matrices and Applications #graph theory and CDMA systems #math.CO #msc:05A05 #msc:05A18 #msc:05E10
paper · pdf · doi:10.48550/arxiv.math/0507031
14 pages, LaTeX, uses pstricks; v2: major revision after section 3; to be published in Adv. Appl. Math
openalex publication_date 2005/07/02 · arxiv created 2005/09/02 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (called pile configurations) 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. Unlike Geometric RSK, though, the lattice paths coming from Patience Sorting are allowed to intersect. We thus also give a characterization for the intersections of these lattice paths in terms of the pile configurations associated with a given permutation under the Extended Patience Sorting Algorithm.