Discrete Mathematics & Theoretical Computer Science, Vol 12, No 2 (2010)

Font Size:  Small  Medium  Large

Asymptotics of smallest component sizes in decomposable structures of alg-log type

Li Dong, Zhicheng Gao, Daniel Panario, Bruce Richmond


A decomposable combinatorial structure consists of simpler objects called components which by themselves can not be further decomposed. We focus on the case when the component generating function C(z) is of alg-log type, that is, C(z) behaves like c + d(1-z/\rho)^\alpha ( \log (1/(1-z/\rho )) ) ^\beta (1+o(1)) when z is near the dominant singularity . We provide asymptotic results about the size of the smallest components in random combinatorial structures for the cases 0 < \alpha < 1 and any \beta, and \alpha < 0 and \beta = 0. The particular case \alpha = 0 and \beta = 1, the so-called exp-log class, have been treated in previous papers. We also provide similar asymptotic estimates for combinatorial objects with a restricted pattern, that is, when part of its factorization pattern is known. We extend our results to include certain type of integers partitions.

Full Text: PDF PostScript