Longest Increasing Subsequences of Randomly Chosen Multi-Row Arrays
Artículo
![Thumbnail](/themes/Mirage2/images/cubierta.jpg)
Open/ Download
Publication date
2015Metadata
Show full item record
Cómo citar
Kiwi Krauskopf, Marcos
Cómo citar
Longest Increasing Subsequences of Randomly Chosen Multi-Row Arrays
Abstract
To Philippe Flajolet, a mathematical discontinuity, a tamer of singularities. A two-row array of integers an = a1 a2 ... an b1 b2 ... bn 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 < ak+ 1, or bk bk+ 1 when ak = ak+ 1). A length (strictly) increasing subsequence of an is a set of indices i1 < i2 < u u u < i such that ai1 < ai2 < ... < ai and bi1 < bi2 < ... < bi . We are interested in the statistics of the length of a longest increasing subsequence of an chosen according to Dn, for different families of distributions D = (Dn) n. N, 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.
General note
Artículo de publicación ISI
Patrocinador
FONDECYT
1090227, and Núcleo Milenio Información y Coordinación en Redes ICM/FI P10-024F
Identifier
URI: https://repositorio.uchile.cl/handle/2250/132719
DOI: DOI: 10.1017/S0963548314000637
ISSN: 1469-2163
Quote Item
Combinatorics, Probability and Computing (2015) 24, 254–293
Collections
The following license files are associated with this item: