Geometric realizations using regular subdivisions: Construction of many polytopes, sweep polytopes, s-permutahedra

Abstract

[eng] This thesis concerns three problems of geometric realizations of combinatorial structures via polytopes and polyhedral subdivisions. A polytope is the convex hull of a finite set of points in a Euclidean space Rd. It is endowed with a combinatorial structure coming from its faces. A subdivision is a collection of polytopes whose faces intersect properly and such that their union is convex. It is regular if it can be obtained by taking the lower faces of a lifting of its vertices in one dimension higher. We first present a new geometric construction of many combinatorially different polytopes of fixed dimension and number of vertices. This construction relies on showing that certain polytopes admit many regular triangulations. It allows us to improve the best known lower bound on the number of combinatorial types of polytopes. We then study the projections of permutahedra, that we call sweep polytopes because they model the possible orderings of a fixed point configuration by hyperplanes that sweep the space in a constant direction. We also introduce and study a combinatorial abstraction of these structures: the sweep oriented matroids, that generalize Goodman and Pollack’s theory of allowable sequences to dimensions higher than 2. Finally, we provide geometric realizations of the s-weak order, a combinatorial structure that generalizes the weak order on permutations, parameterized by a vector s ∈ (Z>0)n. In particular, we answer Ceballos and Pons’s conjecture that the s-weak order can be realized as the edge-graph of a polytopal complex that is moreover a subdivision of a permutahedron.

[fra] Cette thèse concerne trois problèmes de réalisations géométriques de structures combinatoires par des polytopes et des subdivisions polyédrales. Un polytope est l'enveloppe convexe d'un ensemble fini de points dans un espace euclidíen R(d). Il est muni d'une structure combinatoire donnée par ses faces. Une subdivision est une collection de polytopes dont les faces s'íntersectent correctement et dont l'union est convexe. Elle est régulière si elle peut être obtenue en prenant les faces inférieures d'un relèvement de ses sommets dans une dimension de plus. Nous présentons d'abord une nouvelle construction géométrique d'un grand nombre de polytopes combinatoirement distincts, de dimension et nombre de sommets fixés. Cette construction consiste à montrer que certains polytopes admettent un grand nombre de triangulations régulières. Elle nous permet d'améliorer la meilleure borne inférieure connue sur le nombre de types combinatoires de polytopes. Nous étudions ensuite les projections du permutoèdre, nommées polytopes de balayage (sweep polytopes) parce qu'elles modélisent les manières d'ordonner une configuration de points fixée en balayant l’espace par des hyperplans dans une direction constante. Nous introduisons également et étud1ons une abstraction combinatoire de ces structures: les matroïdes orientés de balayage, qui généralisent en dimension supérieure à 2 la théorie des suites admissibles de Goodman et Pollack. Enfin, nous proposons des réalisations géométriques du s-ordre faible, une structure combinatoire qui généralise l'ordre faible sur les permutations, paramétrée par un vecteur s appartient à (Z>o)n. En particulier, nous résolvons une conjecture de Ceballos et Pons en montrant que le s-permutoedre peut être réalisé comme le graphe d'un complexe polytopal qui est une subdivision du permutoèdre.

[spa] Esta tesis se centra en tres problemas de realizaciones geométricas de estructuras combinatorias usando politopos y subdivisiones poliedrales. Un politopo es la envolvente convexa de un conjunto finito de puntos en un espacio Euclídeo JR.d_ Tiene una estructura combi­ natoria dada por sus caras. Una subdivisión es una colección de politopos cuyas caras se intersecan correctamente y cuya unión es convexa. Es regular si se puede obtener con las caras inferiores de un levantamiento de sus vértices en una dimensión más. Primero, presentamos una nueva construcción geométrica de un gran número de politopos combinatoriamente distintos, con dimensión y número de vértices fijados. Esta construcción consiste en mostrar que ciertos politopos admiten un gran número de triangulaciones regulares. Nos permite mejorar la mayor cota inferior conocida en el número de tipos combinatorios de politopos. A continuación estudiamos las proyecciones del permutaedro, llamadas politopos de barrido (sweep polytopes) porque modelan las posibles ordenaciones de una configuración de puntos fijada inducidas por el barrido con hiperplanos que recorren el espacio en una • dirección constante. Introducimos también y estudiamos una abstracción combinatoria de estas estructuras: las matroides orientadas de barrido, que generalizan en dimensión mayor que 2 la teoría de secuencias admisibles de Goodman y Pollack. Por último, proporcionamos realizaciones geométricas del s-orden débil, una estructura combinatoria que generaliza el orden débil en permutaciones, parametrizada por un vector s que pertenece a (Z>o)(t). En particular, resolvemos una conjetura de Ceballos y Pons mostrando que se puede realizar el s-permutaedro como el grafo de aristas de un complejo politopal que es una subdivisión del permutaedro.