{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T13:00:46Z","timestamp":1649077246543},"reference-count":30,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,10,2]],"date-time":"2014-10-02T00:00:00Z","timestamp":1412208000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>A two-row array of integers\n<jats:disp-formula-group><jats:disp-formula><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0963548314000637_eqnU1\" \/><jats:tex-math>\n\\[\n\\alpha_{n}= \\begin{pmatrix}a_1 &amp; a_2 &amp; \\cdots &amp; a_n\\\\ \nb_1 &amp; b_2 &amp; \\cdots &amp; b_n \\end{pmatrix}\n\\]\n<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula><\/jats:disp-formula-group>\nis said to be in lexicographic order if its columns are in lexicographic order (where character significance decreases from top to bottom, <jats:italic>i.e.<\/jats:italic>, either <jats:italic>a<jats:sub>k<\/jats:sub><\/jats:italic> &lt; <jats:italic>a<\/jats:italic><jats:sub><jats:italic>k<\/jats:italic>+1<\/jats:sub>, or <jats:italic>b<jats:sub>k<\/jats:sub><\/jats:italic> \u2264 <jats:italic>b<\/jats:italic><jats:sub><jats:italic>k<\/jats:italic>+1<\/jats:sub> when <jats:italic>a<jats:sub>k<\/jats:sub><\/jats:italic> = <jats:italic>a<\/jats:italic><jats:sub><jats:italic>k<\/jats:italic>+1<\/jats:sub>). A length \u2113 (strictly) increasing subsequence of \u03b1<jats:italic><jats:sub>n<\/jats:sub><\/jats:italic> is a set of indices <jats:italic>i<\/jats:italic><jats:sub>1<\/jats:sub> &lt; <jats:italic>i<\/jats:italic><jats:sub>2<\/jats:sub> &lt; \u22c5\u22c5\u22c5 &lt; <jats:italic>i<\/jats:italic><jats:sub>\u2113<\/jats:sub> such that <jats:italic>a<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><jats:sub>1<\/jats:sub><\/jats:sub> &lt; <jats:italic>a<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><jats:sub>2<\/jats:sub><\/jats:sub> &lt; \u22c5\u22c5\u22c5 &lt; <jats:italic>a<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><jats:sub>\u2113<\/jats:sub><\/jats:sub> and <jats:italic>b<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><jats:sub>1<\/jats:sub><\/jats:sub> &lt; <jats:italic>b<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><jats:sub>2<\/jats:sub><\/jats:sub> &lt; \u22c5\u22c5\u22c5 &lt; <jats:italic>b<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><jats:sub>\u2113<\/jats:sub><\/jats:sub>. We are interested in the statistics of the length of a longest increasing subsequence of \u03b1<jats:italic><jats:sub>n<\/jats:sub><\/jats:italic> chosen according to <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548314000637_inline1\" \/><jats:tex-math>${\\cal D}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula><jats:italic><jats:sub>n<\/jats:sub><\/jats:italic>, for different families of distributions <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548314000637_inline2\" \/><jats:tex-math>${\\cal D} = ({\\cal D}_{n})_{n\\in\\NN}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, and when <jats:italic>n<\/jats:italic> 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 <jats:italic>d<\/jats:italic>-row arrays as well as symmetry-restricted two-row arrays.<\/jats:p>","DOI":"10.1017\/s0963548314000637","type":"journal-article","created":{"date-parts":[[2014,10,2]],"date-time":"2014-10-02T14:16:35Z","timestamp":1412259395000},"page":"254-293","source":"Crossref","is-referenced-by-count":1,"title":["Longest Increasing Subsequences of Randomly Chosen Multi-Row Arrays"],"prefix":"10.1017","volume":"24","author":[{"given":"MARCOS","family":"KIWI","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JOS\u00c9 A.","family":"SOTO","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,10,2]]},"reference":[{"key":"S0963548314000637_ref29","doi-asserted-by":"crossref","first-page":"886","DOI":"10.1214\/aoap\/1043862416","article-title":"Increasing sequences of independent points on the planar lattice.","volume":"7","author":"Sepp\u00e4l\u00e4inen","year":"1997","journal-title":"Ann. Appl. Probab."},{"key":"S0963548314000637_ref17","doi-asserted-by":"publisher","DOI":"10.1017\/S0001867800016621"},{"key":"S0963548314000637_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S0001867800007205"},{"key":"S0963548314000637_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S0021900200047999"},{"key":"S0963548314000637_ref10","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005586"},{"key":"S0963548314000637_ref19","first-page":"627","article-title":"The optimum choice of the instant for stopping a Markov process.","volume":"4","author":"Dynkin","year":"1963","journal-title":"Sov. Math. Doklady"},{"key":"S0963548314000637_ref22","volume-title":"Inequalities","author":"Hardy","year":"1952"},{"key":"S0963548314000637_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-4149(01)00122-3"},{"key":"S0963548314000637_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S0001867800009010"},{"key":"S0963548314000637_ref28","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176994265"},{"key":"S0963548314000637_ref20","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1966.10502008"},{"key":"S0963548314000637_ref1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-99-00796-X"},{"key":"S0963548314000637_ref6","unstructured":"Babaioff M. , Immorlica N. and Kleinberg R. (2007) Matroids, secretary problems, and online mechanisms. In Proc. 18th SODA, pp. 434\u2013443."},{"key":"S0963548314000637_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000411"},{"key":"S0963548314000637_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/S0021900200008652"},{"key":"S0963548314000637_ref15","doi-asserted-by":"crossref","first-page":"612","DOI":"10.2307\/1427625","article-title":"`Wald's Lemma' for sums of order statistics of i.i.d. random variables.","volume":"23","author":"Bruss","year":"1991","journal-title":"Adv. Appl. Probab."},{"key":"S0963548314000637_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.03.025"},{"key":"S0963548314000637_ref5","doi-asserted-by":"crossref","unstructured":"Babaioff M. , Immorlica N. , Kempe D. and Kleinberg R. (2007) A knapsack secretary problem with applications. In Proc. 10th APPROX and 11th RANDOM, pp. 16\u201328.","DOI":"10.1007\/978-3-540-74208-1_2"},{"key":"S0963548314000637_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.spa.2004.09.002"},{"key":"S0963548314000637_ref26","unstructured":"Odlyzko A. and Rains E. (1998) On longest increasing subsequences in random permutations. Technical report, AT&T Labs."},{"key":"S0963548314000637_ref8","first-page":"1","volume-title":"Random Matrix Models and their Applications","author":"Baik","year":"2001"},{"key":"S0963548314000637_ref30","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-02-00966-7"},{"key":"S0963548314000637_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2004.10.012"},{"key":"S0963548314000637_ref27","doi-asserted-by":"publisher","DOI":"10.1017\/S0021900200042856"},{"key":"S0963548314000637_ref7","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-99-00307-0"},{"key":"S0963548314000637_ref9","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1214\/aoap\/1019737672","article-title":"Sequential selection of an increasing sequence from a multidimensional random sample.","volume":"10","author":"Baryshnikov","year":"2000","journal-title":"Ann. Appl. Probab."},{"key":"S0963548314000637_ref11","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1988-0943043-6"},{"key":"S0963548314000637_ref21","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548399004149"},{"key":"S0963548314000637_ref23","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548314000637_ref18","doi-asserted-by":"publisher","DOI":"10.1145\/2491533.2491557"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548314000637","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,21]],"date-time":"2019-04-21T20:55:11Z","timestamp":1555880111000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548314000637\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,2]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["S0963548314000637"],"URL":"https:\/\/doi.org\/10.1017\/s0963548314000637","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,2]]}}}