Добірка наукової літератури з теми "Arbre enraciné"

Connes et Kreimer ont introduit une algèbre de Hopf des arbres enracinés (éventuellement décorés) Hr dans le but d'étudier la Renormalisation. Nous introduisons ici une algèbre de Hopf des arbres enracinés plans décorés Hpr, généralisant la construction de Hr. Cette algèbre de Hopf vérifie une propriété universelle en cohomologie de Hochschild. Nous montrons que cette algèbre est auto-duale. Cette propriété entraîne l'existence d'un couplage de Hopf entre Hpr et elle-même ; en conséquence, la base duale de la base des forêts permet de décrire l'espace des primitifs de Hpr, puis de trouver les primitifs de Hr par passage au quotient, ce qui répond à une question de Kreimer. Nous étudions de plus les Hr- et les Hpr-comodules de dimension finie et nous établissons le lien entre Hpr et d'autres algèbres de Hopf d'arbres telles que les algèbres de Brouder et Frabetti, de Loday et Ronco, de Grossman et Larson, ou la quantification de Hpr de Moerdijk et van der Laan<br>Connes and Kreimer have introduced a Hopf algebra of (decorated) rooted trees Hr, in order to study Renormalization. We introduce here a Hopf algebra of planar decorated rooted trees Hpr, which construction generalizes the construction of Hr. This Hopf algebra satisfies a universal property in Hochschild cohomology. We show that it is self-dual. This property induces the existence of non-degenerate Hopf pairing between Hpr and itself. As a consequence, the dual basis of the basis of forests allows to find a basis of the space of the primitive elements of Hpr, and then to find all primitive elements of Hr, answering a question of Kreimer. Moreover, we study the Hr- and Hpr-comodules of finite dimension, and we establish the link between Hpr and several other Hopf algebras of trees, such as the Hopf algebras of Brouder and Frabetti, of Loday and Ronco, of Grossman and Larson, or the quantization of Hpr of Moerdijk and van der Laan

Nous étudions dans cette thèse l'algèbre de Hopf H associée à l'opérade pré-Lie. L'espace des éléments primitifs du dual gradué est muni d'une structure pré-Lie à gauche notée ⊲ définie par l'insertion d'un arbre dans un autre. Nous retrouvons la relation de dérivation entre le produit pré-Lie ⊲ et le produit pré-Lie de greffe → sur les éléments primitifs du dual gradué de l'algèbre de Hopf de Connes Kreimer HCK. Nous mettons en évidence un coproduit sur le produit tensoriel H ⊗HCK, qui en fait une algèbre de Hopf dont le dual gradué est isomorphe à l'algèbre enveloppante du produit semi-direct des deux algèbres de Lie considérées. Nous montrons que l'espace engendré par les arbres enracinés qui ont au moins une arête, muni du produit d'insertion, est une algèbre pré-Lie (non libre) engendrée par deux éléments. Nous mettons en évidence deux familles de relations. De plus nous montrons un résultat similaire pour l'algèbre pré-Lie associée à l'opérade NAP. Finalement on introduit les opérades à débit constant et on montre que l'opérade pré-Lie s'obtient comme déformation de l'opérade NAP dans ce cadre.

