Polyhedral and Convex Geometry

We present a complete computational classification of the combinatorial types of hyperplane sections, or slices, of the regular cube up to dimension six. For each dimension, we determine the exact number of distinct combinatorial types. When restricted to slices through the origin, our computations extend to dimension seven. The classification combines combinatorial, algebraic, and numerical techniques, with all results certified. Beyond enumeration, we analyze the distribution of types by number of vertices, establish new theoretical results about the combinatorics of slices of cubes, and propose conjectures motivated by our computational findings.

This article introduces the theory of Veronese polytopes, a broad generalisation of cyclic polytopes. These arise as convex hulls of points on curves with one or more connected components, obtained as the image of the rational normal curve in affine charts. We describe their facial structure by extending Gale’s evenness condition, and provide a further combinatorial characterisation of facets via σ-parity alternating sequences. Notably, we establish a bijective correspondence between combinatorial types of Veronese polytopes and partitions of finite sets equipped with a cyclic order, called circular compositions. We show that, although the only Veronese 3-polytopes are the cyclic 3-polytopes and the octahedron, in general dimension they form a rich and diverse class including all combinatorial types of simplicial d-polytopes with at most d+3 vertices, the cross-polytope and particular stacked polytopes. In addition, we characterise which curves defining Veronese polytopes are d-order curves, and provide a closed formula for the number of facets of any Veronese polytope.

We unify the study of quotients of matroids, polymatroids, valuated matroids and strong maps of submodular functions in the framework of Murota’s discrete convex analysis. As a main result, we compile a list of ten equivalent characterizations of quotients for M-convex sets, generalizing existing formulations for (poly)matroids and submodular functions. We also initiate the study of quotients of M-convex functions, constructing a hierarchy of four separate characterizations. Our investigations yield new insights into the fundamental operation of induction, as well as the structure of linking sets and linking functions, which are generalizations of linking systems and bimatroids.

In this paper we contribute to the frequently studied question of how to decompose a continuous piecewise linear (CPWL) function into a difference of two convex CPWL functions. Every CPWL function has infinitely many such decompositions, but for applications in optimization and neural network theory, it is crucial to find decompositions with as few linear pieces as possible. This is a highly challenging problem, as we further demonstrate by disproving a recently proposed approach by Tran and Wang [Minimal representations of tropical rational functions. Algebraic Statistics, 15(1):27-59, 2024]. To make the problem more tractable, we propose to fix an underlying polyhedral complex determining the possible locus of nonlinearity. Under this assumption, we prove that the set of decompositions forms a polyhedron that arises as intersection of two translated cones. We prove that irreducible decompositions correspond to the bounded faces of this polyhedron and minimal solutions must be vertices. We then identify cases with a unique minimal decomposition, and illustrate how our insights have consequences in the theory of submodular functions. Finally, we improve upon previous constructions of neural networks for a given convex CPWL function and apply our framework to obtain results in the nonconvex case.

We study the structure of the set of all possible affine hyperplane sections of a convex polytope. We present two different cell decompositions of this set, induced by hyperplane arrangements. Using our decomposition, we bound the number of possible combinatorial types of sections and craft algorithms that compute optimal sections of the polytope according to various combinatorial and metric criteria, including sections that maximize the number of \(k\)-dimensional faces, maximize the volume, and maximize the integral of a polynomial. Our optimization algorithms run in polynomial time in fixed dimension, but the same problems show hardness otherwise. Our tools can be extended to intersection with halfspaces and projections onto hyperplanes. Finally, we present several experiments illustrating our theorems and algorithms on famous polytopes.

We continue the study of intersection bodies of polytopes, focusing on the behavior of \(IP\) under translations of \(P\). We introduce an affine hyperplane arrangement and show that the polynomials describing the boundary of \(I(P+t)\) can be extended to polynomials in variables \(t ∈R^d\) within each region of the arrangement. In dimension 2, we give a full characterization of those polygons such that their intersection body is convex. We give a partial characterization for general dimensions.