Explorations combinatoires des structures arborescentes et libres / Christophe Cordero ; sous la direction de Jean-Christophe Novelli et de Samuele Giraudo

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Catalogue Worldcat

Combinatoire algébrique

Opérades

Arbres (théorie des graphes) -- Informatique

Équations fonctionnelles

Novelli, Jean-Christophe (Directeur de thèse / thesis advisor)

Giraudo, Samuele (1986-....) (Directeur de thèse / thesis advisor)

Béal, Marie-Pierre (1962-....) (Président du jury de soutenance / praeses)

Manchon, Dominique (Rapporteur de la thèse / thesis reporter)

Luque, Jean-Gabriel (Membre du jury / opponent)

Rao, Michaël (1979-...) (Membre du jury / opponent)

Université Paris-Est (2015-....) (Organisme de soutenance / degree-grantor)

École doctorale Mathématiques, Sciences et Technologies de l'Information et de la Communication (Champs-sur-Marne, Seine-et-Marne ; 2015-....) (Ecole doctorale associée à la thèse / doctoral school)

Laboratoire d'informatique de l'Institut Gaspard Monge (Laboratoire associé à la thèse / thesis associated laboratory)

Résumé / Abstract : Nous abordons trois axes de la combinatoire algébrique et énumérative. Le premier concerne principalement la recherche d'un contre-exemple à la conjecture commutativement équivalente. Proposée dans les années soixante, elle conjecture que les codes non commutativement préfixes ne sont pas inclus dans des codes maximaux finis. La stratégie que nous adoptons est de d'abord trouver des codes non commutativement préfixes puis de chercher des codes maximaux finis susceptibles de les contenir. Nous donnons une caractérisation, raffinant l'inégalité de Kraft-Redheffer, des ensembles commutativement préfixes. Grâce à l’algorithme qui en découle, nous trouvons 70 codes non commutativement préfixes. Certains d'entre eux améliorent la borne inférieure qui était connue pour le problème du ratio de Shor. De plus, 7 de ces codes se projettent dans des factorisations de groupes cycliques, chose dont nous ignorions jusqu'à présent l'existence. Grâce aux raisonnements classiques de la théorie des factorisations des groupes cycliques, nous calculons des bornes inférieures sur les tailles des codes maximaux finis susceptibles de les contenir. Nous introduisons également la notion de "code modulaire baïonnette complet". Elle nous permet notamment d'améliorer certaines de ces bornes inférieures et de trouver les premiers exemples de codes non commutativement préfixes et non inclus dans des codes maximaux finis. Le deuxième axe de recherche porte sur la combinatoire des circuits. Nous dénombrons les circuits selon la nature de leurs générateurs, leurs nombre de générateurs, leurs nombre d’entrées et leurs nombre de sorties. La principale difficulté que nous rencontrons provient de l’ambiguïté de la grammaire qui définie les circuits. Nous présentons une nouvelle grammaire, issue d'une construction combinatoire et algébrique, non ambiguë qui les engendre. Nous en déduisons une bijection entre les circuits et des familles de chemins colorés en trois dimensions. En étudiant la combinatoire de ces chemins, nous obtenons des formules de récurrences, des équations fonctionnelles et des formules closes sur les circuits. Le dernier axe de recherche de cette thèse porte sur la réécriture dans des quotients magmatiques. Nous caractérisons tous les morphismes d'opérades peignes et nous en exhibons une structure de treillis. Nous étudions ensuite les 10 quotients magmatiques où deux arbres de degré 3 sont confondus. Pour 8 d'entre eux, nous en donnons des présentations convergentes, leurs séries de Hilbert et des réalisations combinatoires. Pour les 2 autres ainsi que pour les opérades peignes de degré supérieur à 4, nous conjecturons à partir de plusieurs explorations informatiques qu'ils ne possèdent pas de présentations convergentes

Résumé / Abstract : We study three domains of algebraic and enumerative combinatorics. Firstly, we are looking for a counter-example to the commutatively equivalence conjecture. Stated in the Sixties, it conjectures that a not commutatively prefix code is not included in a finite maximal code. First, we find some not commutatively prefix codes and then we search for some finite maximal codes that might contain them. Thanks to a refinement of Kraft's inequality that we have proven, we found mostly by computer exploration 70 not commutatively prefix codes. Some of them improve a lower bound from Shor or embedded in some factorizations of cyclic groups. Thanks to classical studies on factorizations of cyclic groups, we compute some lower bounds for the size of finites maximals codes that might contains them. We introduce the notion of "complete modular bayonet code", in order to compute the first examples of not commutatively prefix codes that are not included in a finite maximal code. Secondly, we present and prove a new construction of prographs. We deduce from it a bijection between prographs and some families of three-dimensional colouredlattice paths. By a classical study of these lattice paths, we obtain recurrence relations satisfied by the prographs and a functional equation satisfied by the generating series of prographs. Finally, we compute some closed formulas for prographs made of only one type of generators. Finally, we conclude this thesis by a study of magmatic quotient. Driven by computer experimentations, we study the 10 quotients of the magmatic operad by one cubic relation by expressing their Hilbert series and providing combinatorial realizations. Moreover, we found all morphisms between comb operads and we exhibit a lattice structure over them