Longest Increasing Subsequences of Randomly Chosen Multi-Row Arrays. (2nd October 2014)

• Record Type: Journal Article
• Authors: KIWI, MARCOS; SOTO, JOSÉ A.
• Editors: Broutin, Nicolas; Fill, James Allen; Nebel, Markus; Ward, Mark Daniel
• Is Part Of: Combinatorics, probability and computing. Volume 24:Number 1(2015:Jan.)
• Page Start: 254
• Page End: 293
• Publication Date: 2014-10-02
• Subjects: 60C05; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000637
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : A two-row array of integers \[ \alpha_{n}= \begin{pmatrix}a_1 & a_2 & \cdots & a_n\\ b_1 & b_2 & \cdots & b_n \end{pmatrix} \] is said to be in lexicographic order if its columns are in lexicographic order (where character significance decreases from top to bottom, i.e., either ak < a k +1, or bk ≤ b k +1 when ak = a k +1 ). A length ℓ (strictly) increasing subsequence of α n is a set of indices i 1 < i 2 < ⋅⋅⋅ < i ℓ such that a i 1 < a i 2 < ⋅⋅⋅ < a i ℓ and b i 1 < b i 2 < ⋅⋅⋅ < b i ℓ . We are interested in the statistics of the length of a longest increasing subsequence of α n chosen according to ${\cal D}$ n, for different families of distributions ${\cal D} = ({\cal D}_{n})_{n\in\NN}$, and when n goes to infinity. This general framework encompasses well-studied problems such as the so-called longest increasing subsequence problem, the longest common subsequence problem, and problems concerning directed bond percolation models, among others. We define several natural families of different distributions and characterize the asymptotic behaviour of the length of a longest increasing subsequence chosen according to them. In particular, we consider generalizations to d -row arrays as well as symmetry-restricted two-row arrays.