We propose a new geometric method for measuring the quality of representations obtained from deep learning. Our approach, called "Random Polytope Descriptor", provides an efficient description of data points based on the construction of random convex polytopes. We demonstrate the use of our technique by qualitatively comparing the behavior of classic and regularized autoencoders. This reveals that applying regularization to autoencoder networks may decrease the out-of-distribution detection performance in latent space. While our technique is similar in spirit to k-means clustering, we achieve significantly better false positive/negative balance in clustering tasks on autoencoded datasets.
Joint work with Marek Kaluba and Lukas Ruff.
An empty simplex is a lattice simplex in which vertices are the only lattice points. After reviewing what is known about width of lattice polytopes and convex bodies, we show two constructions leading to the first known empty simplices of width larger than their dimension:(1) We introduce cyclotomic simplices and exhaustively compute all the cyclotomic simplices of dimension $10$ and volume up to $2^{31}$. Among them we find five empty ones of width $11$, and none of larger width.(2) Using circulant matrices of a very specific form, we construct empty simplices of arbitrary dimension $d$ and of width growing asymptotically as $d/$arcsinh$(1) \sim 1.1346\,d$.The width in part (2) is (asymptotically) only $3\%$ lower than the widest convex bodies known.This is joint work with Joseph Doolittle, Lukas Katthän, and Benjamin Nill.
Seventy three years ago, Richard Feynman introduced a diagrammatic formalism in Quantum Field Theory (QFT) to organize the expansion of a scattering amplitude as a sum of elementary rational functions, labeled by graphs. These graphs, now called Feynman Diagrams, revolutionized theoretical physics and are still widely used today.In using the scattering equations formalism to compute scattering amplitudes in terms of a Morse theoretic question posed on the Riemann sphere $\mathbb{CP}^{1}$, as introduced by Cachazo-He-Yuan in 2013, one can't help but feel that Feynman Diagrams should be living, breathing beings in their own right. Taking this idea seriously, in 2019, in joint work with Cachazo, Guevara and Mizera, we formulated an analog of the scattering equations on $\mathbb{CP}^{k-1}$, and introduced a generalized notion of scattering amplitudes: the generalized biadjoint scalar $m^{(k)}_n$. We found that, indeed, the set of Generalized Feynman Diagrams for the first new generalized amplitude $m^{(3)}_6$ should be understood as the set of maximal cones of the positive tropical Grassmannians $\text{Trop}^+G(3,6)$! This observation was quickly generalized to all $\text{Trop}^+G(k,n)$.In this talk, we will explore how a novel structure in combinatorial geometry, the matroidal blade arrangement, can be used to study the rays of the positive tropical Grassmannian by selecting, essentially canonically, a very special basis of height functions over the hypersimplex $\Delta_{k,n}$, and, in particular, to organize and represent the poles appearing in Generalized Feynman Diagrams for $m^{(k)}_n$. Applications include an appearance of weak separation as a compatibility condition for certain positroidal subdivisions of $\Delta_{k,n}$.
This talk deals with polytope theory in the context of an open problem concerning the expressivity of feedforward neural networks (NNs) with rectified linear unit (ReLU) activations. While it has been shown that NNs with logarithmic depth (in the input dimension) can represent any continuous, piecewise linear (CPWL) function, it is still unknown whether there exists any CPWL function that cannot be represented with three layers. In the first part of the talk, we present first progress towards depth lower bounds: based on mixed-integer linear programming we show that a 3-layer NN cannot compute the maximum of five scalar inputs under a natural, yet unproven assumption. In the second part, we explain how polytope theory might help to tackle the open problem via Newton polytopes of convex CPWL functions (aka tropical signomials). This is joint work in progress with Amitabh Basu, Marco Di Summa, and Martin Skutella.
Generalized permutahedra are a class of polytopes with many interesting combinatorial subclasses. We introduce pruned inside-out polytopes, a generalization of inside-out polytopes introduced by Beck--Zaslavsky (2006), which have many applications such as recovering the famous reciprocity result for graph colorings by Stanley.
We study the integer point count of pruned inside-out polytopes by applying classical Ehrhart polynomials and Ehrhart--Macdonald reciprocity. This yields a geometric perspective on and a generalization of a combinatorial reciprocity theorem for generalized permutahedra by Aguiar--Ardila (2017) and Billera--Jia--Reiner (2009).
Applying this reciprocity theorem to hypergraphic polytopes allows us to give an arguably simpler proof of a recent combinatorial reciprocity theorem for hypergraph colorings by Aval--Karaboghossian--Tanasa (2020).
Ardila-Benedetti-Doker showed that any generalized permutahedron is a signed Minkowski sum of the faces of the standard simplex. In contrast, Ardila-Castillo-Eur-Postnikov observed that the faces of the cross-polytope only generate a subspace of roughly half the dimension in the space of deformations of the type B permutahedron. In this talk, I will use McMullen's polytope algebra to help explain this phenomenon. Concretely, I will consider the subalgebra generated by (type B) generalized permutahedra and endow it with the structure of a module over the Tits algebra of the corresponding Coxeter arrangement. The module structure surprisingly reveals that any family of generators (via signed Minkowski sums) for generalized permutahedra of type B will contain at least $2^{d-1}$ full-dimensional polytopes. I will present a family of generators that shows that this lower bound is sharp.
Polynomial capacity has been used in the past 20 years to obtain lower bounds on various combinatorial quantities, including the permanent, the mixed discriminant, matchings of a graph, and the intersection of two matroids (to name a few). In joint work with Petter Brändén and Igor Pak, we have recently used capacity to obtain improved lower bounds on the number of contingency tables with given marginals. Contingency tables can be viewed as the lattice points of transportation polytopes and flow polytopes more generally, and so these lower bounds imply volume lower bounds for such polytopes. In this talk, we state these bounds and discuss a few key points of their proofs.
Generalized permutahedra form a combinatorially rich class of polytopes that appear naturally in various areas of mathematics. They include many interesting and significant classes of polytopes such as matroid polytopes. We study functions on generalized permutahedra that behave linearly with respect to dilation and taking Minkowski sums. We present classification results and discuss how these can be applied to prove positivity of the linear coefficient of the Ehrhart polynomial of generalized permutahedra.
This is joint work with Mohan Ravichandran.
The Ehrhart quasipolynomial of a rational polytope P encodes fundamental arithmetic data of P, namely, the number of integer lattice points in positive integral dilates of P. Ehrhart quasipolynomials were introduced in the 1960s, satisfy several fundamental structural results and have applications in many areas of mathematics and beyond. The enumerative theory of lattice points in rational (equivalently, real) dilates of rational polytopes is much younger, starting with work by Linke (2011), Baldoni-Berline-Koeppe-Vergne (2013), and Stapledon (2017). We introduce a generating-function ansatz for rational Ehrhart quasipolynomials, which unifies several known results with classical Ehrhart quasipolynomials, as well as generalized reflexive polytopes studied by Fiset-Kasprzyk (2008) and Kasprzyk-Nill (2012). This is joint work with Sophia Elia and Sophie Rehberg.
The normalized volume of the classical permutahedron is given by the formula $n^{n-2}$ which, ask any combinatorialist and they will tell you, agrees with the number of trees on n vertices.This coincidence is well understood; the classical permutahedron is a unimodular zonotope, on the set of positive roots of the Symmetric group $S_n$, and its bases are indexed by trees and hence enumerated by the determinant of a Laplacian matrix. This description of the permutahedron lends itself to a natural generalization: for a Weyl group W, the zonotope associated to the collection of positive roots of W will be called the root zonotope $Z_W$. These zonotopes $Z_W$ are not unimodular, but their bases can be differentiated with respect to the reflection subgroup they generate (and its connection index). In joint work with Guillaume Chapuy (arxiv.2012.04519) we have introduced for any Weyl group W a (nxn) Laplacian matrix $L_W$ whose spectrum encodes (nontrivially) many enumerative properties of W. In particular we will present new short formulas (ibid: Section 8.3) for the volumes of the root zonotopes $Z_W$ involving only the Coxeter numbers of W and its reflection subgroups. Our approach is uniform and does not rely on the classification.
Permutreehedra are polytopes that interpolate between the permutahedron, the associahedron and the cube. They were constructed as removahedra, i.e. by deleting inequalities in the facet description of the classical permutahedron. We investigate the type cone (the space of polytopal realizations) of permutree fans and prove that this removahedral construction works starting from any realization of the braid fan.
In general dimension the edge-graph of a polytope carries very little information about the polytope itself. For example, the edge-graph can have many more symmetries than the polytope or any realization thereof.
Using techniques from spectral graph theory and convex geometry we show that the edge-graph of every polytope can be colored so that every combinatorial symmetry of the colored edge-graph extends to a geometric symmetry of the polytope.
Up to now, the only proof known of this fact makes use of spectral graph theory and demonstrates the usefulnes of this seemingly unrelated subject in the study of polytopes.
The Ehrhart polynomial of a polytope counts the number of lattice points in every integer dilation of the polytope. A conjecture of De Loera et al. states that if the polytope is a matroid polytope, then these polynomials have positive coefficients. For uniform matroids it is indeed true, because in fact in that case the polytopes are hypersimplices. We will also discuss some purely matroidal operations that behave nicely with the Ehrhart polynomial of a matroid and discuss further conjectures and results on the matter.
Kazhdan-Lusztig varieties are defined by ideals generated by certain minors of a matrix, which are chosen by a combinatorial rule. These varieties are of interest in commutative algebra and Schubert varieties. Each Kazhdan-Lusztig variety has a natural torus action from which one can construct a polytope. The complexity of this torus action can be computed from the dimension of the polytope and, in some sense, indicates how close the geometry of the variety is to the combinatorics of the associated polytope. In joint work with Maria Donten-Bury and Irem Portakal we address the problem of classifying which Kazhdan-Lusztig varieties have a given complexity. We do so by utilizing the rich combinatorics of Kazhdan-Lusztig varieties, which is reflected on the polytopes.
A closed PL-curve is called integral if it is comprised of unit intervals. Kenyon's problem asks whether for every integral curve $\gamma$ in the $3$-dimensional euclidean space, there is a dome over $\gamma$, i.e. whether $\gamma$ is a boundary of a polyhedral surface whose faces are equilateral triangles with unit edge lengths. I will survey both positive and negative results on the subject. Joint work with Alexey Glazyrin.
My plan is to talk about the value of examplesthe value and the limits of enumerationour limited tool-box of construction methodsthe challenges of explicit constructionsthe value of counter-examples the value and challenges of numerical computationin polytope theory and to illustrate this with some of my favourite (open and solved) polytope problems from the last 35 years.
A polytope $P$ is inscribable if there is a combinatorially equivalent polytope $P'$ with all vertices contained in a sphere. This notion relates to the combinatorics of ideal hyperbolic polytopes and Delaunay subdivisions. Steinitz showed that not every polytope is inscribable and Rivin gave a complete and effective characterization for $3$-dimensional polytopes. There is no such characterization in dimensions $4$ and up. I will discuss the related notion of normally inscribable polytopes: A polytope $P$ is normally inscribable if there is a normally equivalent polytope $P'$ with all vertices on a sphere. Normal inscribability, it turns out, reveals a fascinating interplay of algebra, geometry, and combinatorics. I will explain connections to a deformation theory of ideal hyperbolic polytopes and Delaunay subdivisions, routed particle trajectories, and reflection groupoids. In particular, for zonotopes, this reveals new connections to reflection groups and Grünbaum's quest for simplicial arrangements. This is based on joint work with Sebastian Manecke.
Schubert polynomials are multivariate polynomials representing cohomology classes on the flag manifold. Despite the beautiful formulas developed for them over the past three decades, the coefficients of these polynomials remained mysterious. I will explain Schubert polynomials from a polytopal point of view, answering, at least partially, the questions: Which coefficients are nonzero? How do the coefficients compare to each other in size? Are the Newton polytopes of these polynomials saturated? Are their coefficients log-concave along lines? Is there a polytope whose integer point transform specializes to Schubert polynomials? As the questions themselves suggest, we will find that polytopes play an outsized role in our understanding. The talk is based on joint works with Alex Fink, June Huh, Ricky Liu, Jacob Matherne and Avery St. Dizier.
We present joint work with Anna-Laura Sattelberger at the interface of geometric combinatorics and differential algebra. We show how stable set polytopes of certain regular triangulations arise naturally in the study of jet schemes of monomials.
We give a Brion-type formula for the weighted enumeration of lattice points in a polytope. The weighting has combinatorial significance, and also arises from the arc scheme of the associated toric variety. We obtain some new and old identities of q-series as consequences.
In the early 1990s, Billera and Sturmfels introduced monotone path polytopes (MPPs). MPPs encode the combinatorial structure of paths potentially chosen by the simplex method to solve a linear program on a given polytope for a fixed linear functional. In their original paper, they showed that MPPs of simplices and cubes for any generic linear functional are combinatorial cubes and permutahedra respectively. The natural next question to ask is: What are the MPPs of cross-polytopes for generic linear functionals? I will present a complete characterization of MPPs of cross-polytopes for generic linear functionals and show how this result informs our understanding of MPPs of centrally symmetric polytopes. This talk is based on joint work with Jesús De Loera.
Matroids are combinatorial objects that generalize the notion of independence, and their subdivisions have rich connections to geometry. Thus we are often interested in functions on matroids that behave nicely with respect to subdivisions, which are called valuations. Matroids are naturally linked to the symmetric group; generalizing to other finite reflection groups gives rise to Coxeter matroids. I will give an overview of these ideas and then present some work with Chris Eur and Mario Sanchez on constructing the universal valuative invariant of Coxeter matroids. Since matroids and their Coxeter analogues can be understood as families of polytopes with special combinatorial properties, I will present these results from a polytopal perspective.
A classic problem connecting algebraic and geometric combinatorics is the realization problem: given a poset (with a reasonable structure), determine whether there exists a polytope whose face lattice it the poset. In 1990s, Kapranov defined a poset called permuto-associhedron as a hybrid between the face poset of the permutohedron and the associahedron, and he asked whether this poset is realizable. Shortly after his question was posed, Reiner and Ziegler provided a realization. In this talk, I will discuss a different construction we obtained as a deformations of nested permutohedra.
For any lattice congruence of the weak order on permutations, N. Reading proved that glueing together the cones of the braid fan that belong to the same congruence class defines a complete fan, called quotient fan, and V. Pilaud and F. Santos showed that it is the normal fan of a polytope, called quotientope. In this talk, I will present an alternative simpler approach to realize this quotient fan based on Minkowski sums of elementary polytopes, called shard polytopes, which have remarkable combinatorial and geometric properties. In contrast to the original construction of quotientopes, this Minkowski sum approach extends to type B. This is joint work with Vincent Pilaud and Julian Ritter.
The normal fan of a simple zonotope is a simplicial hyperplane arrangement. In rank 3 there is still much to learn about these arrangements. We provide an updated catalogue of the currently known simplicial hyperplane arrangements of rank 3, and compute normals and invariants of the arrangements. Additionally, we determine whether the associated posets of regions possess the combinatorial property of "congruence normality," which hints at potential geometric interpretations. We use methods from oriented matroids that make the computations possible. This refines the structure of the catalogue, breaking it into three separate combinatorial categories. In particular, we show that arrangements stemming from finite Weyl groupoids have congruence normal posets of regions. This is joint work with Michael Cuntz and Jean-Philippe Labbé.
Results of Koebe (1936), Schramm (1992), and Springborn (2005) yield realizations of three dimensional polytopes with edges tangent to the unit sphere. In this talk we introduce the study of algebraic degrees of such realizations. We will show how these notions provide algebraic complexity measures reflecting the combinatorics of the polytopes. Joint work with Mara Belotti and Michael Joswig.
It is known that the sectional genus of a polarized variety has an upper bound, which is an extension of the Castelnuovo bound on the genus of a projective curve. Polarized varieties whose sectional genus achieves this bound are called Castelnuovo. On the other hand, there is a one-to-one correspondence between full-dimensional lattice polytopes and polarized toric varieties and we call a lattice polytope Castelnuovo if the associated polarized toric variety is Castelnuovo. In this talk, I give a combinatorial characterization of Castelnuovo polytopes and an application of this characterization.
Consider a configuration of n labeled points in a Euclidean space. Any linear functional gives an ordering of these points: an ordered partition that we call a sweep, because we can imagine its parts as the sets of points successively hit by a sweeping hyperplane. The set of all such sweeps forms a poset which is isomorphic to a polytope, called the sweep polytope.
I will present several constructions of the sweep polytope, related to zonotopes, projections of permutahedra and monotone path polytopes of zonotopes.
This structure can also be generalized in terms of oriented matroids. For oriented matroids that admit a sweep oriented matroid, we gain precision on the topological description of their poset of cellular strings, refining a particular case of the Generalized Baues Problem.
This is joint work with Arnau Padrol.
About fifteen years ago F. Brenti and V. Welker asked whether the face enumerating polynomial of the barycentric subdivision of any convex polytope has only real roots and showed that this is the case for simplicial polytopes. Until very recently, no strong evidence had been provided in the literature that such a result may hold beyond the simplicial case. This talk will give an affirmative answer for another important class of convex polytopes, namely that of cubical polytopes, and will discuss some related topics.
Given a graph $G=(V,E)$, the maximum bond problem searches for a maximum cut $\delta(S)\subseteq E$ with $S\subseteq V$ such that $G[S]$ and $G[V\setminus S]$ are connected. This problem is closely related to the well-known maximum cut problem and known under a variety of names such as largest bond, maximum minimal cut and maximum connected (sides) cut. The bond polytope is the convex hull of all incidence vectors of bonds. Similar to the connection of the corresponding optimization problems, the bond polytope is closely related to the cut polytope. While cut polytopes have been intensively studied, there are no results on bond polytopes. We start a structural study of the latter.We investigate the relation between cut- and bond polytopes and study the effect of graph modifications on bond polytopes and their facets. Moreover, we study facet-defining inequalities arising from edges and cycles for bond polytopes. In particular, these yield a complete linear description of bond polytopes of cycles and $3$-connected planar $(K_5-e)$--minor free graphs. This is joint work with Markus Chimani and Alexander Nover.
The Stanley-Reisner ring R of any simplicial complex contains a "universal" family of elements that form an h.s.o.p. (homogeneous system of parameters): the elementary symmetric functions in the vertex variables. This talk will discuss an interesting depth-detection property of this universal h.s.o.p., as well as a conjecture on the shape of the minimal free resolution of the ring R over this universal parameter ring. This conjecture is closely connected to a generalization of Hochster's formula on resolutions of Stanley-Reisner rings, one that applies to any proper vertex-coloring of the simplicial complex.
In our work with Graham Denham and June Huh on the Lagrangian geometry of matroids, we introduced the conormal fan of a matroid M. Using tools from combinatorial Hodge theory, we used this fan to prove Brylawski and Dawson's conjectures on the log-concavity of the h-vector of the broken circuit and the independence complex of M. Two $(2n-2)$-dimensional polytopes with $3^n-3$ facets arose in our investigation of conormal fans: the bipermutohedron and the harmonic polytope. The bipermutohedron has $(2n)!/2^n$ vertices. Its h-polynomial is an analog of the Eulerian polynomial. It is real-rooted, and hence its coefficients are log-concave and unimodal. The harmonic polytope has $(n!)^2(1+1/2+…+1/n)$ vertices. Its volume is a combination of the degrees of the projective varieties of all the toric ideals of connected bipartite graphs with n edges. My talk will discuss these combinatorial constructions. The work on the harmonic polytope is joint with Laura Escobar.