## Topics in Combinatorics and Random Matrix Theory

Loading...

##### Date

2009-09-27T19:09:15Z

##### Authors

Novak, Jonathan

##### Keyword

Combinatorics , Random Matrices

##### Abstract

Motivated by the longest increasing subsequence problem, we examine sundry
topics at the interface of enumerative/algebraic combinatorics and random matrix theory.
We begin with an expository account of the increasing subsequence problem,
contextualizing it as an ``exactly solvable'' Ramsey-type problem and introducing
the RSK correspondence. New proofs and generalizations
of some of the key results in increasing subsequence theory are given. These include Regev's single
scaling limit, Gessel's Toeplitz determinant identity, and Rains' integral representation. The double scaling limit (Baik-Deift-Johansson theorem) is briefly described, although we have no
new results in that direction.
Following up on the appearance of determinantal generating functions in increasing subsequence type problems, we are led to a connection between combinatorics and the ensemble of truncated random
unitary matrices, which we describe in terms of Fisher's random-turns vicious walker model
from statistical mechanics. We prove that the moment generating function of the trace
of a truncated random unitary matrix is the grand canonical partition function for Fisher's
random-turns model with reunions.
Finally, we consider unitary matrix integrals of a very general type, namely the ``correlation functions'' of entries of Haar-distributed random matrices. We show
that these expand perturbatively as generating functions for class multiplicities in symmetric functions of Jucys-Murphy elements, thus addressing a problem originally raised by De Wit and t'Hooft and
recently resurrected by Collins. We argue that this expansion is the CUE counterpart of genus expansion.