Longest Increasing Subsequences of Random Colored Permutations

Alexei Borodin


We compute the limit distribution for the (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 the two–colored case our method provides a different proof of a similar result by Tracy and Widom about the 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.

Full Text: PDF