Asymptotics of Smallest Component Sizes in Decomposable Combinatorial Structures of Alg-Log Type

Abstract : A decomposable combinatorial structure consists of simpler objects called components which by thems elves cannot be further decomposed. We focus on the multi-set construction where the component generating function C(z) is of alg-log type, that is, C(z) behaves like c + d(1 -z/rho)(alpha) (ln1/1-z/rho)(beta) (1 + o(1)) when z is near the dominant singularity rho. We provide asymptotic results about the size of thes mallest 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, has 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 patterns is known. We extend our results to include certain type of integers partitions. partitions
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (2), pp.197-222
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990464
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:37:47
Dernière modification le : mercredi 20 décembre 2017 - 14:48:02
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:19:14

Fichier

1307-5007-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990464, version 1

Collections

Citation

Lihua Dong, Zhicheng Gao, Daniel Panario, Bruce Richmond. Asymptotics of Smallest Component Sizes in Decomposable Combinatorial Structures of Alg-Log Type. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (2), pp.197-222. 〈hal-00990464〉

Partager

Métriques

Consultations de la notice

123

Téléchargements de fichiers

178