Date Available
12-7-2015
Year of Publication
2015
Document Type
Doctoral Dissertation
Degree Name
Doctor of Philosophy (PhD)
College
Arts and Sciences
Department/School/Program
Mathematics
Advisor
Dr. Benjamin Braun
Co-Director of Graduate Studies
Dr. Carl Lee
Abstract
In this dissertation, we exhibit two instances of polyhedra in combinatorial convex geometry. The first instance arises in the context of Ehrhart theory, and the polyhedra are the central objects of study. The second instance arises in algebraic statistics, and the polyhedra act as a conduit through which we study a nonpolyhedral problem.
In the first case, we examine combinatorial and algebraic properties of the Ehrhart h*-polynomial of the r-stable (n,k)-hypersimplices. These are a family of polytopes which form a nested chain of subpolytopes within the (n,k)-hypersimplex. We show that a well-studied unimodular triangulation of the (n,k)-hypersimplex restricts to a triangulation of each r-stable (n,k)-hypersimplex within. We then use this triangulation to compute the facet-defining inequalities of these polytopes. In the k=2 case, we use shelling techniques to devise a combinatorial interpretation of the coefficients of the h*-polynomials in terms of independent sets of certain graphs. From this, we then extract some results on unimodality. We also characterize the Gorenstein r-stable (n,k)-hypersimplices, and we conclude that these also have unimodal h*-polynomials.
In the second case, for a graph G on p vertices we consider the closure of the cone of concentration matrices of G. The extreme rays of this cone, and their associated ranks, have applications in maximum likelihood estimation for the undirected Gaussian graphical model associated to G. Consequently, the extreme ranks of this cone have been well-studied. Yet, there are few graph classes for which all the possible extreme ranks are known. We show that the facet-normals of the cut polytope of G can serve to identify extreme rays of this nonpolyhedral cone. We see that for graphs without K5 minors each facet-normal of the cut polytope identifies an extreme ray in the cone, and we determine the rank of this extreme ray. When the graph is also series-parallel, we find that all possible extreme ranks arise in this fashion, thereby extending the collection of graph classes for which all the possible extreme ranks are known.
Digital Object Identifier (DOI)
http://dx.doi.org/10.13023/ETD.2016.014
Recommended Citation
Solus, Liam, "Polyhedral Problems in Combinatorial Convex Geometry" (2015). Theses and Dissertations--Mathematics. 32.
https://uknowledge.uky.edu/math_etds/32
ETD Approval Form
solus_liam_proquest.pdf (623 kB)
Proquest Form
solus_liam_SED_completion_confirm.pdf (149 kB)
Confirmation of completion of SED survey