Étant donnés un graphe simple non orienté G = (V, E) et un sommet particulier r dans V appelé racine, un arbre enraciné, ou r-arbre, de G est soit le graphe nul soit un arbre contenant r. Si un vecteur de capacités sur les sommets est donné, un sous-graphe de G est dit borné si le degré de chaque sommet dans le sous-graphe est inférieur ou égal à sa capacité. Soit w un vecteur de poids sur les arêtes et p un vecteur de profits sur les sommets. Le problème du r-arbre borné maximum (MBrT, de l’anglais Maximum Bounded r-Tree) consiste à trouver un r-arbre borné T = (U, F) de G tel que son poids soit maximisé. Si la contrainte de capacité du problème MBrT est relâchée, nous obtenons le problème du r-arbre maximum (MrT, de l’anglais Maximum r-Tree). Cette thèse contribue à l’étude des problèmes MBrT et MrT.Tout d’abord, ces deux problèmes sont formellement définis et leur complexité est étudiée. Nous présentons ensuite des polytopes associés ainsi qu’une formulation pour chacun d’entre eux. Par la suite, nous proposons plusieurs algorithmes combinatoires pour résoudre le problème MBrT (et donc le problème MrT) en temps polynomial sur les arbres, les cycles et les cactus. En particulier, un algorithme de programmation dynamique est utilisé pour résoudre le problème MBrT sur les arbres. Pour les cycles, nous sommes amenés a considérer trois cas différents pour lesquels le problem MBrT se réduit à certains problèmes polynomiaux. Pour les cactus, nous montrons tout d’abord que le problème MBrT peut être résolu en temps polynomial sur un type de graphes appelé cactus basis. En utilisant une série de décompositions en sous-problèmes sur les arbres et les cactus basis, nous obtenons un algorithme pour les graphes de type cactus.La deuxième partie de ce travail étudie la structure polyédrale de trois polytopes associés aux problèmes MBrT et MrT. Les deux premiers polytopes, Bxy(G,r,c) et Bx(G,r,c) sont associés au problème MBrT. Tous deux considèrent des variables sur les arêtes de G, mais seuls Bxy(G,r,c) possède également des variables sur les sommets de G. Le troisième polytope, Rx(G,r), est associé au problème MrT et repose uniquement sur les variables sur les arêtes. Pour chacun de ces trois polytopes, nous étudions sa dimension, caractérisons certaines inégalités définissant des facettes, et présentons les moyens possibles de décomposition. Nous introduisons également de nouvelles familles de contraintes. L’ajout de ces contraintes nous permettent de caractériser ces trois polytopes dans plusieurs classes de graphes.Pour finir, nous étudions les problèmes de séparation pour toutes les inégalités que nous avons trouvées jusqu’ici. Des algorithmes polynomiaux de séparation sont présentés, et lorsqu’un problème de séparation est NP-difficile, nous donnons des heuristiques de séparation. Tous les résultats théoriques développés dans ce travail sont implémentés dans plusieurs algorithmes de coupes et branchements auxquels une matheuristique est également jointe pour générer rapidement des solutions réalisables. Des expérimentations intensives ont été menées via le logiciel CPLEX afin de comparer les formulations renforcées et originales. Les résultats obtenus montrent de manière convaincante la force des formulations renforcées<br>Given a simple undirected graph G = (V, E) with a so-called root node r in V, a rooted tree, or an r-tree, of G is either the empty graph, or a tree containing r. If a node-capacity vector c is given, then a subgraph of G is said to be bounded if the degree of each node in the subgraph does not exceed its capacity. Let w be an edge-weight vector and p a node-price vector. The Maximum Bounded r-Tree (MBrT) problem consists of finding a bounded r-tree T = (U, F) of G such that its weight is maximized. If the capacity constraint from the MBrT problem is relaxed, we then obtain the Maximum r-Tree (MrT) problem. This dissertation contributes to the study of the MBrT problem and the MrT problem.First we introduce the problems with their definitions and complexities. We define the associated polytopes along with a formulation for each of them. We present several polynomial-time combinatorial algorithms for both the MBrT problem (and thus the MrT problem) on trees, cycles and cactus graphs. Particularly, a dynamic-programming-based algorithm is used to solve the MBrT problem on trees, whereas on cycles we reduce it to some polynomially solvable problems in three different cases. For cactus graphs, we first show that the MBrT problem can be solved in polynomial time on a so-called cactus basis, then break down the problem on any cactus graph into a series of subproblems on trees and on cactus basis.The second part of this work investigates the polyhedral structure of three polytopes associated with the MBrT problem and the MrT problem, namely Bxy(G, r, c), Bx(G, r, c) and Rx(G, r). Bxy(G, r, c) and Bx(G, r, c) are polytopes associated with the MBrT problem, where Bxy(G, r, c) considers both edge- and node-indexed variables and Bx(G, r, c) considers only edge-indexed variables. Rx(G, r) is the polytope associated with the MrT problem that only considers edge-indexed variables. For each of the three polytopes, we study their dimensions, facets as well as possible ways of decomposition. We introduce some newly discovered constraints for each polytope, and show that these new constraints allow us to characterize them on several graph classes. Specifically, we provide characterization for Bxy (G, r, c) on cactus graphs with the help of a decomposition through 1-sum. On the other hand, a TDI-system that characterizes Bx(G,r,c) is given in each case of trees and cycles. The characterization of Rx(G,r) on trees and cycles then follows as an immediate result.Finally, we discuss the separation problems for all the inequalities we have found so far, and present algorithms or cut-generation heuristics accordingly. A couple of branch-and-cut frameworks are implemented to solve the MBrT problem together with a greedy-based matheuristic. We compare the performances of the enhanced formulations with the original formulations through intensive computational test, where the results demonstrate convincingly the strength of the enhanced formulations

