Complexity of linear relaxations in integer programming.

For a set X of integer points in a polyhedron, the smallest number of facets of any polyhedron whose set of integer points coincides with X is called the relaxation complexity  rc ( X ) . This parameter, introduced by Kaibel & Weltge (2015), captures the complexity of linear descriptions of X without using auxiliary variables. Using tools from combinatorics, geometry of numbers, and quantifier elimination, we make progress on several open questions regarding rc ( X ) and its variant rc Q ( X ) , restricting the descriptions of X to rational polyhedra. As our main results we show that rc ( X ) = rc Q ( X ) when: (a) X is at most four-dimensional, (b) X represents every residue class in ( Z / 2 Z ) d , (c) the convex hull of X contains an interior integer point, or (d) the lattice-width of X is above a certain threshold. Additionally, rc ( X ) can be algorithmically computed when X is at most three-dimensional, or X satisfies one of the conditions (b), (c), or (d) above. Moreover, we obtain an improved lower bound on rc ( X ) in terms of the dimension of X.

The Covering Radius and a Discrete Surface Area for Non-Hollow Simplices.

We explore upper bounds on the covering radius of non-hollow lattice polytopes. In particular, we conjecture a general upper bound of d/2 in dimension d, achieved by the "standard terminal simplices" and direct sums of them. We prove this conjecture up to dimension three and show it to be equivalent to the conjecture of González-Merino and Schymura (Discrete Comput. Geom. 58(3), 663-685 (2017)) that the d-th covering minimum of the standard terminal n-simplex equals d/2, for every n ≥ d . We also show that these two conjectures would follow from a discrete analog for lattice simplices of Hadwiger's formula bounding the covering radius of a convex body in terms of the ratio of surface area versus volume. To this end, we introduce a new notion of discrete surface area of non-hollow simplices. We prove our discrete analog in dimension two and give strong evidence for its validity in arbitrary dimension.

Tropical Ehrhart theory and tropical volume.

We introduce a novel intrinsic volume concept in tropical geometry. This is achieved by developing the foundations of a tropical analog of lattice point counting in polytopes. We exhibit the basic properties and compare it to existing measures. Our exposition is complemented by a brief study of arising complexity questions.