Longest Increasing and Decreasing Subsequences

DOI10.4153/CJM-1961-015-3zbMath0097.25202OpenAlexW4235936977WikidataQ56004216 ScholiaQ56004216MaRDI QIDQ3276710

Craige Schensted

Publication date: 1961

Published in: Canadian Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4153/cjm-1961-015-3

zbMATH Keywords

combinatorics

Related Items

Invariance of polymer partition functions under the geometric RSK correspondence, Tableau atoms and a new Macdonald positivity conjecture, Generalization of Schensted insertion algorithm to the cases of hooks and semi-shuffles, Hall-Littlewood RSK field, Generalized Robinson-Schensted correspondence: A new algorithm, Duality of graded graphs, A pair of dual Hopf algebras on permutations, Longest increasing subsequences in sliding windows, RSK in last passage percolation: a unified approach, Crystal monoids \& crystal bases: rewriting systems and biautomatic structures for plactic monoids of types \(A_{n}\), \(B_{n}\), \(C_{n}\), \(D_{n}\), and \(G_{2}\), Schensted algorithms for dual graded graphs, An alternative presentation of the Schensted correspondence, The Robinson-Schensted correspondence for skew oscillating tableaux, Combinatorial \(R\) matrices for a family of crystals: \(B_n^{(1)}\), \(D_n^{(1)}\), \(A_{2n}^{(2)}\) and \(D_{n+1}^{(2)}\) cases, Generating trees and the Catalan and Schröder numbers, Orthosymplectic Cauchy identities, The stylic monoid, A Robinson-Schensted algorithm for a class of partial orders, Noncommutative symmetric functions. IV: Quantum linear groups and Hecke algebras at \(q=0\), Quasisymmetric and noncommutative skew Pieri rules, Computing the longest common almost-increasing subsequence, Computing longest (common) Lyndon subsequences, On embedding certain Kazhdan-Lusztig cells of \(S_n\) into cells of \(S_{n+1}\), An orthosymplectic Pieri rule, An insertion algorithm on multiset partitions with applications to diagram algebras, Tableau algorithms defined naturally for pictures, The bijection between plane partitions and nonnegative matrices, Sequences of symmetric polynomials and combinatorial properties of tableaux, Knuth's coherent presentations of plactic monoids of type A, Longest increasing subsequences and log concavity, Modular Nekrasov-Okounkov formulas, An insertion algorithm for diagram algebras, Limit theorems for longest monotone subsequences in random Mallows permutations, Plactic monoids: a braided approach, On the longest common subsequence of conjugation invariant random permutations, Pattern avoidance in matchings and partitions, Fast computation of a longest increasing subsequence and application, Lyndon words, permutations and trees., The distribution of the length of the longest increasing subsequence in random permutations of arbitrary multi-sets, Monotonous subsequences and the descent process of invariant random permutations, Computing a longest common almost-increasing subsequence of two sequences, Plactic algebras., Tropical plactic algebra, the cloaktic monoid, and semigroup representations, On extremal permutations avoiding \(\omega_N=NN-1\dots 1\), General tests of independence based on empirical processes indexed by functions, \(R\)-systems, Schubert polynomials, the Bruhat order, and the geometry of flag manifolds, Flag varieties and interpretations of Young tableau algorithms, Iterating the RSK bijection, Pattern avoidance and quasisymmetric functions, Lattice paths, Young tableaux, and weight multiplicities, Space-efficient algorithms for longest increasing subsequence, Improvised divide and conquer approach for the LIS problem, A \(q\)-deformation of the symplectic Schur functions and the Berele insertion algorithm, A generalization of plactic-coplactic equivalences and Kazhdan-Lusztig cells., A simple counting argument of the irreducible representations of \(\mathsf{SU}(N)\) on mixed product spaces, The peak algebra of the symmetric group revisited., Factorization of the Robinson-Schensted-Knuth correspondence, Action of the symmetric group on sets of skew-tableaux with prescribed matrix realization, Vogan classes in type \(B_n\), A Nekrasov-Okounkov formula for Macdonald polynomials, A generalization of Edelman-Greene insertion for Schubert polynomials, Rank tests from partially ordered data using importance and MCMC sampling methods, Bigrassmannian permutations and Verma modules, Tableau stabilization and rectangular tableaux fixed by promotion powers, Kazhdan-Lusztig representations and Whittaker space of some genuine representations, Zigzag diagrams and Martin boundary, On Schensted's construction and the multiplication of Schur functions, A Pieri formula in the Grothendieck ring of a flag bundle, Bases for coordinate rings of conjugacy classes of nilpotent matrices, Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences, Bijection between indexed monomials and standard bitableaux, Percentage-avoiding, northwest shapes and peelable tableaux, Toward a local characterization of crystals for the quantum queer superalgebra, A diagonal-based algorithm for the longest common increasing subsequence problem, Combinatorics of patience sorting monoids, Balanced tableaux, A characteristic property of labelings and linear extensions of posets of dimension 2, Block number, descents and Schur positivity of fully commutative elements in \(B_n\), \(3d\) field theory, plane partitions and triple Macdonald polynomials, Chinese syzygies by insertions, Gröbner bases and Stanley decompositions of determinantal ideals, On odd symplectic Schur functions, Explicit enumeration of 321, hexagon-avoiding permutations, Anisotropic Young diagrams and Jack symmetric functions, Multiplying Schur \(Q\)-functions, Position sequences and a \(q\)-analogue for the modular hook length formula, Enumerative aspects of certain subclasses of perfect graphs, Kernelization lower bound for permutation pattern matching, Grammic monoids with three generators, Lengths of monotone subsequences in a Mallows permutation, Affine type A crystal structure on tensor products of rectangles, Demazure characters, and nilpotent varieties, Hopf algebra structure on packed square matrices., The Burge correspondence and crystal graphs, Shape avoiding permutations, Counting permutations with given cycle structure and descent set, Doubly stochastic matrices and Schur-Weyl duality for partition algebras, Brauer diagrams, updown tableaux and nilpotent matrices, Multiplicities of some maximal dominant weights of the \(\widehat{s\ell }(n)\)-modules \(V (k \Lambda_0)\), Fast and longest rollercoasters, Notes on Schubert, Grothendieck and key polynomials, On growing a random Young tableau, Recognizable subsets of the two letter plactic monoid, Word reading is a crystal morphism, A fast algorithm for computing a longest common increasing subsequence, Diagonal invariants and the refined multimahonian distribution., Enumerating longest increasing subsequences and patience sorting, A fast algorithm for permutation pattern matching based on alternating runs, A linear space algorithm for computing a longest common increasing subsequence, On the longest increasing subsequence of a circular list, Polynuclear growth on a flat substrate and edge scaling of GOE eigenvalues, Refined restricted involutions, Similar constructions for Young tableaux and involutions, and their application to shiftable tableaux, Shifted tableaux, Schur q-functions, and a conjecture of R. Stanley, Permutation statistics and \((k,\ell)\)-hook Schur functions, Tableaux and matrix correspondences, Standard Young tableaux of height 4 and 5, A central limit theorem for extremal characters of the infinite symmetric group., Bijections for refined restricted permutations, Link homology theories from symplectic geometry, An extension of Brualdi's algorithm for the construction of \((0,1)\)-matrices with prescribed row and column sum vectors, Computing a longest common subsequence that is almost increasing on sequences having no repeated elements, A Pieri rule for skew shapes, An analog of Schensted's algorithm for shifted Young tableaux, A Polya interpretation of the Schur function, Equivalence classes of permutations modulo replacements between 123 and two-integer patterns, Crystal \(B(\lambda)\) as a subset of crystal \(B(\infty)\) expressed as tableaux for \(A_n\) type, Oscillating rim hook tableaux and colored matchings, Modified growth diagrams, permutation pivots, and the BWX map \(\phi ^{\ast}\), Words and polynomial invariants of finite groups in non-commutative variables, Descending subsequences of random permutations, On the equality of two plane partition correspondences, Signed enumeration of ribbon tableaux: an approach through growth diagrams, The number of increasing subsequences of the random permutation, Some connections between the Littlewood-Richardson rule and the construction of Schensted, On mixed insertion, symmetry, and shifted Young tableaux, Generalized Robinson-Schensted-Knuth correspondence, The Hillman-Grassl correspondence and the enumeration of reverse plane partitions, Tournaments and generalized Young tableaux, Symmetric functions and P-recursiveness, On the Lipschitz constant of the RSK correspondence, The Cauchy identity for \(Sp(2n)\), Descent sets on 321-avoiding involutions and hook decompositions of partitions, Some aspects of groups acting on finite posets, Coinsertion and standard bitableaux, A symmetry property for \(q\)-weighted Robinson-Schensted and other branching insertion algorithms, The number of involutions with \(r\) fixed points and a long increasing subsequence, On increasing subsequences of minimal Erdős-Szekeres permutations, Tableaux and insertion schemes for spinor representations of the orthogonal Lie algebra \(so(2r+1,\mathbb{C})\), Generalized roinsertive correspondence between multitableaux and multimonomials, Enumerating \(r\)c-invariant permutations with no long decreasing subsequences, The generalized Robinson-Schensted algorithm on the affine Weyl group of type \(A_{n-1}\), Joint relations on elements of the symmetric group., Finite Gröbner-Shirshov bases for plactic algebras and biautomatic structures for plactic monoids., New approaches to plactic monoid via Gröbner-Shirshov bases., A Robinson-Schensted-type algorithm for \(SO(2n,\mathbb{C})\), Matrices, characters and descents, Generalized rodeletive correspondence between multitableaux and multimonomials, Algorithms for generating labelled graphs with given degree, On a bijection between Littlewood-Richardson fillings of conjugate shape, Comparing bacterial genomes from linear orders of patterns, Eulerian numbers, tableaux, and the Betti numbers of a toric variety, Crystallizing the hypoplactic monoid: from quasi-Kashiwara operators to the Robinson-Schensted-Knuth-type correspondence for quasi-ribbon tableaux, Enumeration of generalized Young tableaux with bounded height, On the representation theory of the symmetric groups and associated Hecke algebras, Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm, Gröbner bases and multiplicity of determinantal and Pfaffian ideals, Counting permutations with no long monotone subsequence via generating trees and the kernel method, A Robinson-Schensted-type correspondence for a dual pair on spinors, Generalized coinsertion and standard multitableaux, An extension of Schensted's theorem, Evacuation and a geometric construction for Fibonacci tableaux, The algebra of binary search trees, On a correspondence between binary trees and a certain type of permutation, Enumeration of permutations with prescribed up-down and inversion sequences, Rational tableaux and the tensor algebra of \(gl_ n\), On a construction of Schätzenberger, A variational problem for random Young tableaux, Efficient algorithms for finding a longest common increasing subsequence, Ascending sequences in permutations, Some results on hook lengths, Young-Fibonacci insertion, tableauhedron and Kostka numbers, Enumeration des tableaux Standards, Bijections between oscillating tableaux and (semi)standard tableaux via growth diagrams, Structure constants for \(K\)-theory of Grassmannians, revisited, Multicolored permutations, sequences, and tableaux, Orthogonal tableaux and an insertion algorithm for \(SO(2n+1)\), On (0, 1)-matrices with prescribed row and column sum vectors, The longest almost-increasing subsequence, Untangling a planar graph, Almost avoiding permutations, A bijection proving orthogonality of the characters of \(S_ n\), Hook flag characters and their combinatorics, A Schensted algorithm for rim hook tableaux, Hybrid tableaux and the Littlewood-Richardson rule, Robinson-Schensted algorithms for skew tableaux, Multivariate polynomials, standard tableaux, and representations of symmetric groups, Two descent statistics over \(321\)-avoiding centrosymmetric involutions, The estimate of the number of permutationally-ordered sets, Shuffles of permutations and the Kronecker product, Recent progress in algebraic combinatorics, Limit shape for infinite rank limit of tensor power decomposition for Lie algebras of series so2n+1 ^*, The Schensted Correspondence and Lexicographic Matchings on Multisubset Lattices, Acyclic Digraphs, Young Tableaux and Nilpotent Matrices, Demazure crystals for Kohnert polynomials, Insertion Scheme for the Classical Lie Algebras, THE CHINESE MONOID, On the distribution of the length of the longest increasing subsequence of random permutations, A bijective proof of a factorization theorem for (k,l)-hook schur functions, Longest increasing subsequences in windows based on canonical antichain partition, Maxima of log-correlated fields: some recent developments*, Breakthroughs in the theory of Macdonald polynomials, Monotone subsets in lattices and the Schensted shape of a Sós permutation, Variations on Hammersley’s interacting particle process, Intersecting principal Bruhat ideals and grades of simple modules, Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem, Largest planar matching in random bipartite graphs, Growth diagrams from polygons in the affine Grassmannian, A Pieri rule for key polynomials, Dual equivalence graphs and CAT(0) combinatorics, On the Littlewood-Richardson rule in terms of lattice path combinatorics, Unnamed Item, Schröder partitions, Schröder tableaux and weak poset patterns, Limit shapes for random square Young tableaux, Estimates in Shirshov height theorem, A Generalized Berele-Schensted Algorithm and Conjectured Young Tableaux for Intermediate Symplectic Groups, Unnamed Item, Minimal determining sets for certain $W$-graph ideals, Probabilistic existence of regular combinatorial structures, Irreducible representations of the plactic algebra of rank four, Super jeu de taquin and combinatorics of super tableaux of type A, A \(q\)-Robinson-Schensted-Knuth algorithm and a \(q\)-polymer, Longest monotone subsequences and rare regions of pattern-avoiding permutations, Partition into Heapable Sequences, Heap Tableaux and a Multiset Extension of Hammersley’s Process, Theory and Application of Plane Partitions: Part 1, Theory and Application of Plane Partitions. Part 2, Space-Efficient Algorithms for Longest Increasing Subsequence, Super RSK correspondence with symmetry, On cyclic quiver parabolic Kostka-Shoji polynomials, Identities of tropical matrix semigroups and the plactic monoid of rank 4, Some algebraic structures in KPZ universality, A new approach to word standardization and some of its applications, Rigged configuration descriptions of the crystals B(∞) and B(λ) for special linear Lie algebras, Box-ball systems and RSK tableaux, Multicritical random partitions, Tropical representations and identities of the stylic monoid, Goldie ranks of hook ideals in type a, Robinson–Schensted Correspondence for the Walled Brauer Algebras and the Walled Signed Brauer Algebras, Plactic key agreement (insecure?), The Preisach graph and longest increasing subsequences, Second class particles and limit shapes of evacuation and sliding paths for random tableaux., Combinatorial approach to the representation of the Schur-Weyl duality in one-dimensional spin systems, Fonctions symétriques et séries hypergéométriques basiques multivariées, Independence tests for continuous random variables based on the longest increasing subsequence, A divide and conquer approach and a work-optimal parallel algorithm for the LIS problem, Symmetric functions in noncommuting variables, The monoids of the patience sorting algorithm, Major Index and Inversion Number of Permutations, On the longest upsequence problem for permutations, Inner tableau translation property of the weak order and related results, On ordered k-paths and rims for certain families of Kazhdan–Lusztig cells of Sn, Stable Grothendieck polynomials and \(K\)-theoretic factor sequences, On subsequences and certain elements which determine various cells in \(S_n\), The Robinson-Schensted correspondence for skew oscillating semi-standard tableaux, Rees algebra of ideals generated by pfaffians, A cyclage poset structure for Littlewood-Richardson tableaux, Finite posets and Ferrers shapes, Decreasing subsequences in permutations and Wilf equivalence for involutions, An inversion formula involving partitions, Restricted permutations, On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation, A Matrix-analog for Viennot's construction of the Robinson correspondence^†, Finding longest increasing and common subsequences in streaming data, Properties of four partial orders on standard Young tableaux, Inverses of words and the parabolic structure of the symmetric group, Complementary algorithms for tableaux, Permutrees, Unnamed Item, Sorting shuffled monotone sequences, On the annihilators of the simple subquotients of the principal series, Asymptotics of Plancherel measures for symmetric groups, On the distribution of the length of the longest increasing subsequence in a random permutation, Identities in character tables ofS_n, Tableau stabilization and lattice paths, GENERALIZATION OF THE SCHENSTED ALGORITHM FOR RIM HOOK TABLEAUX, THE JEU DE TAQUIN ON THE SHIFTED RIM HOOK TABLEAUX, Virtual crystals and fermionic formulas of type 𝐷_{𝑛+1}⁽²⁾, 𝐴_{2𝑛}⁽²⁾, and 𝐶_{𝑛}⁽¹⁾, A matrix model for plane partitions, Tropical representations and identities of plactic monoids, Finding maximum cliques in circle graphs, SUPER RSK-ALGORITHMS AND SUPER PLACTIC MONOID, Unnamed Item, Crossings and nestings of matchings and partitions, All order asymptotic expansion of large partitions, Expected length of the longest common subsequence for large alphabets, Minimal and maximal elements in two-sided cells of \(S_n\) and Robinson-Schensted correspondence, SOME PROPERTIES OF SCHENSTED ALGORITHM USING VIENNOT'S GEOMETRIC INTERPRETATION, Young tableaux and longest monotone subsequences: An inequality and a conjecture, Identities and bases in the hypoplactic monoid, A note on the Formanek Weingarten function, Multiparameter colored partition category and the product of the reduced Kronecker coefficients, Finite basis problems for stalactic, taiga, sylvester and baxter monoids, Skew RSK dynamics: Greene invariants, affine crystals and applications toq-Whittaker polynomials, The Eulerian distribution on the fixed-point free involutions of the hyperoctahedral group, A Maple package for combinatorial aspects of Bethe ansatz, Cyclic descents, matchings and Schur-positivity, Recursion relation for Toeplitz determinants and the discrete Painlevé II hierarchy, Monk's rule for Demazure characters of the general linear group, RSK tableaux and the weak order on fully commutative permutations, Counting crucial permutations with respect to monotone patterns, Computing longest Lyndon subsequences and longest common Lyndon subsequences, Top-degree components of Grothendieck and Lascoux polynomials, RSK tableaux and box-ball systems, Representations and identities of hypoplactic monoids with involution, The number of inversions of permutations with fixed shape, Permutations whose reverse shares the same recording tableau in the RS correspondence, Longest bordered and periodic subsequences, Rowmotion on 321-avoiding permutations, General tests of conditional independence based on empirical processes indexed by functions, Identities and bases in the Sylvester and Baxter monoids, Coherence for plactic monoids via rewriting theory and crystal structures, Skew Howe duality and limit shapes of Young diagrams, Computing balanced convex partitions of lines, Minuscule reverse plane partitions via quiver representations, A generalization of the Kostka-Foulkes polynomials, The shifted plactic monoid, The Schützenberger involution over Dyck paths