Longest increasing subsequences of random colored permutations

1999/01/31 by Alexei Borodin, Borodin, Alexei
Mathematics · #05A05 #60F99 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:05A05 #msc:60F99

paper · pdf · doi:10.48550/arxiv.math/9902001

AMSTeX, 11 pages

arxiv created 1999/02/02 · arxiv updated 2009/11/30

Abstract

We compute the limit distribution for (centered and scaled) length of the longest increasing subsequence of random colored permutations. The limit distribution function is a power of that for usual random permutations computed recently by Baik, Deift, and Johansson (math.CO/9810105). In two--colored case our method provides a different proof of a similar result by Tracy and Widom about longest increasing subsequences of signed permutations (math.CO/9811154). Our main idea is to reduce the `colored' problem to the case of usual random permutations using certain combinatorial results and elementary probabilistic arguments.

Related

• Asymptotics of the Longest Increasing Subsequence in Random Permutations
• Longest increasing subsequences in pattern-restricted permutations
• On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation
• Longest subsequence for certain repeated up/down patterns in random permutations avoiding a pattern of length three
• On the Limiting Distribution for the Longest Alternating Sequence in a Random Permutation