Auswahl der wissenschaftlichen Literatur zum Thema „Subword complexes“

Cette thèse s'inscrit dans le domaine de la combinatoire algébrique. Certains algorithmes de tri peuvent être décrits par des diagrammes appelés réseaux de tri, et l'exécution de ces algorithmes sur des permutations se traduit alors par des arrangements de courbes sur ces réseaux. Ces arrangements donnent des modèles pour des structures combinatoires classiques : par exemple, le treillis de Tamari, dont les relations de couverture sont les rotations sur les arbres binaires, et qui est un quotient bien connu de l'ordre faible sur les permutations. Les complexes de sous-mots généralisent les réseaux de tris et les arrangements de courbes aux groupes de Coxeter. Ils ont des liens profonds en algèbre et géométrie, notamment dans le calcul de Schubert, l'étude des variétés grassmanniennes et la théorie des algèbres amassées. Cette thèse s'intéresse aux structures de treillis sur certains complexes de sous-mots, généralisant les treillis de Tamari. Plus précisément, elle étudie la relation définie par les extensions linéaires des facettes d'un complexe de sous-mot. Dans un premier lieu, nous nous intéressons aux complexes de sous-mots définis sur un mot triangulaire du groupe symétrique, que nous représentons par des arrangements de tuyaux triangulaires. Nous prouvons alors que cette relation définit un quotient de treillis d'un intervalle de l'ordre faible ; par ailleurs, nous pouvons également utiliser cette relation pour définir un morphisme de treillis de cet intervalle au graphe des flips du complexe de sous-mots restreint à certaines de ses facettes. Dans un second lieu, nous étendons notre étude aux complexes de sous-mots définis sur les mots alternants du groupe symétrique. Nous montrons que cette même relation définit également un quotient de treillis ; en revanche, le morphisme associé n'a plus pour image le graphe des flips, mais le squelette du polyhèdre de brique, un objet défini sur les complexes de sous-mots pour étudier des réalisations du multi-associahèdre. Enfin, nous discutons des possibles extensions de ces résultats aux groupes de Coxeter finis, ainsi que de leurs applications pour généraliser certains objets définis en type A comme les treillis de nu-Tamari<br>This thesis comes within the scope of algebraic combinatorics. Some sorting algorithms can be described by diagrams called sorting networks, and the execution of the algorithms on input permutations translates to arrangements of curves on the networks. These arrangements modelize some classical combinatorial structures: for example, the Tamari lattice, whose cover relations are the rotations on binary trees, and which is a well-known quotient of the weak order on permutations. Subword complexes generalize sorting network and arrangements of curves to Coxeter groups. They have deep connections in algebra and geometry, in particular in Schubert calculus, in the study of grassmannian varieties, and in the theory of cluster algebras. This thesis focuses on lattice structures on some subword complexes, generalizing Tamari lattices. More precisely, it studies the relation defined by linear extensions of the facets of a subword complex. At first we focus on subword complexes defined on a triangular word of the symmetric group, which we represent with triangular pipe dreams. We prove that this relation defines a lattice quotient of a weak order interval; moreover, we can also use this relation to define a lattice morphism from this interval to the restriction of the flip graph of the subword complex to some of its facets. Secondly, we extent our study to subword complexes defined on alternating words of the symmetric group. We prove that this same relation also defines a lattice quotient; however, the image of the associated morphism is no longer the flip graph, but the skeleton of the brick polyhedron, an object defines on subword complexes to study realizations of the multiassociahedron. Finally, we discuss possible extensions of these results to finite Coxeter groups, as well as their applications to generalize some objects defined in type A such as nu-Tamari lattices

<div>The Subword Complexity of a character string refers to the number of distinct substrings of any length that occur as contiguous patterns in the string. The kth Subword Complexity in particular, refers to the number of distinct substrings of length k in a string of length n. In this work, we evaluate the expected value and the second factorial moment of the kth Subword Complexity for the binary strings over memory-less sources. We first take a combinatorial approach to derive a probability generating function for the number of occurrences of patterns in strings of finite length. This enables us to have an exact expression for the two moments in terms of patterns' auto-correlation and correlation polynomials. We then investigate the asymptotic behavior for values of k=a log n. In the proof, we compare the distribution of the kth Subword Complexity of binary strings to the distribution of distinct prefixes of independent strings stored in a trie. </div><div>The methodology that we use involves complex analysis, analytical poissonization and depoissonization, the Mellin transform, and saddle point analysis.</div>