Nous étudions dans cette thèse l’algèbre de Hopf H associée à l’opérade pré-Lie. L’espace des éléments primitifs du dual gradué est muni d’une structure pré-Lie à gauche notée ⊲ définie par l’insertion d’un arbre dans un autre. Nous retrouvons la relation de dérivation entre le produit pré-Lie ⊲ et le produit pré-Lie de greffe → sur les éléments primitifs du dual gradué de l’algèbre de Hopf de Connes Kreimer HCK. Nous mettons en évidence un coproduit sur le produit tensoriel H ⊗HCK, qui en fait une algèbre de Hopf dont le dual gradué est isomorphe à l’algèbre enveloppante du produit semi-direct des deux algèbres de Lie considérées. Nous montrons que l’espace engendré par les arbres enracinés qui ont au moins une arête, muni du produit d’insertion, est une algèbre pré-Lie (non libre) engendrée par deux éléments. Nous mettons en évidence deux familles de relations. De plus nous montrons un résultat similaire pour l’algèbre pré-Lie associée à l’opérade NAP. Finalement on introduit les opérades à débit constant et on montre que l’opérade pré-Lie s’obtient comme déformation de l’opérade NAP dans ce cadre<br>We investigate in this thesis the Hopf algebra structure on the vector space H spanned by the rooted forests, associated with the pre-Lie operad. The space of primitive elements of the graded dual of this Hopf algebra is endowed with a left pre-Lie product denoted by ⊲, defined in terms of insertion of a tree inside another. In this thesis we retrieve the “derivation” relation between the pre-Lie structure ⊲ and the left pre-Lie product → on the space of primitive elements of the graded dual H0CK of the Connes-Kreimer Hopf algebra HCK, defined by grafting. We also exhibit a coproduct on the tensor product H⊗HCK, making it a Hopf algebra the graded dual of which is isomorphic to the enveloping algebra of the semidirect product of the two (pre-)Lie algebras considered. We prove that the span of the rooted trees with at least one edge endowed with the pre-Lie product ⊲ is generated by two elements. It is not free : we exhibit two families of relations. Moreover we prove a similar result for the pre-Lie algebra associated with the NAP operad. Finally, we introduce current preserving operads and prove that the pre-Lie operad can be obtained as a deformation of the NAP operad in this framework

