AbstractsLaw & Legal Studies

Matroids : h-vectors, zonotopes, and Lawrence polytopes

by Aaron Matthew Dall

Institution: Universitat Polit├Ęcnica de Catalunya
Year: 2015
Record ID: 1125692
Full text PDF: http://hdl.handle.net/10803/286280


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…