Part Sizes of Smooth Supercritical Compositional Structures
- 9 July 2014
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 23 (5) , 686-716
Abstract
We define the notion of smooth supercritical compositional structures. Two well-known examples are compositions and graphs of given genus. The ‘parts’ of a graph are the subgraphs that are maximal trees. We show that large part sizes have asymptotically geometric distributions. This leads to asymptotically independent Poisson variables for numbers of various large parts. In many cases this leads to asymptotic formulas for the probability of being gap-free and for the expected values of the largest part sizes, number of distinct parts and number of parts of multiplicityk.Keywords
This publication has 18 references indexed in Scilit:
- Asymptotic enumeration and limit laws for graphs of fixed genusJournal of Combinatorial Theory, Series A, 2011
- Gap-free compositions and gap-free samples of geometric random variablesDiscrete Mathematics, 2005
- Lattice animals and heaps of dimersDiscrete Mathematics, 2002
- The Distribution of the Maximum Vertex Degree in Random Planar MapsJournal of Combinatorial Theory, Series A, 2000
- Largest component in random combinatorial structuresDiscrete Mathematics, 1998
- Asymptotic results for the number of multidimensional partitions of an integer and directed compact lattice animalsJournal of Physics A: General Physics, 1997
- A Bivariate Asymptotic Expansion of Coefficients of Powers of Generating FunctionsEuropean Journal of Combinatorics, 1994
- Singularity Analysis of Generating FunctionsSIAM Journal on Discrete Mathematics, 1990
- Convex n-ominoesDiscrete Mathematics, 1974
- Asymptotic bounds for the number of convex n-ominoesDiscrete Mathematics, 1974