Asymptotic enumeration, cluster statistics, and limit laws for combinatorial structures

Ramzews, Valery Leon (2022): Asymptotic enumeration, cluster statistics, and limit laws for combinatorial structures. Dissertation, LMU München: Fakultät für Mathematik, Informatik und Statistik

Abstract

For a given combinatorial class C we study two types of combinatorial structures: the class G = Mset(C) satisfying the multiset construction, that is, every object in G is uniquely specified by a set of distinct C-objects each paired with a multiplicity from N indicating the number of occurrences of that object in the multiset (e.g. unlabelled forests are multisets of unlabelled trees). And, secondly, the class S = Set(C) containing sets of labelled C-objects, such that no label appears twice in the set and any two C-objects are treated as distinct if their set of labels is (e.g. labelled forests are sets of labelled trees). In both settings, clusters (=components) are the C-objects a (multi-)set is composed of. The focus of this work is to investigate several research questions related to these combinatorial constructions, such as asymptotic enumeration as well as limit laws for the statistics of the number of clusters and the smallest/largest cluster of random (multi-)sets. We consider the two broad cases that the counting sequence of C is either subexponential or expansive. The enumerative results of this work are concerned with the following specific setting. We want to asymptotically determine the number of (multi-)sets of total size n ∈ N and with N ∈ N clusters as n and N both grow large. Apart from being mathematically challenging, this is interesting from another perspective. Knowing the answer to this counting problem is equivalent to knowing the distribution of the number of clusters of a (multi-)set of size n drawn uniformly at random from all (multi-)sets of that size. We complete this task for multisets in the subexponential setting, and for both sets and multisets in the expansive setting for the entire range of N. In the resulting formulas we see that these settings are inherently different: whereas the number of multisets in the subexponential case is basically given by the number of C-objects of a certain size uniformly in N, the expansive case exposes a phase transition depending on N/n where the asymptotic order flips. In the subexponential case we are additionally able to say much more about the structure of multisets of size n and with N clusters. It is possible to completely describe the multiset drawn uniformly at random from all such multisets in terms of an explicit distribution. Namely, after removing the largest cluster and all clusters of smallest possible size, the remainder converges in distribution to a limit given by the well-known Boltzmann model. We baptise this phenomenon extreme condensation as virtually all components in that multiset are of smallest possible size, a bounded number of clusters is bounded and there is one huge cluster receiving almost the entire possible size. In the expansive setting such a neat description is not possible and we will only be able to make (very) educated guesses about the structure. The last batch of results is concerned with the cluster statistics from random (multi-)sets drawn uniformly at random from all (multi-)sets of size n in the expansive case, and in some instances in a slightly more general version called oscillating expansive. For that purpose, we show that a wide class related to the respective generating series is H-admissible, a property allowing us to compare different coefficients of a power series asymptotically. With this at hand, we determine all moments of the number of clusters. Further, assisted by our counting results about multisets of a particular size and number of clusters, we establish a local limit theorem for the number of clusters. Finally, we determine the scaling under which the size of the largest cluster in a uniform (multi-)set converges in distribution to the extreme value distribution and show that the size of the smallest cluster converges in distribution without scaling. Our methods are based on reformulating the problem at hand into a probability involving iid random variables via the Pólya-Boltzmann model. This gives access to probability theory’s large toolbox in the subexponential setting, where we make efficient use of existing results regarding subexponential distributions. In the counting problem of the expansive case we are initially confronted with the complex problem of determining a twodimensional Cauchy integral. By well-known results such as Chernoff bounds and estimates for Poisson variables, the aforementioned probability can then be simplified to a one-dimensional integral which is tackled via the saddle-point method. Lastly, for the problems related to cluster statistics we develop a simple and unified approach using the framework of H-admissibility and the elementary inclusion/exclusion principle.

Abstract

