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.

Article Number