CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Asymptotic Enumeration

AUBREY BLECHER, University of Witwatersrand, Johannesburg, South Africa
Compositions of positive integers n viewed as alternating sequences of increasing/decreasing partitions.  [PDF]

Decompositions of positive integers into partitions or compositions is well studied. Here we consider arbitrary compositions of n and split these up into blocks where each block is either increasing or decreasing. For example the composition 1432123 of 16 may be split up into partitions (143)(21)(23). How this is done depends on precisely how the blocks are defined. Here we find the expected value for the number of such blocks as n tends to infinity.

Asymptotic analysis of walks with small steps in the quarter plane.  [PDF]

The enumeration of walks in the quarter plane is an elegant problem. Much work has been done attempting to classify walks with small steps. At the coarsest level there are two families; asymptotic estimates for one family are known but not proved, and non-holonomy of the generating functions for walks in the other family is conjectured. Proving these conjectures is a priority: we survey recent results while outlining a strategy for achieving a rigorous classification.

DAVID LAFERRIÈRE, Carleton University
Asymptotics of Decomposable Combinatorial Structures with Components of Alg-Log Type  [PDF]

\emph{Decomposable combinatorial structures} are structures constructed from smaller structures called \emph{components} which cannot be further decomposed. We assume that the component generating function $C(z)$ is of alg-log type \emph{i.e.}, $C(z)$ behaves like \begin{align*} (1-z/\rho)^{-\alpha}\log\left(\frac{1}{1-z/\rho}\right)^{\beta} \end{align*} near its dominant singularity $\rho$. We determine asymptotic enumerative results in the case $\alpha =0, \beta > 0$ and also examine objects whose components are subject to size restrictions. This work extends results of Dong, Gao, Panario and Richmond.

CRISTIANE M. SATO, University of Waterloo
Asymptotic enumeration of sparse 2-connected graphs  [PDF]

We determine an asymptotic formula for the number of labelled $2$-connected (simple) graphs on $n$ vertices and $m$ edges, provided that $m-n\to\infty$ and $m=O(n\log n)$ as $n\to\infty$. This is the entire range of $m$ not covered by previous results and solves a problem proposed by Wright from 1983. This talk is based on joint work with Graeme Kemkes and Nicholas Wormald.

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria