Speaker: 

Stephen DeSalvo

Institution: 

UCLA

Time: 

Tuesday, November 15, 2016 - 11:00pm to 11:50pm

Host: 

Location: 

RH 306

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.