In the last few decades, combinatorial families exhibiting noncrossing or cluster phenomena have proven useful in understanding and connecting mathematical objects arising in seemingly unrelated branches of mathematics and theoretical physics. These phenomena can be modeled in the context of Coxeter groups and play an important role in algebraic combinatorics. In finite type, such families are enumerated by generalized Catalan numbers. In this thesis, we consider the extension of this theory to parabolic quotients of Coxeter groups. We outline the history, present the basic definitions and constructions, and provide a number of conjectures and research challenges arising in this context. We then solve these questions in linear type A and exhibit surprising connections of this theory to certain Hopf algebras and to the theory of diagonal harmonics. We end this thesis by proposing related directions for future research.:Chapter 0. Prologue Noncrossing partitions Triangulations Stack-sortable permutations Dyck paths Chapter 1. Preliminaries 1.1. Posets and lattices 1.1.1. A notion of order 1.1.2. Diagrams and labelings 1.1.3. Duality and multichains 1.1.4. Zeta polynomial and Möbius function 1.1.5. Lattices 1.1.6. Distributivity 1.1.7. Semidistributivity 1.1.8. Trimness 1.1.9. Congruence-uniformity 1.1.10. The core label order 1.2. Coxeter groups 1.2.1. Coxeter systems 1.2.2. The geometric representation 1.2.3. Ordering a Coxeter group 1.2.4. Orienting a Coxeter group Chapter 2. Cataland 2.1. Catalan numbers 2.2. Aligned elements 2.2.1. Cambrian lattices 2.3. Noncrossing partitions 2.4. Clusters 2.5. Nonnesting partitions 2.5.1. v-Tamari lattices 2.6. Chapoton Triangles Chapter 3. Parabolic Cataland: Origins 3.1. Parabolic quotients of Coxeter groups 3.2. Parabolic aligned elements 3.3. Parabolic noncrossing partitions 3.4. Parabolic clusters 3.5. Parabolic nonnesting partitions 3.6. Parabolic Chapoton triangles Chapter 4. Parabolic Cataland: Linear type A 4.1. Definitions 4.1.1. Parabolic quotients of the symmetric group 4.1.2. The longest α-permutation 4.1.3. The root poset of S_α and α-Dyck paths 4.1.4. c-clusters for S_α 4.1.5. c-aligned elements for S_α 4.1.6. c-noncrossing partitions for S_α 4.1.7. α-trees 4.2. Bijections 4.2.1. Noncrossing α-partitions and (α, 231)-avoiding permutations 4.2.2. Noncrossing α-partitions and α-Dyck paths 4.2.3. α-trees and (α, 231)-avoiding permutations 4.2.4. α-trees and noncrossing α-partitions 4.2.5. α-trees and α-Dyck paths 4.3. Posets 4.3.1. The weak order on S_α(231) 4.3.2. The rotation order on Dyck(α) 4.3.3. The core label order of Tam(α) 4.4. Chapoton triangles 4.5. Applications 4.5.1. A Hopf algebra on pipe dreams 4.5.2. A zeta map from diagonal harmonics Chapter 5. Epilogue 5.1. Arbitrary type A 5.2. Linear type B 5.3. (α, m)-Tamari lattices 5.4. Parabolic multiclusters Chapter A. Data A.1. Parabolic Catalan numbers in rank 3 A.2. Parabolic Catalan numbers in rank 4 A.3. Answers to Research Challenge 3.3.4 in rank 4 / Kombinatorische Familien, die nichtkreuzende oder Cluster-Phänomene aufweisen, haben sich in den letzten Jahrzehnten als wichtiges Werkzeug für das Verständnis und die Verbindung mathematischer Objekte aus scheinbar unverbundenen Teilgebieten der Mathematik und der theoretischen Physik erwiesen. Diese Phänomene können im Zusammenhang mit Coxeter-Gruppen modelliert werden, und spielen eine wichtige Rolle in der algebraischen Kombinatorik. Im endlichen Fall werden derartige kombinatorische Familien von verallgemeinerten Catalanzahlen abgezählt. In dieser Schrift betrachten wir eine Erweiterung dieser Theorie auf parabolische Quotienten von Coxeter-Gruppen. Wir stellen die historische Entwicklung und die grundlegenden Definitionen und Konstruktionen dar und präsentieren eine Reihe von Vermutungen und Forschungsfragen, die in diesem Zusammenhang entstehen. Anschließend lösen wir diese Fragen im sogenannten 'linearen Typ A' und decken überraschende Zusammenhänge dieser Theorie zu bestimmten Hopf-Algebren und zur Theorie der diagonal-harmonischen Polynome auf. Am Ende dieser Schrift schlagen wir weiterführende Forschungsrichtungen vor.:Chapter 0. Prologue Noncrossing partitions Triangulations Stack-sortable permutations Dyck paths Chapter 1. Preliminaries 1.1. Posets and lattices 1.1.1. A notion of order 1.1.2. Diagrams and labelings 1.1.3. Duality and multichains 1.1.4. Zeta polynomial and Möbius function 1.1.5. Lattices 1.1.6. Distributivity 1.1.7. Semidistributivity 1.1.8. Trimness 1.1.9. Congruence-uniformity 1.1.10. The core label order 1.2. Coxeter groups 1.2.1. Coxeter systems 1.2.2. The geometric representation 1.2.3. Ordering a Coxeter group 1.2.4. Orienting a Coxeter group Chapter 2. Cataland 2.1. Catalan numbers 2.2. Aligned elements 2.2.1. Cambrian lattices 2.3. Noncrossing partitions 2.4. Clusters 2.5. Nonnesting partitions 2.5.1. v-Tamari lattices 2.6. Chapoton Triangles Chapter 3. Parabolic Cataland: Origins 3.1. Parabolic quotients of Coxeter groups 3.2. Parabolic aligned elements 3.3. Parabolic noncrossing partitions 3.4. Parabolic clusters 3.5. Parabolic nonnesting partitions 3.6. Parabolic Chapoton triangles Chapter 4. Parabolic Cataland: Linear type A 4.1. Definitions 4.1.1. Parabolic quotients of the symmetric group 4.1.2. The longest α-permutation 4.1.3. The root poset of S_α and α-Dyck paths 4.1.4. c-clusters for S_α 4.1.5. c-aligned elements for S_α 4.1.6. c-noncrossing partitions for S_α 4.1.7. α-trees 4.2. Bijections 4.2.1. Noncrossing α-partitions and (α, 231)-avoiding permutations 4.2.2. Noncrossing α-partitions and α-Dyck paths 4.2.3. α-trees and (α, 231)-avoiding permutations 4.2.4. α-trees and noncrossing α-partitions 4.2.5. α-trees and α-Dyck paths 4.3. Posets 4.3.1. The weak order on S_α(231) 4.3.2. The rotation order on Dyck(α) 4.3.3. The core label order of Tam(α) 4.4. Chapoton triangles 4.5. Applications 4.5.1. A Hopf algebra on pipe dreams 4.5.2. A zeta map from diagonal harmonics Chapter 5. Epilogue 5.1. Arbitrary type A 5.2. Linear type B 5.3. (α, m)-Tamari lattices 5.4. Parabolic multiclusters Chapter A. Data A.1. Parabolic Catalan numbers in rank 3 A.2. Parabolic Catalan numbers in rank 4 A.3. Answers to Research Challenge 3.3.4 in rank 4

