No Detail Found!

Average length of the longest increasing subsequences in random involutions avoiding 231 and a layered pattern

Author(s)
Toufik Mansour Department of Mathematics, University of Haifa,3498838 Haifa,Israel
Chunwei Song School of Mathematical Sciences, LMAM, Peking University,100871 Beijing,P. R. China
Abstract
The problems of deciding the length of the longest increasing subsequence for a permutation or an involution, the expectation and the limiting distribution, surveyed in Stanley's ICM (International Congress of Mathematicians) Plenary address, have been widely studied by combinatorialists, analysts and probabilists. Partially motivated by the intriguing phenomenon stated by Simion and Schmidt [European J. Combin. 6 (1985) 383-406] that 231-avoiding permutations are exactly the set of layered permutations, in this paper, we investigate the limiting behavior of the average length of the longest increasing subsequences in random involutions avoiding 231 and another pattern which is a layered permutation. We obtain an explicit formula of the generating function and apply it to exemplify a set of interesting examples, which extend recent results of the first author with Yildirim [Turkish J. Math. 43 (2019) 2183-2192], where the longest increasing subsequences in involutions avoiding a pair of patterns of length 3 are studied.
Publication Details
Page(s) 56-59
DOI DOI not available
Published Journal: Discrete Mathematics Letters, Volume: 4, Issue: 0, Year: 2020

Request the full text from PASTIC

Keywords
longest increasing subsequence problem, pattern-avoiding involutions, pattern-avoidance, generating functions
References
Aldous D.,Diaconis P. .1999 .Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull. Amer. Math. Soc. (N.S.), 36 : 413-432.
Baik J.,Deift P.,Johansson K. .1999 .On the distribution of the length of the longest increasing subsequence of random permutations. J. Amer. Math. Soc, 12 : 1119-1178.
Baik J.,Deift P. .2016 .. American Mathematical Society, : .
Bo M. .2012 .´na, Combinatorics of Permutations, Second Edition. , : .
I. Corwin .2018 .Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem” by David Aldous and Persi Diaconis. Bull. Amer. Math. Soc. (N.S.), 55 : 363-374.
Deift P. .2007 .. Vol. I, Eur. Math. Soc., : 125-152.
Egge E. S.,Mansour T .2004 .231-avoiding involutions and Fibonacci numbers. Australas. J. Combin, 30 : 75-84.
Kitaev S. .2011 .. , : .
Logan B. F.,Shepp L. A. .1977 .A variational problem for random Young tableaux. , 26 : 206-222.
Madras N. . .Longest monotone subsequences and rare regions of pattern-avoiding permutations. Electron. J. Combin, 24(2017) : 13.
Mansour T. .2019 .Longest increasing subsequences in involutions avoiding patterns of length three. , 43 : 2183-2192.
Mansour T. . .Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences. Adv. Appl, 116(2020) : 102002.
Romik D. .2015 .. The Surprising Mathematics of Longest Increasing Subsequences, : .
Rotem D. .1981 .. , 33 : 185-196.
Seppa T. . .¨ la¨ inen, A microscopic model for the Burgers equation and longest increasing subsequences. Electron. J. Probab. 1, (1996) : 5.
Simion R.,Schmidt F. W. .1985 .. European J. Combin, 6 : 383-406.
Stanley R. P. .2003 .Recent progress in algebraic combinatorics. Bull. Amer. Math. Soc. (N.S.), 40 : 55-68.
Stanley R. P.,Subsequences Decreasing,Variants Their .2006 .. Proceedings of the International Congress of Mathematicians, : 545-579.
Tracy C. A.,Widom H. .1994 .Level-spacing distributions and the Airy kernel. Comm. Math. Phys. 159, : 151-174.
A. M. Versˇik S. V.,Kerov S. V. .1977 .Asymptotic behavior of the Plancherel measure of the symmetric group and the limit form of Young tableaux. Dokl. Akad. Nauk, 233 : 1024-1027.
Wilf H. S. .1994 .. , : .
0

Citations

0

Downloads

13

Views