Dans la première partie de ce mémoire nous introduisons toute la théorie nécessaire à une bonne compréhension de la théorie des variétés et orbifolds toriques. Dans la deuxième partie nous présentons la construction de Delzant d'une variété torique. Finalement, le troisième chapitre présente deux preuves différentes de la formule de Guillemin. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Géométrie kählérienne, Orbifold, Variété torique, Polytope de Delzant.

Le polytope des m-sous-espaces est défini comme l'enveloppe convexe des vecteurs caractéristiques de tous les sous-espaces de dimension m d'un espace affin fini. Le cas particulier du polytope des hyperplans a été étudié par Maurras (1993) et Anglada et Maurras (2003), qui ont obtenu une description complète des facettes. Le polytope général des m-sous-espaces que nous considérons possède une structure plus complexe, notamment concernant les facettes. Néanmoins, nous établissons dans cette thèse plusieurs familles de facettes. Nous caractérisons également complètement le groupe des automorphismes du polytope ainsi que l'adjacence des sommets du polytope des m-sous-espaces. Un tangle est un ensemble d'hyperplans d'un espace affin contenant un hyperplan par classe d'hyperplans parallèles. Anglada et Maurras ont montré que les tangles définissent des facettes du polytope des hyperplans et que toutes les facettes de ce polytope proviennent de tangles. Nous tentons d'établir une généralisation de ce résultat. Nous élaborons une classification des tangles en familles pour de petites dimensions d'espaces affins.

<p>This thesis consists of two papers.</p><p>The first paper is a study of the structure of the k-assignment polytope, whose vertices are the <em>m x n</em> (0; 1)-matrices with exactly <em>k</em> 1:s and at most one 1 in each row and each column. This is a natural generalisation of the Birkhoff polytope and many of the known properties of the Birkhoff polytope are generalised. Two equivalent representations of the faces are given, one as (0; 1)-matrices and one as ear decompositions of bipartite graphs. These tools are used to describe properties of the polytope, especially a complete description of the cover relation in the face lattice of the polytope and an exact expression for the diameter.</p><p>The second paper studies the edge-product space <em>Є(X)</em> for trees on <em>X</em>. This space is generated by the set of edge-weighted finite trees on <em>X</em>, and arises by multiplying the weights of edges on paths in trees. These spaces are closely connected to tree-indexed Markov processes in molecular evolutionary biology. It is known that <em>Є(X)</em> has a natural <em>CW</em>-complex structure, and a combinatorial description of the associated face poset exists which is a poset <em>S(X)</em> of <em>X</em>-forests. In this paper it is shown that the edge-product space is a regular cell complex. One important part in showing that is to conclude that all intervals <em>[Ô, Г], Г </em>Є<em> S(X),</em> have recursive coatom orderings.</p> / Report code: LiU-TEK-LIC-2004:46.

This thesis consists of two papers. The first paper is a study of the structure of the k-assignment polytope, whose vertices are the m x n (0; 1)-matrices with exactly k 1:s and at most one 1 in each row and each column. This is a natural generalisation of the Birkhoff polytope and many of the known properties of the Birkhoff polytope are generalised. Two equivalent representations of the faces are given, one as (0; 1)-matrices and one as ear decompositions of bipartite graphs. These tools are used to describe properties of the polytope, especially a complete description of the cover relation in the face lattice of the polytope and an exact expression for the diameter. The second paper studies the edge-product space Є(X) for trees on X. This space is generated by the set of edge-weighted finite trees on X, and arises by multiplying the weights of edges on paths in trees. These spaces are closely connected to tree-indexed Markov processes in molecular evolutionary biology. It is known that Є(X) has a natural CW-complex structure, and a combinatorial description of the associated face poset exists which is a poset S(X) of X-forests. In this paper it is shown that the edge-product space is a regular cell complex. One important part in showing that is to conclude that all intervals [Ô, Г], Г Є S(X), have recursive coatom orderings.