Dans cette thèse, nous examinons différents cadres pour la théorie générale des opérades cycliques de Getzler et Kapranov. Comme le suggère le titre, nous établissons des fondements théoriques de natures syntaxiques, algébriques et catégorifiées pour la notion d’opérade cyclique. Dans le traitement syntaxique, nous proposons un langage formel à la manière du lambda-calcul, appelé mu-syntaxe, en tant que représentation légère de la structure &lt;&gt; d’opérades cycliques. Contrairement à la caractérisation originale des opérades cycliques, appelée la caractérisation &lt;&gt; , selon laquelle les opérations d’une opérade cyclique ont des entrées et une sortie qui peut être &lt;&lt; échangée &gt;&gt; avec une entrée, les opérades cycliques &lt;&gt; sont présentées comme des généralisations d’opérades pour lesquelles une opération n’a plus des entrées et une sortie, mais seulement des entrées (c’est-à-dire pour lesquelles la sortie est &lt;&gt; que les entrées). Grâce aux méthodes de réécriture derrière le formalisme, nous donnons une preuve pas-à-pas complète de l’équivalence entre les définitions biaisées et non biaisées des opérades cycliques.Guidés par le principe du microcosme de Baez et Dolan et par les définitions algébriques des opérades de Kelly et Fiore, dans l’approche algébrique, nous définissons les opérades cycliques à l’intérieur de la catégorie des espèces de structures de Joyal. De cette façon, la caractérisation originale &lt;&lt; exchangeable-output&gt;&gt; de Getzler et Kapranov, et la caractérisation alternative &lt;&gt; des opérades cycliques de Markl, sont toutes les deux incarnées comme monoïdes dans une catégorie monoïdale des espèces de structures. En s’appuyant sur un résultat de Lamarche sur la descente pour les espèces, nous utilisons ces définitions monoïdales pour prouver l’équivalence entre les points de vue &lt;&gt; et &lt;&lt; entries-only&gt;&gt; pour les opérades cycliques.Enfin, nous établissons une notion d’opérade cyclique catégorifiée pour les opérades cycliques avec symétries, définies dans la catégorie des ensembles en termes de générateurs et relations. Les catégorifications que nous introduisons sont obtenues en remplaçant des ensembles d’opérations de la même arité par des catégories, en relâchant certains axiomes de la structure, comme l’associativité et la commutativité, en isomorphismes, tout en laissant l’équivariance stricte, et en formulant des conditions de cohérence pour ces isomorphismes. Le théorème de cohérence que nous prouvons a la forme &lt;&lt; tous les diagrammes d’isomorphismes canoniques commutent &gt;&gt;. Pour les opérades cycliques &lt;&gt; , notre preuve a un caractère syntaxique et s’appuie sur la cohérence des opérades non symétriques catégorifiées, établie par Došen et Petrić. Nous prouvons la cohérence des opérades cycliques &lt;&gt;, en relevant au cadre catégorifié l’équivalence entre les définitions &lt;&gt; et &lt;&gt; , mise en place précédemment dans l’approche algébrique<br>In this thesis, we examine different frameworks for the general theory of cyclic operads of Getzler and Kapranov. As suggested by the title, we set up theoretical grounds of syntactic, algebraic and categorified nature for the notion of a cyclic operad.In the syntactic treatment, we propose a lambda-calculus-style formal language, called mu-syntax, as a lightweight representation of the entries-only cyclic operad structure. As opposed to the original exchangeable-output characterisation of cyclic operads, according to which the operations of a cyclic operad have inputs and an output that can be “exchanged” with one of the inputs, the entries-only cyclic operads have only entries (i.e. the output is put on the same level as the inputs). By employing the rewriting methods behind the formalism, we give a complete step-by-step proof of the equivalence between the unbiased and biased definitions of cyclic operads.Guided by the microcosm principle of Baez and Dolan and by the algebraic definitions of operads of Kelly and Fiore, in the algebraic approach we define cyclic operads internally to the category of Joyal’s species of structures. In this way, both the original exchangeable-output characterisation of Getzler and Kapranov, and the alternative entries-only characterisation of cyclic operads of Markl are epitomised as “monoid-like” objects in “monoidal-like” categories of species. Relying on a result of Lamarche on descent for species, we use these “monoid-like” definitions to prove the equivalence between the exchangeable-output and entries-only points of view on cyclic operads.Finally, we establish a notion of categorified cyclic operad for set-based cyclic operads with symmetries, defined in terms of generators and relations. The categorifications we introduce are obtained by replacing sets of operations of the same arity with categories, by relaxing certain defining axioms, like associativity and commutativity, to isomorphisms, while leaving the equivariance strict, and by formulating coherence conditions for these isomorphisms. The coherence theorem that we prove has the form “all diagrams of canonical isomorphisms commute”.For entries-only categorified cyclic operads, our proof is of syntactic nature and relies on the coherence of categorified operads established by Došen and Petrić. We prove the coherence of exchangeable-output categorified cyclic operads by “lifting to the categorified setting” theequivalence between entries-only and exchangeable-output cyclic operads, set up previously in the algebraic approach

