Moderate deviations for longest increasing subsequences: The upper tail

We derive the upper-tail moderate deviations for the length of a longest in creasing subsequence in a random permutation. This concerns the regime betw een the upper-tail large-deviation regime and the central limit regime. Our proof uses a formula to describe the relevant probabilities in terms of th e solution of the rank 2 Riemann-Hilbert problem (RHP); this formula was in vented by Baik, Deift, and Johansson [3] to find the central limit asymptot ics of the same quantities. In contrast to the work of these authors, who a pply a third-order (nonstandard) steepest-descent approximation at an infle ction point of the transition matrix elements of the RHP, our approach is b ased on a (more classical) second-order (Gaussian) saddle point approximati on at the stationary points of the transition function matrix elements. (C) 2001 John Wiley & Sons, Inc.