Matroids : h-vectors, zonotopes, and Lawrence polytopes

Abstract

The main objects of study in this thesis are matroids. In particular we are interested in three particular classes matroids: regular matroids, arithmetic matroids, and internally perfect matroids. Of these families, regular matroids are the oldest and most well-known. In contrast, arithmetic matroids are relatively new structures that simultaneously capture combinatorial and geometric invariants of rational vector configurations. We introduce the class of internally perfect matroids in order to use the structure of the internal order of such a matroid to prove Stanley's conjecture that (under a certain assumption) any h-vector of a matroid is a pure O-sequence in this case. The thesis is structured as follows. We give all relevant background information in Chapter 1. In Chapter 2 we give a new proof of a generalization of Kirchoff's matrix-tree theorem to regular matroids. After recasting the problem into the world of polyhedral geometry via two zonotopes determined by a regular matroid, we reprove the theorem by showing that the volumes of these zonotopes are equal by providing an explicit bijection between the points in them (up to a set of measure zero). We then generalize to the weighted case, and conclude by using our technique to reprove the the classical matrix-tree theorem by working out the details when the matrices involved have rank-plus-one many rows. This chapter is joint work with Julian Pfeifle. In Chapter 3 we exploit a well-known connection between the zonotope and Lawrence polytope generated by a fixed integer representation of a rational matroid to prove relations between various polynomials associated to these two polytopes and the underlying matroid. First we prove a relationship between the Ehrhart polynomial of the zonotope and the numerator of the Ehrhart series of the Lawrence polytope. On the level of arithmetic matroids, this relation allows us to view the numerator of the Ehrhart series of the Lawrence polytope as the arithmetic matroid analogue of the usual matroid h-vector of the matroid. After proving the previous result, we use it to give a new interpretation of the coefficients of a certain evaluation of the arithmetic Tutte polynomial. Finally, we give a new proof that the h-vector of the matroid and the numerator of the Ehrhart series of the Lawrence polytope coincide when the matrix representing the matroid is unimodular. In Chapter 4, we consider a new class of matroids consisting of those matroids whose internal order makes them especially amenable to proving Stanley's conjecture. Stanley's conjecture states that for any matroid there exists a pure order ideal whose O-sequence coincides with the h-vector of the matroid. We give a brief review of known results in Section 4.1 before turning to ordered matroids and the internal order in Section 4.2, where we also define internally perfect bases and matroids. In Section 4.3 we first prove preliminary results about internally perfect bases culminating in Theorem 4.11 in which we show that, under a certain assumption, any internally perfect matroid satisfies Stanley's conjecture. Moreover, we conjecture that the assumption in the previous sentence holds for all internally perfect matroids.

El principal objeto de estudio de la presente tesis son las matroides, que generalizan propiedades de matrices a un contexto más combinatorio. Nos interesaremos principalmente por tres clases particulares: matroides regulares, matroides aritméticas, y matroides internamente perfectas. De estas famílias, las matroides regulares son las mejor estudiadas. En cambio, las matroides aritméticas son estructuras relativamente nuevas que capturan simultáneamente invariantes combinatorias y geométricas de configuraciones racionales de vectores. Introducimos en esta tesis la clase de matroides internamente perfectas, que nos permiten usar la estructura del orden interno de dichas matroides para probar, en este caso y suponiendo la veracidad de una afirmación, la conjetura de Stanley que cualquier h-vector de una matroide es una O-secuencia pura. Esta tesis está estructurada de la siguiente forma. En el Capítulo 1 damos los antecedentes relevantes. En el Capítulo 2 ofrecemos una nueva demostración de una generalización del teorema de Kirchhoff. Después reestructuramos el problema en el mundo de la geometría poliédrica a través de dos zonotopos determinados por una matroide regular, demostrando que los volúmenes de estos zonotopos son iguales, y construyendo una biyección explícita entre ellos (fuera de un conjunto de medida cero). Generalizamos entonces al caso de una matroide con pesos. Concluimos mostrando que nuestra técnica pude ser usada para volver a demostrar el teorema clásico de Kirchhoff, puliendo los detalles cuando las matrices tienen corrango igual a uno. Este capítulo es fruto de trabajo conjunto con Julian Pfeifle. En el Capítulo 3 sacamos provecho de una conexión entre el zonotopo y el politopo de Lawrence generado por una representación íntegra (con coeficientes enteros) de una matroide racional para probar relaciones entre varios polinomios asociados con ellos. Primero demostramos una relación entre el polinomio de Ehrhart del zonotopo y el numerador de la serie de Ehrhart del politopo de Lawrence. Al nivel de matroides aritméticas esta relación nos permite ver el numerador de la serie de Ehrhart del politopo de Lawrence como el análogo, para matroides aritméticas, del usual h-vector de la matroide. Después de demostrar el resultado mencionado, lo usamos para ofrecer una nueva interpretación de los coeficientes de una evaluación particular del polinomio aritmético de Tutte. Finalmente mostramos que el h-vector de la matroide y la serie de Ehrhart del politopo de Lawrence coinciden cuando la representación es unimodular. En el Capítulo 4 consideramos una nueva clase de matroides, cuyo orden interno las vuelve especialmente dispuestas para demostrar la conjetura de Stanley. Esta conjetura dice que para cualquier matroide existe un ideal de orden puro cuya O-secuencia coincide con el h-vector de la matroide. Damos un breve repaso de los resultados conocidos en la Sección 4.1 antes de enfocarnos en las matroides ordenadas y el orden interno en la Sección 4.2, donde también definimos las bases y matroides internamente perfectas. En la Sección 4.3 probamos resultados preliminares sobre bases internamente perfectas culminando en el Teorema 4.11, dónde mostramos que, suponiendo la veracidad de cierta afirmación, cualquier matroide perfecta satisface la conjetura de Stanley. Por otra parte, conjeturamos que esta afirmación, en efecto, es válida para todas las matroides internamente perfectas.