Die vorliegende Dissertation widmet sich der theoretischen Untersuchung zweier neuer Algorithmen für Clustering und Community Detection: AWC (Adaptive Weights Clustering) und AWCD (Adaptive Weights Community Detection). Ein zentraler Aspekt sind dabei die Raten der Konsistenz. Bei der Betrachtung von AWC steht die Tiefe Lücke zwischen den Clustern, also die relative Differenz der jeweiligen Dichten, im Vordergrund. Bis auf logarithmische Faktoren ist die erreichte Konsistenzrate optimal. Dies erweitert die niedrigdimensionalen Ergebnisse von Efimov, Adamyan and Spokoiny (2019) auf das Mannigfaltigkeitenmodell und berücksichtigt darüber hinaus viel allgemeinere Bedingungen an die zugrunde liegende Dichte und die Form der Cluster. Insbesondere wird der Fall betrachtet, bei dem zwei Punkte des gleichen Clusters nahe an dessen Rand liegen. Zudem werden Ergebnisse für endliche Stichproben und die optimale Wahl des zentralen Parameters λ diskutiert. Bei der Untersuchung von AWCD steht die Asymptotik der Differenz θ − ρ zwischen den beiden Bernoulli Parametern eines symmetrischen stochastischen Blockmodells im Mittelpunkt. Es stellt sich heraus, dass das Gebiet der starken Konsistenz bei weitem nicht optimal ist. Es werden jedoch zwei Modifikationen des Algorithmus vorgeschlagen: Zum einen kann der Bias der beteiligten Schätzer minimiert werden. Zum anderen schlagen wir vor, die Größe der initialen Schätzung der Struktur der Gruppen zu erhöhen, indem auch längere Pfade mit berücksichtigt werden. Mithilfe dieser Modifikationen erreicht der Algorithmus eine nahezu optimale Konsistenzrate. Teilweise können diese Ergebnisse auch auf allgemeinere stochastische Blockmodelle erweitert werden. Für beide Probleme illustrieren und validieren wir außerdem die theoretischen Resultate durch umfangreiche Experimente. Abschließend lässt sich sagen, dass die vorliegende Arbeit die Lücke zwischen theoretischen und praktischen Ergebnissen für die Algorithmen AWC und AWCD schließt. Insbesondere sind beide Algorithmen nach einigen Modifikationen auf relevanten Modellen konsistent mit einer nahezu optimalen Rate. / This thesis presents a theoretical study of two novel algorithms for clustering and community detection: AWC (Adaptive Weights Clustering) and AWCD (Adaptive Weights Community Detection). Most importantly, we discuss rates of consistency. For AWC, we focus on the asymptotics of the depth ε of the gap between clusters, i.e. the relative difference between the density level of the clusters and the density level of the area between them. We show that AWC is consistent with a nearly optimal rate. This extends the low-dimensional results of Efimov, Adamyan and Spokoiny (2019) to the manifold model while also considering much more general assumptions on the underlying density and the shape of clusters. In particular, we also consider the case of two points in the same cluster that are relatively close to the boundary. Moreover, we provide finite sample guarantees as well as the optimal tuning parameter λ. For AWCD, we consider the asymptotics of the difference θ − ρ between the two Bernoulli parameters of a symmetric stochastic block model. As it turns out, the resulting regime of strong consistency is far from optimal. However, we propose two major modifications to the algorithm: Firstly, we discuss an approach to minimize the bias of the involved estimates. Secondly, we suggest increasing the starting neighborhood guess of the algorithm by taking into account paths of minimal path length k. Using these modifications, we are able to show that AWCD achieves a nearly optimal rate of strong consistency. We partially extend these results to more general stochastic block models. For both problems, we illustrate and validate the theoretical study through a wide range of numerical experiments. To summarize, this thesis closes the gap between the practical and theoretical studies for AWC and AWCD. In particular, after some modifications, both algorithms exhibit a nearly optimal performance on relevant models.