# Jerusalem Mathematics Colloquium

Thursday, 17th January 2008, 4:00 pm

Mathematics Building, Lecture Hall 2

##

Ross Pinsky

(Technion)

"Increasing subsequences in random permutations"

** Abstract: ** Let *S_n* be the symmetric group of
permutations on *n* elements and let *U_n* denote the
uniform measure on *S_n* so that *\sigma\in S_n* may be
thought of as a random permutation. For *k <= n*, let
*Z_{n,k}=Z_{n,k)(\sigma)* denote the *number* of
increasing subsequences of length *k* in a random permutation
*\sigma* in *S_n*. In this talk we will be interested in the
behavior of *Z_{n,k_n}*, where typically *k_n=n^l*.

Let *EZ_{n,k}* denote the expected value of *Z_{n,k}*.
We say that the weak law of large numbers (WLLN) holds for *Z_{n,k_n)* if

*lim_{n->\infty} Z_{n,k_n}/EZ_{n,k_n} = 1* in probability
Presumably, there exists a critical exponent *l_0* such that
WLLN holds for *Z_{n,n^1}* if *l < l_0* and does not hold if
*l > l_0*. We prove that WLLN holds for *l < 2/5* and does not
hold for *l > 4/9*. The proof of the second part uses in a
crucial way the recent celebrated result of Baik, Dieft and
Johansson (1999) on the statistics of the longest increasing
subsequence in a random permutation.

We also show that the above problem is equivalent to a more
tangible one concerning the possibility of detecting a certain
tampering in a deck of cards.

Light refreshments
will be served in the faculty lounge at 3:30.

List of talks, 2007-08

Archive of talks