The longest increasing subsequence in involutions avoiding 3412 and another pattern

Mansour, Toufik; Rastegar, Reza; Roitershtein, Alexander; Yıldırım, Gökhan

doi:10.2478/puma-2022-0032

Abstract

In this note, we study the mean length of the longest increasing subsequence of a uniformly sampled involution that avoids the pattern 3412 and another pattern.

References

[1] J. Baik, P. Deift and T. Suidan, Combinatorics and Random Matrix Theory, AMS, 2016.
Search in Google Scholar Back to article
[2] J. Baik and E. M. Rains, The asymptotics of monotone subsequences of involutions, Duke Math. J., 109 (2001) 205–281.10.1215/S0012-7094-01-10921-6
Search in Google Scholar Back to article
[3] M. Bòna, C. Homberger, J. Pantone and V. Vatter, Pattern-avoiding involutions: exact and asymptotic enumeration, Australas. J. Combin., 64 (2016) 88–119.
Search in Google Scholar Back to article
[4] E. Deutsch, A. J. Hildebrand and H. S. Wilf, Longest increasing subsequences in pattern-restricted permutations, Electron. J. Combin., 9 (2002-2003) #R12.10.37236/1684
Search in Google Scholar Back to article
[5] E. S. Egge, Restricted 3412-avoiding involutions, continued fractions, and Chebyshev polynomials, Adv. in Appl. Math., 33 (2004) 451–475.10.1016/j.aam.2003.09.006
Search in Google Scholar Back to article
[6] E. S. Egge and T. Mansour, Bivariate generating functions for involutions restricted by 3412, Adv. in Appl. Math., 36 (2006) 118–137.10.1016/j.aam.2005.01.005
Search in Google Scholar Back to article
[7] O. Guibert, Combinatoire des permutations à motifs exclus en liaison avec mots, cartes planaires et tableaux de Young, PhD thesis, Université Bordeaux I, 1995.
Search in Google Scholar Back to article
[8] S. Kitaev, Patterns in permutations and words, Monographs in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg, 2011.10.1007/978-3-642-17333-2
Search in Google Scholar Back to article
[9] M. Kiwi, A concentration bound for the longest increasing subsequence of a randomly chosen involution, Discrete Appl. Math., 154 (2006) 1816–1823.10.1016/j.dam.2006.03.025
Search in Google Scholar Back to article
[10] T. Mansour and G. Yıldırım, Longest increasing subsequences in involutions avoiding patterns of length three, Turkish J. Math., 43 (2019) 2183–2192.10.3906/mat-1901-86
Search in Google Scholar Back to article
[11] T. Mansour and G. Yıldırım, Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences, Adv. in Appl. Math., 116 (2020) 1–17.10.1016/j.aam.2020.102002
Search in Google Scholar Back to article
[12] A. Reifegerste, On the diagram of 132-avoiding permutations, European J. Combin., 24 (2003) 759–776.10.1016/S0195-6698(03)00065-9
Search in Google Scholar Back to article
[13] T. Rivlin, Chebyshev polynomials. From approximation theory to algebra and number theory, John Wiley, New York, 1990.
Search in Google Scholar Back to article
[14] D. Romik, The Surprising Mathematics of Longest Increasing Subsequences, Cambridge University Press, 2015.10.1017/CBO9781139872003
Search in Google Scholar Back to article
[15] N. J. Sloane, The On-Line Encyclopedia of Integer Sequences, at http://oeis.org, 2010.
Search in Google Scholar Back to article
[16] R. P. Stanley, Increasing and decreasing subsequences and their variants, International Congress of Mathematicians, Vol. I, Eur. Math. Soc., 2007, pp.545–579.10.4171/022-1/21
Search in Google Scholar Back to article
[17] R. P. Stanley, A survey of alternating permutations, In Combinatorics and Graphs, Contemp. Math., 531, Amer. Math. Soc., 2010, pp. 165–196.10.1090/conm/531/10466
Search in Google Scholar Back to article

The longest increasing subsequence in involutions avoiding 3412 and another pattern

Abstract

Paradigm

My account