Für eine kombinatorische Klasse C untersuchen wir zwei kombinatorische Konstruktionen: die Klasse G = Mset(C) der Multimengen, d.h. jedes Objekt in G ist eindeutig durch die darin enthaltenen C-Objekte und deren Vielfachheit spezifiziert (z.B. sind unmarkierte Wälder Multimengen von unmarkierten Bäumen). Und, zweitens, die Klasse S = Set(C), die Mengen von markierten C-Objekten enthält, so dass keine Markierung zweimal in der Menge vorkommt und zwei beliebige C-Objekte verschieden sind, wenn ihre Markierungen verschieden sind (z.B. sind markierte Wälder Mengen von markierten Bäumen). In beiden Fällen nennen wir die C-Objekte, aus denen eine (Multi-)Menge zusammengesetzt ist, Komponenten. Der Schwerpunkt dieser Arbeit liegt auf der Untersuchung verschiedener Forschungsfragen im Zusammenhang mit diesen kombinatorischen Konstruktionen, wie z.B. die asymptotische Aufzählung sowie Grenzwertsätze für die Anzahl von Komponenten und der kleinsten/größten Komponente in zufälligen (Multi-)Mengen. Wir betrachten die beiden allgemeinen Fälle, dass die Zählfolge von C entweder subexponentiell oder expansiv ist. In den Zähl-Ergebnissen dieser Arbeit wollen wir asymptotisch die Anzahl der (Multi-)Mengen der Gesamtgröße n ∈ N und mit N ∈ N Komponenten bestimmen, wenn n und N beide groß werden. Abgesehen davon, dass dies eine mathematische Herausforderung ist, liefert uns die Antwort auf dieses Zählproblem die Verteilung der Anzahl der Komponenten einer (Multi-)Menge der Größe n, die gleichverteilt aus allen (Multi-)Mengen dieser Größe gezogen wird. Wir lösen diese Aufgabe für Multimengen im subexponentiellen Fall, und sowohl für Mengen als auch für Multimengen im expansiven Fall für alle N . In den Ergebnissen sehen wir, dass diese Fälle grundlegend unterschiedlich sind: Während die Anzahl der Multimengen im subexponentiellen Fall im Wesentlichen durch die Anzahl der C-Objekte einer bestimmten Größe gleichmäßig in N gegeben ist, zeigt sich im expansiven Fall ein von N/n abhängiger Phasenübergang, bei dem sich die asymptotische Ordnung stark verändert. Im subexponentiellen Fall untersuchen wir zusätzlich die Struktur von Multimengen der Größe n und mit N Komponenten. Es ist möglich, die Multimenge, die gleichverteilt aus allen solchen Multimengen gezogen wird, vollständig durch eine explizite Verteilung zu beschreiben. Nach dem Entfernen der größten Komponente und aller Komponenten der kleinstmöglichen Größe konvergiert die verbleibende Multimenge in Verteilung gegen einen Grenzwert, der durch das bekannte Boltzmann-Modell gegeben ist. Wir nennen dieses Phänomen extreme Kondensation, da praktisch alle Komponenten in dieser Multimenge die kleinstmögliche Größe haben, eine beschränkte Anzahl von Komponenten beschränkt ist und es eine große Komponente gibt, die fast die gesamte mögliche Masse erhält. Im expansiven Fall ist eine solche genaue Beschreibung nicht möglich, und wir werden nur Vermutungen über die Struktur anstellen können. Die abschließenden Ergebnisse befassen sich mit der Komponenten-Struktur von zufälligen (Multi-)Mengen, die gleichverteilt aus allen (Multi-)Mengen der Größe n gezogen werden, im expansiven Fall und in einigen Ausnahmen in einer etwas allgemeineren Version namens oszillierend expansiv. Wir zeigen, dass eine breite Klasse an Erzeugendenfunktionen H-zulässig ist, was eine Eigenschaft ist, die es erlaubt, verschiedene Koeffizienten einer Potenzreihe asymptotisch zu vergleichen. Auf dieser Grundlage bestimmen wir die Skalierung, unter der die Größe der größten Komponente gegen die Extremwertverteilung konvergiert und zeigen, dass die Größe der kleinsten Komponente in Verteilung ohne Skalierung konvergiert. Schließlich bestimmen wir alle Momente der Anzahl der Komponenten und stellen mithilfe unserer Zählergebnisse einen lokalen Grenzwertsatz für die Anzahl der Komponenten auf. Unsere Methoden beruhen auf der Umformulierung des jeweiligen Problems in eine Wahrscheinlichkeit über unabhängige gleichverteilte Zufallsvariablen über das Pólya-Boltzmann-Modell. Dies ermöglicht den Zugriff auf die vielseitigen Werkzeuge der Wahrscheinlichkeitstheorie im subexponentiellen Fall, in dem wir die bestehenden Ergebnisse zu subexponentiellen Verteilungen effizient nutzen. Bei dem Zählproblem im expansiven Fall sind wir zunächst mit der komplexen Aufgabe der Bestimmung eines zweidimensionalen Cauchy-Integrals konfrontiert. Durch bekannte Ergebnisse wie Chernoff-Grenzen und Abschätzungen für Poisson-Variablen lässt sich die oben genannte Wahrscheinlichkeit dann auf ein eindimensionales Integral vereinfachen, das mit der Sattelpunktmethode gelöst wird. Abschließend entwickeln wir für die Probleme im Zusammenhang mit der Komponenten-Struktur einen einfachen und einheitlichen Ansatz unter Verwendung der H-Zulässigkeit und des elementaren Inklusions-/Exklusionsprinzips.

• Dokumententyp: Dissertationen (Dissertation, LMU München)
• Themengebiete: 500 Naturwissenschaften und Mathematik ; 500 Naturwissenschaften und Mathematik > 510 Mathematik
• Fakultäten: Fakultät für Mathematik, Informatik und Statistik
• Sprache der Hochschulschrift: Englisch
• Datum der mündlichen Prüfung: 27. September 2022
• 1. Bericht­erstatter:in: Panagiotou, Konstantinos