| dc.description.abstract | A \emph{matroid} is a combinatorial structure that provides an abstract and flexible model for dependence relations between elements of a set. One way of studying matroids is via geometry: one associates a polytope to a matroid, then uses both combinatorics and geometry to understand the polytope and thereby the original matroid. By a \emph{polytope}, we mean a bounded convex set in Euclidean space $\mathbb{R}^n$ defined by a finite list of linear equations and inequalities, or equivalently as the convex hull of a finite set of points. The best-known polytope associated with a matroid $M$ is its \emph{base polytope} $P(M)$, first introduced by Gel'fand, Goresky, Macpherson and Serganova in 1987~\cite{GGMS}. This dissertation focuses on a closely related construction, the \emph{independence polytope} $Q(M)$, whose combinatorics is much less well understood. Both $P(M)$ and $Q(M)$ are defined as convex hulls of points corresponding to the bases or independence sets, respectively; defining equations and inequalities were given for $P(M)$ by Feichtner and Sturmfels~\cite{Feichtner_Sturmfels} in terms of the ``flacets'' of $M$, and for $Q(M)$ by Schrijver~\cite{Schrijver_B}. One significant difference between the two constructions is that matroid basis polytopes are \emph{generalized permutahedra} as introduced by Postnikov \cite{Beyond}, but independence polytopes do not \emph{a priori} share this structure, so that fewer tools are available in their study. One of the fundamental questions about a polytope is to determine its combinatorial structure as a cell complex: what are its faces of each dimension and which faces contain others? In general it is a difficult problem to extract this combinatorial structure from a geometric description. For matroid base polytopes, the edges (one-dimensional faces) have a simple combinatorial descriptions in terms of the defining matroid, but faces of higher dimension are not understood in general. In Chapter~2 we give an exact combinatorial and geometric description of all the one- and two-dimensional faces of a matroid independence polytope (Theorems~\ref{theorem: Edge Theorem} and ~\ref{theorem: 2 Faces}). One consequence (Proposition~\ref{prop: is a gen perm}) is that matroid independence polytopes can be transformed into generalized permutahedra with no loss of combinatorial structure (at the cost of making the geometry slightly more complicated), which may be of future use. In Chapter~3 we consider polytopes arising from \emph{shifted matroids}, which were first studied by Klivans~\cite{Klivans_Thesis, Klivans_paper}. We describe additional combinatorial structures in shifted matroids, including their circuits, inseparable flats, and flacets, leading to an extremely concrete description of the defining equations and inequalities for both the base and independence polytopes (Theorem~\ref{theorem: pièce de résistance}). As a side note, we observe that shifted matroids are in fact \emph{positroids} in the sense of Postnikov~\cite{Positroid_Postnikov}, although we do not pursue this point of view further. Chapter~4 considers an even more special class of matroids, the \emph{uniform matroids} $U(r,n)$, whose independence polytopes $TC(r,n)=Q_U(r,n)$ are hypercubes in $\Rr^n$ truncated at ``height''~$r$. These polytopes are strongly enough constrained that we can study them from the point of view of Ehrhart theory. For a polytope $P$ whose vertices have integer coordinates, the function $i(P,t) = |tP\cap\Zz^n|$ (that is, the number of integer points in the $t^{th}$ dilate) is a polynomial in $t$ \cite{OG_Ehrhart}, called the \emph{Ehrhart polynomial}. We give two purely combinatorial formulas for the Ehrhart polynomial of $TC(r,n)$, one a reasonably simple summation formula (Theorem~\ref{thm: Ehrhart_Polynomial_Truncated_Cube}) and one a cruder recursive version (Theorem \ref{theorem: Gross_Formula}) that was nonetheless useful in conjecturing and proving the ``nicer'' Theorem~\ref{thm: Ehrhart_Polynomial_Truncated_Cube}. We observe that another fundamental Ehrhart-theoretic invariant, the \emph{$h^*$-polynomial} of $TC(r,n)$, can easily be obtained from work of Li~\cite{Nan_Li} on closely related polytopes called \emph{hyperslabs}. Having computed these Ehrhart polynomials, we consider the location of their complex roots. The integer roots of $i(Q_M,t)$ can be determined exactly even for arbitrary matroids (Theorem \ref{thm: Integer_Roots}), and extensive experimentation using Sage leads us to the conjecture that for all $r$ and $n$, all roots of $TC(r,n)$ have negative real parts. We prove this conjecture for the case $r=2$ (Theorem \ref{thm: Conj_r=2}), where the algebra is manageable, and present Sage data for other values in the form of plots at the end of Chapter~4. | |
