Variations on Hammersley’s interacting particle process

Arda Atalik; H. S. Melihcan Erol; Go¨khan Yıldırım; Mustafa Yilmaz

doi:10.47443/dml.2021.0049

Author(s)

Arda Atalik Department of Electrical and Electronics Engineering, Bilkent University,Ankara, TR 06800,Turkey

H. S. Melihcan Erol Electrical Engineering & Computer Science,MIT, Cambridge, MA 02139,USA

Go¨khan Yıldırım Department of Mathematics, Bilkent University,Ankara, TR 06800,Turkey

Mustafa Yilmaz Department of Electrical and Electronics Engineering, Bilkent University,Ankara, TR 06800,Turkey

Abstract

The longest increasing subsequence problem for permutations has been studied extensively in the last fifty years. The interpretation of the longest increasing subsequence as the longest 21-avoiding subsequence in the context of permutation patterns leads to many interesting research directions. We introduce and study the statistical properties of Hammersleytype interacting particle processes related to these generalizations and explore the finer structures of their distributions. We also propose three different interacting particle systems in the plane analogous to the Hammersley process in one dimension and obtain estimates for the asymptotic orders of the mean and variance of the number of particles in the systems.

Publication Details

Page(s) 34-39

DOI 10.47443/dml.2021.0049

Published Journal: Discrete Mathematics Letters, Volume: 7, Issue: 0, Year: 2021

Request the full text from PASTIC

Keywords

permutation patterns, longest increasing subsequences, Hammersley's process

References

Albert M. H. .2007 .On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation. Random Struct. Algorithms, 31 : 227-238.

Aldous D.,Diaconis P. .1999 .Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull. Amer. Math. Soc, 36 : 413-433.

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.,Rains E. M. .2001 .The asymptotics of monotone subsequences of involutions. , 109 : 205-281.

I. Corwin .2018 .increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem” by David Aldous and Persi Diaconis. Bull. Amer. Math. Soc, 55 : 363-374.

Greene C. .1974 .An extension of Schensteds theorem. , 14 : 254-265.

Hammersley J. M.,M. Le Cam J.,Neyman E. L.,Scott E. L. .1972 .A few seedlings of research. Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, 1 : 345-394.

Johansson K. .1998 .The longest increasing subsequence in a random permutation and a unitary random matrix model. Math. Res. Lett. 5, : 68-82.

Krabbe P.,Schawe H.,Hartmann A. K. .2020 .Number of longest increasing subsequences. Phys. Rev. E, 101 : 062109.

Makey G.,Galioglu S.,Ghaffari R.,Engin E. D.,Yıldırım G.,¨. Yavuz O,Nizam U¨ . S.,¨ . Akbulut O,O O,Demir H. V.,¨. Ilday F. O,Ilday S. .2020 .Universality of dissipative self-assembly from quantum dots to human cells. Nature Phys, 16 : 795-801.

Mansour T. . .Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences. Adv. Appl, 116(2020) : 102002.

Marcus A. .2004 .Excluded permutation matrices and the Stanley-Wilf conjecture. J. Combin. Theory Ser. A, 107 : 153-160.

Odlyzko A. .2000 .On longest increasing subsequences in random permutations. , 251 : 439-452.

Romik D. .2015 .. The Surprising Mathematics of Longest Increasing Subsequences, : .

Schensted C. .1961 .Longest increasing and decreasing subsequences, Canad. , 13 : 179-191.

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.

Ulam S. M.,McGraw-Hill S. M. .1961 .Monte Carlo calculations in problems of mathematical physics. Modern Mathematics for the Engineers, : 261-281.