Le but de cette thèse est d'étudier les structures symplectiques dans la catégorie des variétés linéaires par morceaux (PL). La question centrale est de déterminer si toute variété symplectique lisse $(M,omega)$ peut être triangulée de manière symplectique, au sens où il existe une variété linéaire par morceaux $K$ et une triangulation $h :K -> M$ telle que $h^*omega$ est une forme symplectique constante par morceaux. Nous étudions d'abord un problème plus simple, qui consiste à trianguler les formes volumes lisses. Étant donnée une variété lisse $M$ munie d'une forme volume $Omega$, nous montrons qu'il existe une triangulation lisse $h :K -> M$ telle que $h^*Omega$ est une forme volume constante par morceaux. En particulier, les variétés symplectiques lisses de dimension 2 admettent donc des triangulations symplectiques. Étant donnée une variété symplectique fermée $(M,omega)$, nous montrons ensuite que pour certaines triangulations lisses $h :K -> M$, on peut, par une modification arbitrairement petite du complexe $K$, supposer que la forme $h^*omega$ est de rang maximal le long de tous les simplexes de $K$. Ce résultat permet d'approximer arbitrairement bien toute variété symplectique fermée par une variété symplectique PL. Nous nous intéressons finalement au cas d'une sous-variété symplectique $M$ d'un espace ambiant qui admet lui-même une triangulation symplectique. Nous montrons qu'il est possible de construire un cobordisme entre la sous-variété $M$ considérée et une approximation lisse par morceaux de celle-ci, triangulée par un complexe symplectique. / In this thesis, we study symplectic structures in a piecewise linear (PL) setting. The central question is to determine whether a smooth symplectic manifold can be triangulated symplectically, in the sense that there exists a triangulation $h :K -> M$ such that $h^*omega$ is a piecewise constant symplectic form on $K$. We first focus on a simpler related problem, and show that any smooth volume form $Omega$ on $M$ can be triangulated. This means that there always exists a triangulation $h :K -> M$ such that $h^*Omega$ is a piecewise constant volume form. In particular, symplectic surfaces admit symplectic triangulations. Given a closed symplectic manifold $(M,omega)$, we then prove that there exists triangulations $h :K -> M$ for which the piecewise smooth form $h^*omega$ has maximal rank along all the simplices of $K$. This result allows to approximate arbitrarily closely any closed symplectic manifold by a PL one. Finally, we investigate the case of a symplectic submanifold $M$ of an ambient space which is itself symplectically triangulated, and give the construction of a cobordism between $M$ and a piecewise smooth approximation of $M$, triangulated by a symplectic complex. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Convex geometries are combinatorial structures; they capture in an abstract way the essential features of convexity in Euclidean space, graphs or posets for instance. A convex geometry consists of a finite ground set plus a collection of subsets, called the convex sets and satisfying certain axioms. In this work, we study two natural problems on convex geometries. First, we consider the maximum-weight convex set problem. After proving a hardness result for the problem, we study a special family of convex geometries built on split graphs. We show that the convex sets of such a convex geometry relate to poset convex geometries constructed from the split graph. We discuss a few consequences, obtaining a simple polynomial-time algorithm to solve the problem on split graphs. Next, we generalize those results and design the first polynomial-time algorithm for the maximum-weight convex set problem in chordal graphs. Second, we consider the realizability problem. We show that deciding if a given convex geometry (encoded by its copoints) results from a point set in the plane is ER-hard. We complete our text with a brief discussion of potential further work. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

A (convex) polytope P is said to be 2-level if every hyperplane H that is facet-defining for P has a parallel hyperplane H' that contains all the vertices of P which are not contained in H.Two level polytopes appear in different areas of mathematics, in particular in contexts related to discrete geometry and optimization. We study the problem of enumerating all combinatorial types of 2-level polytopes of a fixed dimension d. We describe the first algorithm to achieve this. We ran it to produce the complete database for d <= 8. Our results show that the number of combinatorial types of 2-level d-polytopes is surprisingly small for low dimensions d.We provide an upper bound for the number of combinatorially inequivalent 2-level d-polytopes. We phrase this counting problem in terms of counting some objects called 2-level configurations, that capture the class of "maximal" rank d 0/1-matrices, including (maximal) slack matrices of 2-level cones and 2-level polytopes. We provide a proof that the number of d-dimensional 2-level configurations coming from cones and polytopes, up to linear equivalence, is at most 2^{O(d^2 log d)}.Finally, we prove that the extension complexity of every stable set polytope of a bipartite graph with n nodes is O(n^2 log n) and that there exists an infinite class of bipartite graphs such that, for every n-node graph in this class, its stable set polytope has extension complexity equal to Omega(n log n). / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

The thesis focuses on two open problems on finite partially ordered sets: the structure of order polytopes and the approximation of the number of linear extensions of a poset by mean of graph entropy. The polytopes considered here are the linear ordering polytope, the semiorder polytope, the interval order polytope, the partial order polytope and also a generalisation of the linear ordering polytope: the linear extension polytope of a fixed poset P. Various results on the structure of theses polytopes are proved in the first part of the thesis. In the second part of the thesis, we improve the existing bounds linking the entropy of the incomparability graph of the poset P and its number of linear extension. / Le but de la thèse est d'étudier deux problèmes ouverts sur les ensembles ordonnés finis: la structure des polytopes d'ordre et l'approximation du nombre d'extensions linéaires d'un ordre partiel au moyen de la notion d'entropie de graphe. Les polytopes considérés sont le polytope des ordres totaux, le polytope des semiordres, le polytope des ordres d'intervalles, le polytope des ordres partiels, ainsi qu'une généralisation du polytope des ordres totaux: le polytope des extensions linéaires d'un ensemble ordonné fixé P. Des résultats sur la structure de ces polytopes sont présentés dans la première partie de la thèse. Dans la deuxième partie de la thèse, nous améliorons les bornes existantes liant l'entropie du graphe d'incomparabilité d'un ordre partiel et son nombre d'extensions linéaires. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished