Asymptotic enumeration and limit laws for multisets: the subexponential case

DOI10.1214/22-AIHP1324arXiv2007.08274OpenAlexW3042703614MaRDI QIDQ6127310FDOQ6127310

Leon Ramzews, Konstantinos Panagiotou

Publication date: 12 April 2024

Published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Abstract: For a given combinatorial class $mathcalC$ we study the class $mathcalG=mathrmMSET(mathcalC)$ satisfying the multiset construction, that is, any object in $mathcalG$ is uniquely determined by a set of $mathcalC$-objects paired with their multiplicities. For example, $mathrmMSET(mathbbN)$ is (isomorphic to) the class of number partitions of positive integers, a prominent and well-studied case. The multiset construction appears naturally in the study of unlabelled objects, for example graphs or various structures related to number partitions. Our main result establishes the asymptotic size of the set $mathcal{G}_{n,N}$ that contains all multisets in $mathcalG$ having size $n$ and being comprised of $N$ objects from $mathcalC$, as $n$ emph{and} $N$ tend to infinity and when the counting sequence of $mathcalC$ is governed by subexponential growth; this is a particularly important setting in combinatorial applications. Moreover, we study the component distribution of random objects from $mathcal{G}_{n,N}$ and we discover a phenomenon that we baptise emph{extreme condensation}: taking away the largest component as well as all the components of the smallest possible size, we are left with an object which converges in distribution as $n,Noinfty$. The distribution of the limiting object is also retrieved. Moreover and rather surprisingly, in stark contrast to analogous results for labelled objects, the results here hold uniformly in $N$.

Full work available at URL: https://arxiv.org/abs/2007.08274

zbMATH Keywords

asymptotic enumerationcondensationlimit theoremBenjamini-Schramm convergencemultisetsweighted integer partitions

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Partitions of sets (05A18) Combinatorial probability (60C05) Asymptotic enumeration (05A16) Enumeration in graph theory (05C30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Recurrence of distributional limits of finite planar graphs
• Asymptotic Study of Subcritical Graph Classes
• Asymptotische Aussagen über Partitionen
• An Introduction to Heavy-Tailed and Subexponential Distributions
• Statistical mechanics of combinatorial partitions, and their limit shapes
• Logarithmic combinatorial structures: A probabilistic approach
• The maximum degree of random planar graphs
• Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
• The number of trees
• The distribution of the number of summands in the partitions of a positive integer
• Vertices of degree k in random unlabeled trees
• The continuum random tree is the scaling limit of unlabeled unrooted trees
• Scaling limits of random graphs from subcritical classes
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Boltzmann Sampling of Unlabelled Structures
• Maximal biconnected subgraphs of random planar graphs
• On properties of random dissections and triangulations
• Random combinatorial structures: the convergent case
• Limit theorems for the number of summands in integer partitions
• Meinardus' theorem on weighted partitions: Extensions and a probabilistic proof
• On the maximum size of a tree in a random unlabelled unrooted forest
• Components of Random Forests
• Random non-crossing plane configurations: a conditioned Galton-Watson tree approach
• Partition Asymptotics from Recursion Equations
• ASYMPTOTIC ENUMERATION AND LOGICAL LIMIT LAWS FOR EXPANSIVE MULTISETS AND SELECTIONS
• Developments in the Khintchine-Meinardus probabilistic method for asymptotic enumeration
• Asymptotics for the probability of connectedness and the distribution of number of components
• On the number of trees in a random forest
• Scaling limits of random Pólya trees
• Limit theorems for the number of parts in a random weighted partition
• A probabilistic approach to block sizes in random maps
• Random enriched trees with applications to random graphs
• Gibbs partitions: The convergent case
• The Size of the Largest Part of Random Weighted Partitions of Large Integers
• The largest tree in certain models of random forests
• Distribution of integer partitions with large number of summands
• Graph limits of random graphs from a subset of connected k‐trees
• Unlabelled Gibbs partitions
• Asymptotic Enumeration of Graph Classes with Many Components

This page was built for publication: Asymptotic enumeration and limit laws for multisets: the subexponential case

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6127310)