Dans cette thèse, nous étudions le concept d’algèbre pré-Lie libre engendrée par un ensemble (non-vide). Nous rappelons la construction par A. Agrachev et R. Gamkrelidze des bases de monômes dans les algèbres pré-Lie libres. Nous décrivons la matrice des vecteurs d’une base de monômes en termes de la base d’arbres enracinés exposée par F. Chapoton et M. Livernet. Nous montrons que cette matrice est unipotente et trouvons une expression explicite pour les coefficients de cette matrice, en adaptant une procédure suggérée par K. Ebrahimi-Fard et D. Manchon pour l’algèbre magmatique libre. Nous construisons une structure d’algèbre pré-Lie sur l’algèbre de Lie libre $\mathcal{L}$(E) engendrée par un ensemble E, donnant une présentation explicite de $\mathcal{L}$(E) comme quotient de l’algèbre pré-Lie libre $\mathcal{T}$^E, engendrée par les arbres enracinés (non-planaires) E-décorés, par un certain idéal I. Nous étudions les bases de Gröbner pour les algèbres de Lie libres dans une présentation à l’aide d’arbres. Nous décomposons la base d’arbres enracinés planaires E-décorés en deux parties O(J) et $\mathcal{T}$(J), où J est l’idéal définissant $\mathcal{L}$(E) comme quotient de l’algèbre magmatique libre engendrée par E. Ici, $\mathcal{T}$(J) est l’ensemble des termes maximaux des éléments de J, et son complément O(J) définit alors une base de $\mathcal{L}$(E). Nous obtenons un des résultats importants de cette thèse (Théorème 3.12) sur la description de l’ensemble O(J) en termes d’arbres. Nous décrivons des bases de monômes pour l’algèbre pré-Lie (respectivement l’algèbre de Lie libre) $\mathcal{L}$(E), en utilisant les procédures de bases de Gröbner et la base de monômes pour l’algèbre pré-Lie libre obtenue dans le Chapitre 2. Enfin, nous étudions les développements de Magnus classique et pré-Lie, discutant comment nous pouvons trouver une formule de récurrence pour le cas pré-Lie qui intègre déjà l’identité pré-Lie. Nous donnons une vision combinatoire d’une méthode numérique proposée par S. Blanes, F. Casas, et J. Ros, sur une écriture du développement de Magnus classique, utilisant la structure pré-Lie de $\mathcal{L}$(E)<br>In this thesis, we study the concept of free pre-Lie algebra generated by a (non-empty) set. We review the construction by A. Agrachev and R. Gamkrelidze of monomial bases in free pre-Lie algebras. We describe the matrix of the monomial basis vectors in terms of the rooted trees basis exhibited by F. Chapoton and M. Livernet. Also, we show that this matrix is unipotent and we find an explicit expression for its coefficients, adapting a procedure implemented for the free magmatic algebra by K. Ebrahimi-Fard and D. Manchon. We construct a pre-Lie structure on the free Lie algebra $\mathcal{L}$(E) generated by a set E, giving an explicit presentation of $\mathcal{L}$(E) as the quotient of the free pre-Lie algebra $\mathcal{T}$^E, generated by the (non-planar) E-decorated rooted trees, by some ideal I. We study the Gröbner bases for free Lie algebras in tree version. We split the basis of E- decorated planar rooted trees into two parts O(J) and $\mathcal{T}$(J), where J is the ideal defining $\mathcal{L}$(E) as a quotient of the free magmatic algebra generated by E. Here $\mathcal{T}$(J) is the set of maximal terms of elements of J, and its complement O(J) then defines a basis of $\mathcal{L}$(E). We get one of the important results in this thesis (Theorem 3.12), on the description of the set O(J) in terms of trees. We describe monomial bases for the pre-Lie (respectively free Lie) algebra $\mathcal{L}$(E), using the procedure of Gröbner bases and the monomial basis for the free pre-Lie algebra obtained in Chapter 2. Finally, we study the so-called classical and pre-Lie Magnus expansions, discussing how we can find a recursion for the pre-Lie case which already incorporates the pre-Lie identity. We give a combinatorial vision of a numerical method proposed by S. Blanes, F. Casas, and J. Ros, on a writing of the classical Magnus expansion in $\mathcal{L}$(E), using the pre-Lie structure