Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 288 - Probability Seminar

Stephen DeSalvo

UCLA

Poisson approximation of combinatorial assemblies with low rank

Abstract:

We present a general framework for approximating the component structure of random combinatorial assemblies when both the size $n$ and the number of components $k$ is specified. The approach is an extension of the usual saddle point approximation, and we demonstrate near-universal behavior when the rank $r := n-k$ is small relative to $n$ (hence the name `low rank’). In particular, for $\ell = 1, 2, \ldots$, when $r \asymp n^\alpha$, for $\alpha \in \left(\frac{\ell}{\ell+1}, \frac{\ell+1}{\ell+2}\right)$, the size~$L_1$ of the largest component converges in probability to $\ell+2$. When $r \sim t\, n^{\ell/(\ell+1)}$ for any $t>0$ and any positive integer $\ell$, we have $P(L_1 \in \{\ell+1, \ell+2\}) \to 1$. We also obtain as a corollary bounds on the number of such combinatorial assemblies, which in the special case of set partitions fills in a countable number of gaps in the asymptotic analysis of Louchard for Stirling numbers of the second kind. This is joint work with Richard Arratia

Host: Bruce Driver

November 10, 2016

9:00 AM

AP&M 6402

****************************