**Abstract**: We derive limit laws for random combinatorial structures using singularity analysis of generating functions. We begin with a study of the Boltzmann samplers of Flajolet and collaborators, a useful method for generating large discrete structures at random which is useful both for providing intuition and conjecture and as a possible proof technique. We then apply generating functions and Boltzmann samplers to three main classes of objects: permutations with weighted cycles, involutions, and integer partitions. Random permutations in which each cycle carries a multiplicative weight σ have probability (1-γ)

^{σ}of having a random element be in a cycle of length longer than γn; this limit law also holds for cycles carrying multiplicative weights depending on their length and averaging σ. Such permutations have number of cycles asymptotically normally distributed with mean and variance ~ σ log n. For permutations with weights σ

_{k}= 1/k or σ

_{k}= k, other limit laws are found; the prior have finitely many cycles in expectation, the latter around √n. Compositions of uniformly chosen involutions of [n], on the other hand, have about √n cycles on average. These can be modeled as modified 2-regular graphs. A composition of two random involutions in S

_{n}typically has about n

^{1/2}cycles, characteristically of length n

^{1/2}. The number of factorizations of a random permutation into two involutions appears to be asymptotically lognormally distributed, which we prove for a closely related probabilistic model. We also consider connections to pattern avoidance, in particular to the distribution of the number of inversions in involutions. Last, we consider integer partitions. Various results on the shape of random partitions are simple to prove in the Boltzmann model. We give a (conjecturally tight) asymptotic bound on the number of partitions p

_{M}(n) in which all part multiplicities lie in some fixed set n, and explore when that asymptotic form satisfies log p

_{M}(n) ~ π√(Cn) for rational C. Finally we give probabilistic interpretations of various pairs of partition identities and study the Boltzmann model of a family of random objects interpolating between partitions and overpartitions.

## 5 comments:

Congratulations!

Where are you headed next?

Boris, I don't know where I'm heading next. It's a tough job market.

Congratulations!

Congrats! The job situation in industry is bad enough I'm considering going back and completing my PhD (in physics).

Now that you have time on your hands, a reviewer at Phys. Lett. B implied I couldn't put a fairly simple matrix exponential in closed form:

Let H0 be the Hermitian 3x3 matrices whose rows and columns all sum to zero. There are four real degrees of freedom left. Write out exp(i H0) in closed form. Thus one parmaterizes the Lie group with the complete solution for all the 1-parameter Lie subgroups.

I found a solution; but the interesting question is the extension to larger matrices.

Carl, this isn't the sort of thing I'm particularly good at. If you want an answer to the general case, MathOverflow might be a good place to post.

Post a Comment