Dans ce mémoire nous allons définir l'associaèdre et voir différentes manières de construire ses réalisations. Nous allons premièrement voir la réalisation donnée par Jean-Louis Loday via les arbres binaires. Nous introduirons les permutoèdres généralisés ainsi que les associaèdres généralisés de type A et B. Ensuite, nous donnerons des réalisations généralisant celle de Loday via les orientations de graphe de Coxeter et les triangulations de polygones réguliers. Finalement, nous démontrerons une conjecture faite par Chapoton concernant le barycentre de l'associaèdre. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Associaèdre, permutoèdre, polytope abstrait, combinatoire de Catalan.

Dans cette thèse on étudie différents problèmes portant sur les matroïdes et les matroïdes orientés. On s'intéresse à trois sujets particuliers : la décomposition du polytope des bases d'un matroïde, l'orientation de matroïdes et le jeu de commutation de Shannon. Plus précisément dans le chapitre 2 nous étudions une décomposition spéciale introduite par Lafforgue. Pour un matroïde M, une décomposition du polytope des bases d'un matroïde P(M) est une décomposition de la forme P(M) = St i=1 P(Mi) où chaque P(Mi) est également un polytope des bases d'un matroïde pour un certain matroïde Mi, et pour chaque 1 i 6= j t, l'intersection P(Mi) \ P(Mj) est une face de P(Mi) et de P(Mj). Dans cette thèse, nous étudions la séparation par hyperplan, autrement dit la décomposition du polytope quand t = 2. Nous donnons des conditions suffisantes sur M pour que P(M) puisse avoir une séparation par hyperplan. Nous caractérisons également les cas où P(M1 M2) a une séparation par hyperplan où M1 M2 dénote la somme directe des matroïdes M1 et M2. Nous montrons finalement que P(M) n'a pas de séparation par hyperplan si M est binaire. Dans le chapitre 3 nous étudions la classe des matroïdes orientés du réseau. Après avoir donné une caractérisation complète des matroïdes orientés du réseau en fonction de l'union de matroïdes orientés uniformes de rang un, nous montrons que cette classe est fermée par dualité et par mineurs. Nous étudions ensuite les simplexes de l'arrangement d'hyperplans découlant de matroïdes orientés du réseau. Nous présentons une caractérisation de ces simplexes et construisons un arrangement de n hyperplans en dimension d contenant O(2k(n k )k) simplexes avec n < k = bd 2 c. Nous approfondissons une question posée par Grünbaum [Grünbaum, 1971] concernant les colorations des arrangements de pseudodroites. Nous prolongeons la question de Grünbaum à des arrangements d'hyperplans et répondons par l'affirmative à cette question généralisée pour les arrangements découlants de matroïdes orientés du réseau. Dans le chapitre 4 nous nous sommes intéressés à une une version sur les matroïdes orientés du célèbre jeu de commutation de Shannon, version introduite par Y.O. Hamidoune et M.Las Vergnas[Hamidoune et Las Vergnas, 1997a] en 1986. Ils ont conjecturé que la classification du jeu de commutation sur les matroïdes orientés est identique à la classification de la version non orientée. Dans cette thèse, nous confortons cette conjecture en montrant sa validité pour la classe infinie de matroïdes orientés obtenues comme union de matroïdes orientés uniformes de rang 1 et/ou de rang 2.

