Abstract: The study of the cone of submodular functions goes back to Jack Edmonds' seminal 1970 paper, which already highlighted the difficulty of characterizing its extreme rays. Since then, researchers from diverse fields have sought to characterize, enumerate, and bound the number of such rays. In this paper, we introduce an inductive construction that generates new rays of the submodular cone. This allows us to establish that the $n$-th submodular cone has at least $2^{2^{n-2}}$ rays, which improves upon the lower bound obtained from Hien Q. Nguyen's 1986 characterization of indecomposable matroid polytopes by a factor of order $\sqrt{n^3}$ in the exponent.

Abstract: A polytope is indecomposable if it cannot be expressed (non-trivially) as a Minkowski sum of other polytopes. Certifying indecomposability is difficult, and several criteria have been developed since Gale introduced the concept in 1954. Our first contribution is a new indecomposability criterion that encompasses most of the previous techniques. The major new ingredient is the introduction of the (extended) graph of edge-length dependencies, which has diverse applications in the study of deformation cones of polytopes. Our main motivation is to provide new indecomposable deformed permutahedra that are not matroid polytopes. In 1970, Edmonds proposed the problem of characterizing the extreme rays of the submodular cone, that is, indecomposable deformed permutahedra. Matroid polytopes from connected matroids give one such family of polytopes. We present a new infinite disjoint family via truncations of certain graphical zonotopes. This way, we obtain $2 \lfloor (n-1)/2 \rfloor$ new indecomposable deformations of the n-permutahedron $\Pi_n \subseteq \mathbb{R}^n$.

Abstract: Counting lattice points and triangulating polytopes are prominent subjects in discrete geometry, yet proving Ehrhart positivity or the existence of unimodular triangulations remain of utmost difficulty in general, even for "easy" simplices. Inspired by a question of Olsen, we present a natural new class of sequences s for which the s-lecture hall simplices are not Ehrhart positive, by explicitly estimating a negative coefficient. Meanwhile, motivated by a conjecture of Hibi, Olsen and Tsuchiya, we extend the previously known classes of sequences s for which the s-lecture hall simplices admit flag, regular, and unimodular triangulations. The triangulations we construct are explicit.

Abstract: To solve a linear program, the simplex method follows a path in the graph of a polytope, on which a linear function increases. The length of this path is an key measure of the complexity of the simplex method. Numerous previous articles focused on the longest paths, or, following Borgwardt, computed the average length of a path for certain random polytopes. We detail more precisely how this length is distributed, i.e., how many paths of each length there are. It was conjectured by De Loera that the number of paths counted according to their length forms a unimodal sequence. We give examples (old and new) for which this holds; but we disprove this conjecture by constructing counterexamples for several classes of polytopes. However, De Loera is "statistically correct": We prove that the length of coherent paths on a random polytope (with vertices chosen uniformly on a sphere) admits a central limit theorem.

Abstract: The monotone path polytope of a polytope P encapsulates the combinatorial behavior of the shadow vertex rule (a pivot rule used in linear programming) on P. On the other hand, computing monotone path polytopes is the entry door to the larger subject of fiber polytopes, for which explicitly computing examples remains a challenge. Monotone path polytopes of cubes and simplices have been known since the seminal article of Billera and Strumfels 1992. We (partially) extend these results to hypersimplices by linking this problem to the combinatorics of lattice paths. Indeed, we give a combinatorial model to describe the vertices of the monotone path polytope of the hypersimplex Δ(n, 2) (for any generic direction). With this model, we give a precise count of these vertices, and furthermore count the number of coherent monotone paths on Δ(n, 2) according to their lengths. We prove that some of the results obtained also hold for hypersimplices Δ(n, k) for k ≥ 2

Abstract: We provide a piecewise linear isomorphism from the normal fan of the pivot polytope of a product of simplices to the normal fan of a shuffle of associahedra.

Abstract: In this paper, we compute a triangulation of certain faces of the submodular cone. More precisely, graphical zonotopes are generalized permutahedra, and hence are associated to faces of the submodular cone. We give a triangulation of these faces for graphs without induced complete sub-graph on 4 vertices. This grants us access to the rays of these faces: Minkowski indecomposable deformations of these graphical zonotopes are segments and triangles. Besides, computer experiments lead to examples of graphs without induced complete sub-graph on 5 vertices, whose graphical zonotopes have high dimensional Minkowski indecomposable deformations.

Abstract: A hypergraphic polytope is a Minkowski sum of faces of the standard simplex. We study deformations of two fundamental families of hypergraphic polytopes: the graphical zonotopes and the nestohedra. Namely, we provide irredundant facet descriptions for the deformation cones of these polytopes. Moreover, we show that the faces of the standard simplex contained in the deformation cone provide a linear basis of its vector span, a result that extends to any hypergraphic polytope.

Abstract: We study deformations of graphical zonotopes. Deformations of the classical permutahedron (which is the graphical zonotope of the complete graph) have been intensively studied in recent years under the name of generalized permutahedra. We provide an irredundant description of the deformation cone of the graphical zonotope associated to a graph G, consisting of independent equations defining its linear span (in terms of non-cliques of G) and of the inequalities defining its facets (in terms of common neighbors of neighbors in G). In particular, we deduce that the faces of the standard simplex corresponding to induced cliques in G form a linear basis of the deformation cone, and that the deformation cone is simplicial if and only if G is triangle-free.

Abstract: We give the facet description of the deformation cones of graph associahedra and nestohedra, generalizing the classical parametrization of the family of deformed permutahedra by the cone of submodular functions. When the underlying building set is made of intervals, this leads in particular to the construction of kinematic nestohedra generalizing the kinematic associahedra that recently appeared in the theory of scattering amplitudes.