Spelling suggestions: "subject:"algebraic combinatorics"" "subject:"algebraic combinatiorics""
11 |
Enhancing the Quandle Coloring Invariant for Knots and LinksCho, Karina Elle 01 January 2019 (has links)
Quandles, which are algebraic structures related to knots, can be used to color knot diagrams, and the number of these colorings is called the quandle coloring invariant. We strengthen the quandle coloring invariant by considering a graph structure on the space of quandle colorings of a knot, and we call our graph the quandle coloring quiver. This structure is a categorification of the quandle coloring invariant. Then, we strengthen the quiver by decorating it with Boltzmann weights. Explicit examples of links that show that our enhancements are proper are provided, as well as background information in quandle theory.
|
12 |
Pattern posets: enumerative, algebraic and algorithmic issuesCervetti, Matteo 22 March 2021 (has links)
The study of patterns in combinatorial structures has grown up in the past few decades to one of the most active trends of research in combinatorics. Historically, the study of permutations which are constrained by not containing subsequences ordered in various prescribed ways has been motivated by the problem of sorting permutations with certain devices. However, the richness of this notion
became especially evident from its plentiful appearances in several very different disciplines, such as pure mathematics, mathematical physics, computer science,biology, and many others. In the last decades, similar notions of patterns have been considered on discrete structures other than permutations, such as integer sequences, lattice paths, graphs, matchings and set partitions. In the first part of
this talk I will introduce the general framework of pattern posets and some classical problems about patterns. In the second part of this talk I will present some enumerative results obtained in my PhD thesis about patterns in permutations, lattice paths and matchings. In particular I will describe a generating tree with a single label for permutations avoiding the vincular pattern 1 - 32 - 4, a finite automata approach to enumerate lattice excursions avoiding a single pattern and some results about matchings avoiding juxtapositions and liftings of patterns.
|
13 |
Combinatoire algébrique liée aux ordres sur les permutations / Algebraic combinatorics on orders of permutationsPons, Viviane 07 October 2013 (has links)
Cette thèse se situe dans le domaine de la combinatoire algébrique et porte sur l'étude et les applications de trois ordres sur les permutations : les deux ordres faibles (gauche et droit) et l'ordre fort ou de Bruhat. Dans un premier temps, nous étudions l'action du groupe symétrique sur les polynômes multivariés. En particulier, les opérateurs de emph{différences divisées} permettent de définir des bases de l'anneau des polynômes qui généralisent les fonctions de Schur aussi bien du point de vue de leur construction que de leur interprétation géométrique. Nous étudions plus particulièrement la base des polynômes de Grothendieck introduite par Lascoux et Schützenberger. Lascoux a montré qu'un certain produit de polynômes peut s'interpréter comme un produit d'opérateurs de différences divisées. En développant ce produit, nous ré-obtenons un résultat de Lenart et Postnikov et prouvons de plus que le produit s'interprète comme une somme sur un intervalle de l'ordre de Bruhat. Nous présentons aussi l'implantation que nous avons réalisée sur Sage des polynômes multivariés. Cette implantation permet de travailler formellement dans différentes bases et d'effecteur des changements de bases. Elle utilise l'action des différences divisées sur les vecteurs d'exposants des polynômes multivariés. Les bases implantées contiennent en particulier les polynômes de Schubert, les polynômes de Grothendieck et les polynômes clés (ou caractères de Demazure).Dans un second temps, nous étudions le emph{treillis de Tamari} sur les arbres binaires. Celui-ci s'obtient comme un quotient de l'ordre faible sur les permutations : à chaque arbre est associé un intervalle de l'ordre faible formé par ses extensions linéaires. Nous montrons qu'un objet plus général, les intervalles-posets, permet de représenter l'ensemble des intervalles du treillis de Tamari. Grâce à ces objets, nous obtenons une formule récursive donnant pour chaque arbre binaire le nombre d'arbres plus petits ou égaux dans le treillis de Tamari. Nous donnons aussi une nouvelle preuve que la fonction génératrice des intervalles de Tamari vérifie une certaine équation fonctionnelle décrite par Chapoton. Enfin, nous généralisons ces résultats aux treillis de $m$-Tamari. Cette famille de treillis introduite par Bergeron et Préville-Ratelle était décrite uniquement sur les chemins. Nous en donnons une interprétation sur une famille d'arbres binaires en bijection avec les arbres $m+1$-aires. Nous utilisons cette description pour généraliser les résultats obtenus dans le cas du treillis de Tamari classique. Ainsi, nous obtenons une formule comptant le nombre d'éléments plus petits ou égaux qu'un élément donné ainsi qu'une nouvelle preuve de l'équation fonctionnelle des intervalles de $m$-Tamari. Pour finir, nous décrivons des structures algébriques $m$ qui généralisent les algèbres de Hopf $FQSym$ et $PBT$ sur les permutations et les arbres binaires / This thesis comes within the scope of algebraic combinatorics and studies problems related to three orders on permutations: the two said weak orders (right and left) and the strong order or Bruhat order.We first look at the action of the symmetric group on multivariate polynomials. By using the emph{divided differences} operators, one can obtain some generalisations of the Schur function and form bases of non symmetric multivariate polynomials. This construction is similar to the one of Schur functions and also allows for geometric interpretations. We study more specifically the Grothendieck polynomials which were introduced by Lascoux and Schützenberger. Lascoux proved that a product of these polynomials can be interpreted in terms of a product of divided differences. By developing this product, we reobtain a result of Lenart and Postnikov and also prove that it can be interpreted as a sum over an interval of the Bruhat order. We also present our implementation of multivariate polynomials in Sage. This program allows for formal computation on different bases and also implements many changes of bases. It is based on the action of the divided differences operators. The bases include Schubert polynomials, Grothendieck polynomials and Key polynomials. In a second part, we study the emph{Tamari lattice} on binary trees. This lattice can be obtained as a quotient of the weak order. Each tree is associated with the interval of its linear extensions. We introduce a new object called, emph{interval-posets} of Tamari and show that they are in bijection with the intervals of the Tamari lattice. Using these objects, we give the recursive formula counting the number of elements smaller than or equal to a given tree. We also give a new proof that the generating function of the intervals of the Tamari lattice satisfies some functional equation given by Chapoton. Our final contributions deals with the $m$-Tamari lattices. This family of lattices is a generalization of the classical Tamari lattice. It was introduced by Bergeron and Préville-Ratelle and was only known in terms of paths. We give the description of this order in terms of some family of binary trees, in bijection with $m+1$-ary trees. Thus, we generalize our previous results and obtain a recursive formula counting the number of elements smaller than or equal to a given one and a new proof of the functional equation. We finish with the description of some new $"m"$ Hopf algebras which are generalizations of the known $FQSym$ on permutations and $PBT$ on binary trees
|
14 |
Algèbres de Cherednik et ordres sur les blocs de Calogero-Moser des groupes imprimitifs / Cherednik algebras and orders on the Calogero-Moser partition of imprimitive groupsLiboz, Emilie 03 December 2012 (has links)
Cette thèse présente quelques résultats de la théorie des représentations des algèbres de Cherednikrationnelles en t=0 et traite en particulier des différents ordres construits sur la partition de Calogero-Moserdes groupes imprimitifs.On commence par généraliser au cas abélien certains résultats obtenus par M. Chlouveraki concernant lesblocs d'algèbres en système de Clifford pour un groupe cyclique, puis on construit un ordre sur les C*-pointsfixes d'une variété complexe quasi-projective normale, en utilisant la décomposition de Bialynicki-Birula.Dans la deuxième partie, on s'intéresse à la description des partitions de Calogero-Moser de deux groupesde réflexions complexes K et W quand K est un sous-groupe distingué de W et on généralise au cas abélienles résultats obtenus par G. Bellamy dans le cas d'un quotient W/K cyclique.Dans la troisième partie, on présente les différents ordres, construits par I. Gordon, sur la partition deCalogero-Moser des groupes G(l,1,n) pour certains paramètres : les ordres des a et c-fonctions, un ordrecombinatoire et l'ordre géométrique, qui est défini grâce aux C*-points fixes de certaines variétés decarquois, ces points fixes paramétrant les blocs de la partition de Calogero-Moser de G(l,1,n). On donneensuite les relations entre ces ordres, puis on étend ces constructions ainsi que ces liens à l'ensemble desparamètres.Enfin, dans la dernière partie, on tente de généraliser ces propriétés aux groupes G(l,e,n). On cherche alors,pour construire l'ordre géométrique sur la partition de Calogero-Moser de G(l,e,n), une variété dont les C*-points fixes décrivent les blocs de la partition de G(l,e,n). Dans le cas où e ne divise pas n, on construit lavariété qui nous permet de définir l'ordre géométrique et de le relier aux autres ordres. Pour le cas e divise n,on propose une variété qui pourrait décrire par ses points fixes les blocs de Calogero-Moser de G(l,e,n) etnous permettre de construire l'ordre géométrique. / This work is a contribution to the representation theory of Rational Cherednik Algebras for t=0 and deals inparticular with different orders on the Calogero-Moser partition of imprimitive reflection groups.In the first part, we generalize to the abelian case some results about blocs of algebras in Clifford systemobtained by M. Chlouveraki in the cyclic case, and then we build an order on the C*-fixed points of acomplex, quasi-projective and normal variety, using the Bialynicki-Birula decomposition.The second part deals with the Calogero-Moser partition of two groups K and W, when K is a normalsubgroup of W, and generalize to the abelian case the results that G. Bellamy obtained when the quotientW/K is cyclic.In the third part, we present the different orders that I. Gordon built in the Calogero-Moser partition of thegroups G(l,1,n) and for some parameters : the orders of the a and c-functions, a combinatorial order and thegeometric order, defined using the C*-fixed points of some quiver varieties which parametrise the blocs of theCalogero-Moser partition of G(l,1,n). Then we give some relations between these orders and we extendthese constructions and these links for all parameters.Finally, in the last part, we try to generalize these properties for the groups G(l,e,n). We are looking for avariety whose C*-fixed points describe blocs of G(l,e,n) to construct the geometric order on the Calogero-Moser partition of G(l,e,n). When n is not divided by e, we build this variety that enables us to define thegeometric order and to show all the links with the other orders. When e don't divide n, we suggest a varietywhich could describe the blocs of G(l,e,n) and allow us to build the geometric order.
|
15 |
Structures Hopf-algébriques et opéradiques sur différentes familles d'arbres / Hopf-algebraics and operadics structures on different families of treesMansuy, Anthony 31 May 2013 (has links)
Nous introduisons les notions de forêts préordonnées et préordonnées en tas, généralisant les constructions des forêts ordonnées et ordonnées en tas. On démontre que les algèbres des forêts préordonnées et préordonnées en tas sont des algèbres de Hopf pour le coproduit de coupes et on construit un morphisme d'algèbres de Hopf dans l'algèbre des mots tassés. Ensuite, nous définissons un autre coproduit sur les forêts préordonnées donné par la contraction d'arêtes et nous donnons une description combinatoire de morphismes définis sur des algèbres de Hopf de forêts et à valeurs dans les algèbres de Hopf de battages et de battages contractants. Par ailleurs, nous introduisons la notion d'algèbre bigreffe, généralisant les notions d'algèbres de greffes à gauche et à droite. Nous décrivons l'algèbre bigreffe libre engendrée par un générateur et nous munissons cette algèbre d'une structure d'algèbre de Hopf et d'un couplage. Nous étudions ensuite le dual de Koszul de l'operade bigreffe et nous donnons une description combinatoire de l'algèbre bigreffe dual engendrée par un générateur. A l'aide d'une méthode de réécriture, nous prouvons que l'opérade bigreffe est Koszul. Nous définissons la notion de bialgèbre bigreffe infinitésimale et nous prouvons un analogue des théorèmes de Poincaré-Birkhoff-Witt et de Cartier-Milnor-Moore pour les bialgèbres bigreffe infinitésimales connexes. Pour finir, à partir de deux opérateurs de greffes, nous construisons des algèbres de Hopf d'arbres enracinés et ordonnés $ mathbf{B}^{i} $, $ i in mathbb{N}^{ast} $, $ mathbf{B}^{infty} $ et $ mathbf{B} $ vérifiant les relations d'inclusions $ mathbf{B}^{1} subseteq hdots mathbf{B}^{i} subseteq mathbf{B}^{i+1} subseteq hdots subseteq mathbf{B}^{infty} subseteq mathbf{B} $. On munit $ mathbf{B} $ d'une structure de bialgèbre dupliciale dendriforme et on en déduit que $ mathbf{B} $ est colibre et auto-duale. Nous démontrons que $ mathbf{B} $ est engendrée comme algèbre bigreffe par un générateur. / We introduce the notions of preordered and heap-preordered forests, generalizing the construction of ordered and heap-ordered forests. We prove that the algebras of preordered and heap-preordered forests are Hopf for the cut coproduct, and we construct a Hopf morphism to the Hopf algebra of packed words. In addition, we define another coproduct on the preordered forests given by the contraction of edges, and we give a combinatorial description of morphims defined on Hopf algebras of forests with values in the Hopf algebras of shuffes or quasi-shuffles. Moreover, we introduce the notion of bigraft algebra, generalizing the notions of left and right graft algebras. We describe the free bigraft algebra generated by one generator and we endow this algebra with a Hopf algebra structure, and a pairing. Next, we study the Koszul dual of the bigraft operad and we give a combinatorial description of the free dual bigraft algebra generated by one generator. With the help of a rewriting method, we prove that the bigraft operad is Koszul. We define the notion of infinitesimal bigraft bialgebra and we prove an analogue of Poincaré-Birkhoff-Witt and Cartier-Milnor-Moore theorems for connected infinitesimal bigraft bialgebras. Finally, with two grafting operators, we construct Hopf algebras of rooted and ordered trees $ mathbf{B}^{i} $, $ i in mathbb{N}^{ast} $, $ mathbf{B}^{infty} $ and $ mathbf{B} $ satisfying the inclusion relations $ mathbf{B}^{1} subseteq hdots mathbf{B}^{i} subseteq mathbf{B}^{i+1} subseteq hdots subseteq mathbf{B}^{infty} subseteq mathbf{B} $. We endow $ mathbf{B} $ with a structure of duplicial dendriform bialgebra and we deduce that $ mathbf{B} $ is cofree and self-dual. We prove that $ mathbf{B} $ is generated as bigraft algebra by one generator.
|
16 |
Théorie des représentations combinatoire de tours de monoïdes : Application à la catégorification et aux fonctions de parking / Combinatorial representation theory of tower monoids : Application to categorification and to parking functionsVirmaux, Aladin 13 June 2016 (has links)
Cette thèse se situe en combinatoire algébrique, et plus particulièrement en théorie combinatoire des représentations linéaires des monoïdes finis.Rappelons qu'un monoïde est un ensemble fini M muni d'une multiplication et d'un élément neutre, et qu'une représentation de M est un morphisme de M dans le monoïde des matrices $M_n(ck)$ où $ck$ est un corps, typiquement $ck =CC$. Les résultats des dernières décennies donnent un contrôle assez fin sur les représentations des monoïdes, permettant souvent de se ramener à de la théorie des représentations des groupes et de la combinatoire sur des préordres.En 1996, Krob et Thibon ont montré que l'induction et la restriction des représentations irréductibles et projectives de la tour des $0$-algèbres de Hecke $H_n(0)$ permet de munir l'ensemble des caractères d'une structure d'algèbre de Hopf, qui est isomorphe a l'algèbre de Hopf $ncsf$ des fonctions symétriques non commutatives. Cela donne une emph{catégorification} de$ncsf$, c'est-à-dire une interprétation de celle-ci en terme de théorie des représentations. Ils prolongent ainsi un résultat dû à Frobenius établissant un lien entre l'anneau des caractères de la tour des groupes symétriques et lesfonctions symétriques. Un problème naturel depuis lors est d'essayer de catégorifier d'autres algèbres de Hopf -- par exemple l'algèbre $pbt$ desarbres binaires de Loday et Ronco -- par des tours d'algèbres.Deviner une telle tour d'algèbres est difficile en général. Dans le cadre de cemanuscrit on restreint le champ de recherche aux tours de monoïdes, afin de mieux contrôler leurs représentations. C'est naturel car ce cadre couvre enfait les deux exemples fondamentaux ci-dessus, tandis qu'il est impossible decatégorifier $ncsf$ avec seulement une tour de groupes.Nous commençons par donner quelques résultats sur les représentations des toursde monoïdes. Ensuite, nous nous intéressons à la catégorification par destours de semi-treillis, et en particulier de quotients du permutoèdre. Avecceux-ci, nous catégorifions la structure de cogèbre de $fqsym$ sur la base$gbasis$ et celle d'algèbre de $fqsym$ sur la base $fbasis$. Cela ne permetcependant pas de catégorifier simultanément toute la structure de Hopf de ces algèbres. Dans un second temps, nous menons une recherche exhaustive des catégorifications de $pbt$. Nous montrons que, sous des hypothèses naturelles,il n'existe pas de catégorification de $pbt$ par une tour de monoïdesapériodiques. Enfin, nous démontrons que, dans un certain sens, la tour des monoïdes $0$-Hecke est la tour de monoïdes la plus simple catégorifiant $ncsf$.La seconde partie porte sur les fonctions de parking, par application des résultats de la première partie. D'une part, nous étudions la théorie des représentations de la tour des fonctions de parking croissantes. D'autre part,dans un travail commun avec Jean-Baptiste Priez nous reprenons une généralisation des fonctions de parking due à Stanley et Pitman. Afin d'obtenir des formules d'énumérations, nous utilisons une variante -- plus efficace dansle cas présent -- de la théorie des espèces. Nous donnons une action de$H_n(0)$ (et non du groupe symétrique) sur les fonctions de parking généralisées, et utilisons le théorème de catégorification de Krob et Thibon,pour relever dans les fonctions symétriques non commutatives le caractère de cette action. / This thesis is focused on combinatorical representation theory of finitemonoids within the field of algebraic combinatorics.A monoid $M$ is a finite set endowed with a multiplication and a neutralelement. A representation of $M$ is a morphism from $M$ into the monoid ofmatrices $M_n(ck)$ where $ck$ is a field; in this work it will typically bereferred to as $ck = CC$.The results obtained in the last decades allows us to use representation theoryof groups, and combinatorics on preorders in order to explore representationtheory of finite monoides.In 1996, Krob and Thibon proved that the induction and restriction rules ofirreducible and projective representations of the tower of $0$-Hecke monoidsendows its ring of caracters with a Hopf algebra structure, isomorph to thenon-commutative symmetric functions Hopf algebra $ncsf$. This gives acategorification of $ncsf$, which is an interpretation of the non-commutativesymmetruc functions in the language of representation theory. This extends atheorem of Frobenius endowing the character ring of symmetric groups to theHopf algebra of symmetric functions. Since then a natural problem is tocategorify other Hopf algebras -- for instance the Planar Binary Tree algebraof Loday and Ronco -- by a tower of algebras.Guessing such a tower of algebra is a difficult problem in general.In this thesis we restrict ourselves to towers of monoids in order to have abetter control on its representations. This is quite natural as on one hand,this setup covers both previous fundamental examples, whereas $ncsf$cannot be categorified in the restricted set of tower of group algebras.In the first part of this work, we start with some results about representationtheory of towers of monoids. We then focus on categorification with towers ofsemilatices, for example the tower of permutohedrons. We categorify thealgebra, and cogebra structure of $fqsym$, but not the full Hopf algebrastructure with its dual. We then make a comprehensive search in order tocategorify $pbt$ with a tower of monoids. We show that under naturalhypothesis, there exists no tower of monoids satisfying the categorificationaxioms. Finally we show that in some sense, the tower of $0$-Hecke monoids isthe simplest tower categorifying $ncsf$.The second part of this work deals with parking functions, applying resultsfrom the first part. We first study the representation theory of non decreasingparking functions. We then present a joint work with Jean-Baptiste Priez on ageneralization of parking functions from Pitman and Stanley. To obtainenumeration formulas, we use a variant of the species theory which was moreefficient in our case.We used an action of $H_n(0)$ instead of the symmetric group and use theKrob-Thibon theorem to lift the character of this action into the Hopf algebraof non-commutative symmetric functions.
|
17 |
Classification of P-oligomorphic groups, conjectures of Cameron and Macpherson / Classification des groupes P-oligomorphes, conjectures de Cameron et MacphersonFalque, Justine 29 November 2019 (has links)
Les travaux présentés dans cette thèse de doctorat relèvent de la combinatoire algébrique et de la théorie des groupes. Précisément, ils apportent une contribution au domaine de recherche qui étudie le comportement des profils des groupes oligomorphes.La première partie de ce manuscrit introduit la plupart des outils qui nous seront nécessaires, à commencer par des éléments de combinatoire et combinatoire algébrique.Nous présentons les fonctions de comptage à travers quelques exemples classiques, et nous motivons l'addition d'une structure d'algèbre graduée sur les objets énumérés dans le but d'étudier ces fonctions.Nous évoquons aussi les notions d'ordre et de treillis.Dans un second temps, nous donnons un aperçu des définitions et propriétés de base associées aux groupes de permutations, ainsi que quelques résultats de théorie des invariants. Nous terminons cette partie par une description de la méthode d'énumération de Pólya, qui permet de compter des objets sous une action de groupe.La deuxième partie est consacrée à l'introduction du domaine dans lequel s'inscrit cette thèse, celui de l'étude des profils de structures relationnelles, et en particulier des profils orbitaux. Si G est un groupe de permutations infini, son profil est la fonction de comptage qui envoie chaque entier n > 0 sur le nombre d'orbites de n-sous-ensembles, pour l'action induite de G sur les sous-ensembles finis d'éléments.Cameron a conjecturé que le profil de G est équivalent à un polynôme dès lors qu'il est borné par un polynôme. Une autre conjecture, plus forte, a été plus tard émise par Macpherson : elle implique une certaine structure d'algèbre graduée sur les orbites de sous-ensembles, créée par Cameron et baptisée algèbre des orbites, soutenant que si le profil est borné par un polynôme, alors l'algèbre des orbites est de type fini.Comme amorce de notre étude de ce problème, nous développons quelques exemples et faisons nos premiers pas vers une résolution en examinant les systèmes de blocs des groupes de profil borné par un polynôme --- que nous appelons P-oligomorphes ---,ainsi que la notion de sous-produit direct.La troisième partie démontre une classification des groupes P-oligomorphes, notre résultat le plus important et dont la conjecture de Macpherson se révèle un corollaire.Tout d'abord, nous étudions la combinatoire du treillis des systèmes de blocs,qui conduit à l'identification d'un système généralisé particulier, constituébde blocs ayant de bonnes propriétés. Nous abordons ensuite le cas particulier o`u il se limite à un seul bloc de blocs, pour lequel nous établissons une classification. La preuve emprunte à la notion de sous-produit direct pour gérer les synchronisations internes au groupe, et a requis une part d'exploration informatique afin d'être d'abord conjecturée.Dans le cas général, nous nous appuyons sur les résultats précédents et mettons en évidence la structure de G comme produit semi-direct impliquant son sous-groupe normal d'indice fini minimal et un groupe fini. Ceci permet de formaliser une classification complète des groupes P-oligomorphes,et d'en déduire la forme de l'algèbre des orbites : (à peu de choses près) une algèbre d'invariants explicite d'un groupe fini. Les conjectures de Macpherson et de Cameron en découlent, et plus généralement une compréhension exhaustive de ces groupes.L'annexe contient des extraits du code utilisé pour mener la preuve à bien,ainsi qu'un aperçu de celui qui a été produit en s'appuyant sur la nouvelle classification, qui permet de manipuler les groupes P-oligomorphes en usant d'une algorithmique adaptée. Enfin, nous joignons ici notre première preuve, plus faible, des deux conjectures. / This PhD thesis falls under the fields of algebraic combinatorics and group theory. Precisely,it brings a contribution to the domain that studies profiles of oligomorphic permutation groups and their behaviors.The first part of this manuscript introduces most of the tools that will be needed later on, starting with elements of combinatorics and algebraic combinatorics.We define counting functions through classical examples ; with a view of studying them, we argue the relevance of adding a graded algebra structure on the counted objects.We also bring up the notions of order and lattice.Then, we provide an overview of the basic definitions and properties related to permutation groups and to invariant theory. We end this part with a description of the Pólya enumeration method, which allows to count objects under a group action.The second part is dedicated to introducing the domain this thesis comes withinthe scope of. It dwells on profiles of relational structures,and more specifically orbital profiles.If G is an infinite permutation group, its profile is the counting function which maps any n > 0 to the number of orbits of n-subsets, for the inducedaction of G on the finite subsets of elements.Cameron conjectured that the profile of G is asymptotically equivalent to a polynomial whenever it is bounded by apolynomial.Another, stronger conjecture was later made by Macpherson : it involves a certain structure of graded algebra on the orbits of subsetscreated by Cameron, the orbit algebra, and states that if the profile of G is bounded by a polynomial, then its orbit algebra is finitely generated.As a start in our study of this problem, we develop some examples and get our first hints towards a resolution by examining the block systems ofgroups with profile bounded by a polynomial --- that we call P-oligomorphic ---, as well as the notion of subdirect product.The third part is the proof of a classification of P-oligomorphic groups,with Macpherson's conjecture as a corollary.First, we study the combinatorics of the lattice of block systems,which leads to identifying one special, generalized such system, that consists of blocks of blocks with good properties.We then tackle the elementary case when there is only one such block of blocks, for which we establish a classification. The proof borrows to the subdirect product concept to handle synchronizations within the group, and relied on an experimental approach on computer to first conjecture the classification.In the general case, we evidence the structure of a semi-direct product involving the minimal normal subgroup of finite index and some finite group.This allows to formalize a classification of all P-oligomorphic groups, the main result of this thesis, and to deduce the form of the orbit algebra: (little more than) an explicit algebra of invariants of a finite group. This implies the conjectures of Macpherson and Cameron, and a deep understanding of these groups.The appendix provides parts of the code that was used, and a glimpse at that resulting from the classification afterwards,that allows to manipulate P-oligomorphic groups by apropriate algorithmics. Last, we include our earlier (weaker) proof of the conjectures.
|
18 |
Algèbres de Hecke carquois et généralisations d'algèbres d'Iwahori-Hecke / Quiver Hecke algebras and generalisations of Iwahori-Hecke algebrasRostam, Salim 19 November 2018 (has links)
Cette thèse est consacrée à l'étude des algèbres de Hecke carquois et de certaines généralisations des algèbres d'Iwahori-Hecke. Dans un premier temps, nous montrons deux résultats concernant les algèbres de Hecke carquois, dans le cas où le carquois possède plusieurs composantes connexes puis lorsqu'il possède un automorphisme d'ordre fini. Ensuite, nous rappelons un isomorphisme de Brundan-Kleshchev et Rouquier entre algèbres d'Ariki-Koike et certaines algèbres de Hecke carquois cyclotomiques. D'une part nous en déduisons qu'une équivalence de Morita importante bien connue entre algèbres d'Ariki-Koike provient d'un isomorphisme, d'autre part nous donnons une présentation de type Hecke carquois cyclotomique pour l'algèbre de Hecke de G(r,p,n). Nous généralisons aussi l'isomorphisme de Brundan-Kleshchev pour montrer que les algèbres de Yokonuma-Hecke cyclotomiques sont des cas particuliers d'algèbres de Hecke carquois cyclotomiques. Finalement, nous nous intéressons à un problème de combinatoire algébrique, relié à la théorie des représentations des algèbres d'Ariki-Koike. En utilisant la représentation des partitions sous forme d'abaque et en résolvant, via un théorème d'existence de matrices binaires, un problème d'optimisation convexe sous contraintes à variables entières, nous montrons qu'un multi-ensemble de résidus qui est bégayant provient nécessairement d'une multi-partition bégayante. / This thesis is devoted to the study of quiver Hecke algebras and some generalisations of Iwahori-Hecke algebras. We begin with two results concerning quiver Hecke algebras, first when the quiver has several connected components and second when the quiver has an automorphism of finite order. We then recall an isomorphism of Brundan-Kleshchev and Rouquier between Ariki-Koike algebras and certain cyclotomic quiver Hecke algebras. From this, on the one hand we deduce that a well-known important Morita equivalence between Ariki--Koike algebras comes from an isomorphism, on the other hand we give a cyclotomic quiver Hecke-like presentation for the Hecke algebra of type G(r,p,n). We also generalise the isomorphism of Brundan-Kleshchev to prove that cyclotomic Yokonuma-Hecke algebras are particular cases of cyclotomic quiver Hecke algebras. Finally, we study a problem of algebraic combinatorics, related to the representation theory of Ariki-Koike algebras. Using the abacus representation of partitions and solving, via an existence theorem for binary matrices, a constrained optimisation problem with integer variables, we prove that a stuttering multiset of residues necessarily comes from a stuttering multipartition.
|
19 |
On Hopf algebras of symmetric and quasisymmetric functionsDahlgren, Isabel January 2024 (has links)
This bachelor thesis aims to give an introduction to various Hopf algebras that arise in combinatorics, with a view towards symmetric functions. We begin by covering the algebraic background needed to define Hopf algebras, including a discussion of the algebra-coalgebra duality. Takeuchi's formula for the antipode is stated and proved. It is then generalised to incidence Hopf algebras. This is followed by a discussion of the Hopf algebra of symmetric functions. It is shown that the Hopf algebra of symmetric functions is self-dual. We also show that the graded dual of the Hopf algebra of quasisymmetric functions is the Hopf algebra of non-commutative symmetric functions. Relations to the Hopf algebra of symmetric functions in non-commuting variables are emphasised. Finally, we state and prove the Aguiar-Bergeron-Sottile universality theorem.
|
20 |
Calcul des invariants de groupes de permutations par transformée de Fourier / Calculate invariants of permutation groups by Fourier TransformBorie, Nicolas 07 December 2011 (has links)
Cette thèse porte sur trois problèmes en combinatoire algébrique effective et algorithmique.Les premières parties proposent une approche alternative aux bases de Gröbner pour le calcul des invariants secondaires des groupes de permutations, par évaluation en des points choisis de manière appropriée. Cette méthode permet de tirer parti des symétries du problème pour confiner les calculs dans un quotient de petite dimension, et ainsi d'obtenir un meilleur contrôle de la complexité algorithmique, en particulier pour les groupes de grande taille. L'étude théorique est illustrée par de nombreux bancs d'essais utilisant une implantation fine des algorithmes. Un prérequis important est la génération efficace de vecteurs d'entiers modulo l'action d'un groupe de permutation, dont l'algorithmique fait l'objet d'une partie préliminaire.La quatrième partie cherche à déterminer, pour un certain quotient naturel d'une algèbre de Hecke affine, quelles spécialisations des paramètres aux racines de l'unité donne un comportement non générique.Finalement, la dernière partie présente une conjecture sur la structure d'une certaine $q$-déformation des polynômes harmoniques diagonaux en plusieurs paquets de variables pour la famille infinie de groupes de réflexions complexes.Tous ces chapitres s'appuient fortement sur l'exploration informatique, et font l'objet de multiples contributions au logiciel Sage. / This thesis concerns algorithmic approaches to three challenging problems in computational algebraic combinatorics.The firsts parts propose a Gröbner basis free approach for calculating the secondary invariants of a finite permutation group, proceeding by using evaluation at appropriately chosen points. This approach allows for exploiting the symmetries to confine the calculations into a smaller quotient space, which gives a tighter control on the algorithmic complexity, especially for large groups. The theoretical study is illustrated by extensive benchmarks using a fine implementation of algorithms. An important prerequisite is the generation of integer vectors modulo the action of a permutation group, whose algorithmic constitute a preliminary part of the thesis.The fourth part of this thesis is determining for a certain interesting quotient of an affine Hecke algebra exactly which root-of-unity specialization of its parameter lead to non-generic behavior.Finally, the last part presents a conjecture on the structure of certain q-deformed diagonal harmonics in many sets of variables for the infinite family of complex reflection groups.All chapters proceed widely by computer exploration, and most of established algorithms constitute contributions of the software Sage.
|
Page generated in 0.0706 seconds