Dans ce travail, nous nous intéressons à l'estimation d'ensembles convexes dans l'espace Euclidien $\R^d$, en nous penchant sur deux modèles. Dans le premier modèle, nous avons à notre disposition un échantillon de $n$ points aléatoires, indépendants et de même loi, uniforme sur un ensemble convexe inconnu. Le second modèle est un modèle additif de régression, avec bruit sous-gaussien, et dont la fonction de régression est l'indicatrice d'Euler d'un ensemble convexe ici aussi inconnu. Dans le premier modèle, notre objectif est de construire un estimateur du support de la densité des observations, qui soit optimal au sens minimax. Dans le second modèle, l'objectif est double. Il s'agit de construire un estimateur du support de la fonction de régression, ainsi que de décider si le support en question est non vide, c'est-à-dire si la fonction de régression est effectivement non nulle, ou si le signal observé n'est que du bruit. Dans ces deux modèles, nous nous intéressons plus particulièrement au cas où l'ensemble inconnu est un polytope convexe, dont le nombre de sommets est connu. Si ce nombre est inconnu, nous montrons qu'une procédure adaptative permet de construire un estimateur atteignant la même vitesse asymptotique que dans le cas précédent. Enfin, nous démontrons que ce même estimateur pallie à l'erreur de spécification du modèle, consistant à penser à tort que l'ensemble convexe inconnu est un polytope. Nous démontrons une inégalité de déviation pour le volume de l'enveloppe convexe des observations dans le premier modèle. Nous montrons aussi que cette inégalité implique des bornes optimales sur les moments du volume manquant de cette enveloppe convexe, ainsi que sur les moments du nombre de ses sommets. Enfin, dans le cas unidimensionnel, pour le second modèle, nous donnons la taille asymptotique minimale que doit faire l'ensemble inconnu afin de pouvoir être détecté, et nous proposons une règle de décision, permettant un test consistant du caractère non vide de cet ensemble. / In this thesis, we are interested in statistical inference on convex bodies in the Euclidean space $\R^d$. Two models are investigated. The first one consists of the observation of $n$ independent random points, with common uniform distribution on an unknown convex body. The second one is a regression model, with additive subgaussian noise, where the regression function is the indicator function of an unknown convex body. In the first model, our goal is to estimate the unknown support of the common uniform density of the observed points. In the second model, we aim either to estimate the support of the regression function, or to detect whether this support is nonempty, i.e., the regression function is nonzero. In both models, we investigate the cases when the unknown set is a convex polytope, and when we know the number of vertices. If this number is not known, we propose an adaptive method which allows us to obtain a statistical procedure performing asymptotically as well as in the case of perfect knowledge of that number. In addition, this procedure allows misspecification, i.e., provides an estimator of the unknown set, which is optimal in a minimax sense, even if the unknown set is not polytopal, in the contrary to what may have been thought. We prove a universal deviation inequality for the volume of the convex hull of the observations in the first model. We show that this inequality allows one to derive tight bounds on the moments of the missing volume of this convex hull, as well as on the moments of the number of its vertices. In the one-dimensional case, in the second model, we compute the asymptotic minimal size of the unknown set so that it can be detected by some statistical procedure, and we propose a decision rule which allows consistent testing of whether of that set is empty.

