Combinatorics of patience sorting piles

zbMATH Open1267.05005arXivmath/0506358MaRDI QIDQ2654575FDOQ2654575

Authors: Alexander Burstein, Isaiah Lankham 

Publication date: 19 January 2010

Published in: Séminaire Lotharingien de Combinatoire (Search for Journal in Brave)

Abstract: Despite having been introduced in 1962 by C.L. Mallows, the combinatorial algorithm Patience Sorting is only now beginning to receive significant attention due to such recent deep results as the Baik-Deift-Johansson Theorem that connect it to fields including Probabilistic Combinatorics and Random Matrix Theory. The aim of this work is to develop some of the more basic combinatorics of the Patience Sorting Algorithm. In particular, we exploit the similarities between Patience Sorting and the Schensted Insertion Algorithm in order to do things that include defining an analog of the Knuth relations and extending Patience Sorting to a bijection between permutations and certain pairs of set partitions. As an application of these constructions we characterize and enumerate the set S_n(3-�ar{1}-42) of permutations that avoid the generalized permutation pattern 2-31 unless it is part of the generalized pattern 3-1-42.

Full work available at URL: https://arxiv.org/abs/math/0506358

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Restricted patience sorting and barred pattern avoidance
• A geometric form for the extended patience sorting algorithm
• Combinatorics of patience sorting monoids
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• scientific article; zbMATH DE number 2107707

zbMATH Keywords

Bell numbersset partitionsgeneralized permutation patternspatience sortingbasic subsequencesleft-to-right minima subsequencesshadow diagrams

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Partitions of sets (05A18) Combinatorial aspects of representation theory (05E10)

Cited In (9)

• The monoids of the patience sorting algorithm
• Space-efficient algorithms for longest increasing subsequence
• Space-efficient algorithms for longest increasing subsequence
• A geometric form for the extended patience sorting algorithm
• Random matrix theory and its applications
• Asymptotically fastest sorting algorithm for almost sorted arrays
• Restricted patience sorting and barred pattern avoidance
• Descents and des-Wilf equivalence of permutations avoiding certain nonclassical patterns
• Combinatorics of patience sorting monoids

This page was built for publication: Combinatorics of patience sorting piles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2654575)