#### Date Available

12-7-2015

#### Year of Publication

2015

#### Degree Name

Doctor of Philosophy (PhD)

#### Document Type

Doctoral Dissertation

#### College

Arts and Sciences

#### Department/School/Program

Mathematics

#### First Advisor

Dr. Benjamin Braun

#### Second Advisor

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 *K*_{5} 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*