Asymptotic enumeration and limit laws for multisets: The subexponential case

Étant donnée une classe combinatoire C, nous étudions la classe G = Mset(C) satisfaisant la construction multiset, c’est-à-dire que tout objet dans G est déterminé de manière unique par un ensemble d’objets C appariés avec leurs multiplicités. Par exemple, Mset(N) est (isomorphe à) la classe des partitions de nombres entiers positifs, un cas important et bien étudié. La construction multiset apparaît naturellement dans l’étude des objets non étiquetés, par exemple les graphes ou diverses structures liées aux partitions de nombres. Notre résultat principal établit la taille asymptotique de l’ensemble Gn,N qui contient tous les multisets dans G ayant une taille n et étant composés de N objets de C, quand n et N tendent vers l’infini et lorsque la suite de comptage de C est gouvernée par une croissance sous-exponentielle. De plus, nous étudions la loi des composantes des objets aléatoires de Gn,N et nous découvrons un phénomène que nous baptisons condensation extrême : en enlevant la plus grande composante ainsi que toutes les composantes de la plus petite taille possible, on se retrouve avec un objet dont la loi converge quand n,N→∞. On récupère également la loi de l’objet limite. De plus, et de manière assez surprenante, en contraste saisissant avec les résultats analogues pour les objets étiquetés, les résultats obtenus ici sont vrais uniformément en N.