L'associaèdre se situe à l'interface de plusieurs domaines mathématiques. Combinatoirement, il s'agit du complexe simplicial des dissections d'un polygone convexe (ensembles de diagonales ne se croisant pas deux à deux). Géométriquement, il s'agit d'un polytope dont les sommets et les arêtes encodent le graphe dual du complexe des dissections. Enfin l'associaèdre décrit la structure combinatoire qui définit la présentation par générateurs et relations de certaines algèbres, dites << amassées >>. Du fait de son omniprésence, de nouvelles familles généralisant cet objet sont régulièrement découvertes. Cependant elles n'ont souvent que de faibles interactions. Leurs études respectives présentent de notre point de vue deux enjeux majeurs : chercher à les relier en se basant sur les propriétés connues de l'associaèdre ; et chercher pour chacune des cadres combinatoire, géométrique et algébrique dans le même esprit.Dans cette thèse, nous traitons le lien entre combinatoire et géométrie pour certaines de ces généralisations : les associaèdres de graphes, les complexes de sous-mots et les complexes d'accordéons. Nous suivons un fil rouge consistant à adapter, à ces trois familles, une méthode de construction des associaèdres comme éventails (ensembles de cônes polyédraux), dite méthode des d-vecteurs et issue de la théorie des algèbres amassées. De manière plus large, notre problématique principale consiste à réaliser, c'est-à-dire plonger géométriquement dans un espace vectoriel, des complexes abstraits. Nous obtenons trois familles de nouvelles réalisations, ainsi qu'une quatrième encore conjecturale dont les premières instances constituent déjà des avancées significatives.Enfin, en sus des résultats géométriques, nous démontrons des propriétés combinatoires spécifiques à chaque complexe simplicial abordé. / The associahedron is at the interface between several mathematical fields. Combinatorially, it is the simplicial complex of dissections of a convex polygon (sets of mutually noncrossing diagonals). Geometrically, it is a polytope whose vertices and edges encode the dual graph of the complex of dissections. Finally the associahedron describes the combinatorial structure defining a presentation by generators and relations of certain algebras, called ``cluster algebras''. Because of its ubiquity, we regularly come up with new families generalizing this object. However there often are only few interactions between them. From our perspective, there are two main issues when studying them: looking for relations on the basis of known properties of the associahedron; and, for each, looking for combinatorial, geometric and algebraic frameworks in the same spirit.In this thesis, we deal with the link between combinatorics and geometry for some of these generalizations: graph associahedra, subword complexes and accordion complexes. We follow a guidelight consisting in adapting, to these three families, a method for constructing associahedra as fans (sets of polyhedral cones), called the d-vector method and coming from cluster algebra theory. More generally, our main concern is to realize, that is geometrically embed in a vector space, abstract complexes. We obtain three new families of generalizations, and a fourth conjectural one whose first instances already constitute significant advances.Finally in addition to the geometric results, we prove combinatorial properties specific to each encountered simplicial complex.

A long-standing problem in cobordism theory has been to find convenient manifolds to represent cobordism classes. For example, in the late 1950's, Hirzebruch asked which complex cobordism classes can be represented by smooth connected algebraic varieties. This question is still open. Progress can be made on this and related problems by studying certain convenient connected algebraic varieties, namely smooth projective toric varieties. The primary focus of this dissertation is to determine which complex cobordism classes can be represented by smooth projective toric varieties. A complete answer is given up to dimension six, and a partial answer is described in dimension eight. In addition, the role of smooth projective toric varieties in the polynomial ring structure of complex cobordism is examined. More specifically, smooth projective toric varieties are constructed as polynomial ring generators in most dimensions, and evidence is presented suggesting that a smooth projective toric variety can be chosen as a polynomial generator in every dimension. Finally, toric varieties with an additional fiber bundle structure are used to study some manifolds in oriented cobordism. In particular, manifolds with certain fiber bundle structures are shown to all be cobordant to zero in the oriented cobordism ring.

MSc(Eng),Faculty of Engineering and the Built Environment, University of the Witwatersrand, 2010 / This dissertation presents two important results: a novel algorithm that approximately solves the optimal assignment problem as well as a novel method of projecting matrices into the doubly stochastic polytope while preserving the optimal assignment. The optimal assignment problem is a classical combinatorial optimisation problem that has fuelled extensive research in the last century. The problem is concerned with a matching or assignment of elements in one set to those in another set in an optimal manner. It finds typical application in logistical optimisation such as the matching of operators and machines but there are numerous other applications. In this document a process of iterative weighted normalization applied to the benefit matrix associated with the Assignment problem is considered. This process is derived from the application of the Computational Ecology Model to the assignment problem and referred to as the OACE (Optimal Assignment by Computational Ecology) algorithm. This simple process of iterative weighted normalisation converges towards a matrix that is easily converted to a permutation matrix corresponding to the optimal assignment or an assignment close to optimality. The document also considers a method of projecting a matrix into the doubly stochastic polytope while preserving the optimal assignment. Various methods of projecting square matrices into the doubly stochastic polytope exist but none that preserve the assignment. This novel result could prove instrumental in solving assignment problems and promises applications in other optimisation algorithms similar to those that Sinkhorn’s algorithm finds.