Speaker:
Institution:
Time:
Host:
Location:
We present a general framework for approximating 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$, $\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.