Longest increasing subsequences in involutions avoiding patterns of length three

Longest increasing subsequences in involutions avoiding patterns of length three

We study the longest increasing subsequences in random involutions that avoid the patterns of length threeunder the uniform probability distribution. We determine the exact and asymptotic formulas for the average length ofthe longest increasing subsequences for such permutation classes.

___

  • [1] Aldous D, Diaconis P. Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bulletin of the American Mathematical Society 1999; 36 (4): 413-432. doi: 10.1090/S0273-0979-99-00796-X
  • [2] Baik J, Deift P, Johansson K. On the distribution of the length of the longest increasing subsequence of random permutations. Journal of the American Mathematical Society 1999; 12 (4): 1119-1178. doi: 10.1090/S0894-0347- 99-00307-0
  • [3] Baik J, Deift P, Suidan T. Combinatorics and Random Matrix Theory. Graduate Studies in Mathematics, Vol. 172. Providence, RI, USA: American Mathematical Society, 2016.
  • [4] Bóna M. Combinatorics of Permutations, Second Edition. London, UK: Chapman and Hall/CRC Press, 2012.
  • [5] Bóna M, Homberger C, Pantone J, Vatter V. Pattern-avoiding involutions: exact and asymptotic enumeration. Australasian Journal of Combinatorics 2016; 64: 88-119.
  • [6] Chinn PZ, Grimaldi R, Heubach S. The frequency of summands of a particular size in palindromic compositions. Ars Combinatoria 2003; 69: 65-78.
  • [7] Corwin I. Comments on David Aldous and Persi Diaconis’ “Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem”. Bulletin of the American Mathematical Society 2018; 55: 363-374. doi: 10.1090/bull/1623
  • [8] Deift P. Universality for mathematical and physical systems. In: Proceedings of the International Congress of Mathematicians, Vol. I; Madrid, Spain; 2006. pp. 125-152. doi: 10.4171/022-1/7
  • [9] Deutsch E, Hildebrand AJ, Wilf HS. Longest increasing subsequences in pattern-restricted permutations. Electronic Journal Combinatorics 2002; 9 (2): 12.
  • [10] Dukes WMB, Jelínek V, Mansour T, Reifegerste A. New equivalences for pattern avoiding involutions. Proceedings of the American Mathematical Society 2009; 137 (2): 457-465.
  • [11] Egge E, Mansour T. 231-avoiding involutions and Fibonacci numbers. Australasian Journal of Combinatorics 2004; 30: 75-84.
  • [12] Egge E, Mansour T. Bivariate generating functions for involutions restricted by 3412. Advances in Applied Mathematics 2006; 36 (2): 118-137. doi.org/10.1016/j.aam.2005.01.005
  • [13] Erdös P, Szekeres G. A combinatorial theorem in geometry. Compositio Mathematica 1935; 2: 463-470.
  • [14] Flajolet P, Sedgewick R. Analytic Combinatorics. Cambridge, UK: Cambridge University Press, 2009.
  • [15] Guibert O. Combinatoire des permutations à motifs exclus en liaison avec mots, cartes planaires et tableaux de Young. PhD, Université Bordeaux, Bordeaux, France, 1995 (in French).
  • [16] Guibert O, Mansour T. Restricted 132-involutions. Séminaire Lotharingien de Combinatoire 2002; 48: B48a.
  • [17] Guibert O, Mansour T. Some statistics on restricted 132 involutions. Annals of Combinatorics 2002; 6: 349-374.
  • [18] Hammersley JM. A few seedlings of research. In: Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1; Berkeley, CA, USA; 1972. pp. 345–394.
  • [19] Hoffman C, Rizzolo D, Slivken E. Fixed points of 321-avoiding permutations. Proceedings of the American Mathematical Society 2019; 147 (2): 861-872. doi: 10.1090/proc/14299
  • [20] Jaggard AD, Marincel JJ. Generating-tree isomorphisms for pattern-avoiding involutions. Annals of Combinatorics 2011; 15 (3): 437-448. doi: 10.1007/s00026-011-0101-x
  • [21] Kemp R. On the average depth of a prefix of the Dycklanguage D1 . Discrete Mathematics 1981; 36: 155-170. doi: 10.1016/0012-365X(81)90235-1
  • [22] Madras N, Pehlivan L. Large deviations for permutations avoiding monotone patterns. Electronic Journal of Combinatorics 2016; 23 (4): P4.36.
  • [23] Madras N, Yıldırım G. Longest monotone subsequences and rare regions of pattern-avoiding permutations. Electronic Journal of Combinatorics 2017; 24 (4): 1-29.
  • [24] Miner S, Rizzolo D, Slivken E. Asymptotic distribution of fixed points of pattern-avoiding involutions. Discrete Mathematics Theoretical Computer Science 2017; 19 (2): 5. doi: 10.23638/DMTCS-19-2-5
  • [25] Riordan J. Combinatorial Identities. New York, NY, USA: John Wiley, 1968.
  • [26] Romik D. The Surprising Mathematics of Longest Increasing Subsequences. Institute of Mathematical Statistics Textbooks. Cambridge, UK: Cambridge University Press, 2015. doi: 10.1017/CBO9781139872003
  • [27] Schensted C. Longest increasing and decreasing subsequences. Canadian Journal of Mathematics 1961; 13: 179-191. doi: 10.4153/CJM-1961-015-3
  • [28] Simion R, Schmidt FW. Restricted permutations. European Journal of Combinatorics 1985; 6 (4): 383-406. doi: 10.1016/S0195-6698(85)80052-4
  • [29] Sloane NJ. The On-Line Encyclopedia of Integer Sequences, 2010. Available at https://oeis.org/.