Polytopes and Friends - Abstracts
Talks
Monday
Georg Loho: Lower bounds for neural networks via polyhedral geometry
Abstract: Neural networks with piecewise linear activation functions, such as rectified linear units (ReLU) or maxout, are among the most fundamental models in modern machine learning. In this talk, I will show two approaches to prove lower bounds on the size of such neural networks for achieving a desired expressivity. On one hand, we connect their representative capabilities to the notion of the extension complexity of polytopes. This leads to the new notion of virtual extension complexity. On the other hand, I demonstrate how one can use certain valuations on polytopes as invariants.
The talk is based on joint works with Christoph Hertrich and Christian Haase.
Irem Portakal: Exploring equilibria in game theory with polytopes
Abstract: In this talk, we explore the combinatorial aspects of studying and counting Nash equilibria in game theory. This includes finding equilibrium points on the faces of certain polytopes, counting them through mixed volume calculations, and delving into algebraic statistics to understand newer equilibria, such as conditional independence equilibria.
Tuesday
Alex Black: Shadows of Polytopes
Abstract: A shadow of a polytope is its image under a linear projection to two dimensions. Shadows appear in various applications including parametric optimization, algebraic complexity theory, and the theory of the simplex method. In each of these applications, the primary concern is the number of vertices of a shadow, which is used to bound the run-time of several algorithms. In this talk, I will survey known results about sizes of shadows and highlight my work on the topic. Throughout I will describe important open problems. This talk is partially based on joint work with Francisco Criado.
Eleni Tzanaki: Upper bounds on the number of faces of the Minkowski sum of polytopes
Given two convex polytopes $P, Q$, their Minkowski sum, which is again a polytope, is defined as $P+Q = \{p+q:\, p\in P, q\in Q\}$. In this talk I will present tight expressions for the maximum number of $k$-dimensional faces, $0 \leq {k} \leq {d-1}$, of the Minkowski sum $P_1 + \cdots + P_r$, of $r$ convex $d$-dimensional polytopes $P_1, \ldots, P_r$ in $\mathbb R^d$ where $d \geq {2}$ and $r<d$, as a (recursively defined) function of the number of vertices of the polytopes. These upper bounds are proved making use of basic notions such as $f$- and $h$-vector calculus, stellar-subdivisions and shellings, and generalize the steps used by McMullen to prove the Upper Bound Theorem for polytopes. The key idea behind the approach is to express the Minkowski sum $P_1 + \cdots + P_r$ as a section of the Cayley polytope $C$ of the summands; bounding the $k$-faces of $P_1 + \cdots + P_r$ reduces to bounding the subset of the $(k + r - 1)$-faces of $C$ that contain vertices from each of the $r$ polytopes. I will focus on the steps of the proof for the Minkowski sum of two polytopes. I will then explain how these steps should be adjusted when one considers the Minkowski sum of more polytopes.
Vincent Pilaud: Wigglyhedra
Abstract: The talk will present the construction of the wigglyhedron, a polytope whose vertices correspond
* to wiggly pseudotriangulations (some sort of degenerations of the pseudotriangulations of a point set in general position) defining the facets of the wiggly complex,
* and to wiggly permutations (some permutations defined by a pattern avoidance condition) defining the wiggly lattice.
We will see that the wigglyhedron contain copies of all type A Cambrian associahedra, and evoke the motivation of the wiggly complex from categorical representation theory.
This is based on joint work with Asilata Bapat (arXiv:2407.11632).
Wednesday
Jacinta Torres: A new branching model via lattice points in flagged hive polytopes
Abstract: We prove a bijection between the branching models of Kwon and Sundaram, conjectured by Lenart-Lecouvey. To do so, we use a symmetry of the Littlewood-Richardson coefficients in terms of lattice points in hive polytopes. Along the way, we introduce a new branching rule using “flagged hives”. This is joint work with Sathish Kumar.
Lorenzo Venturello: Two graphs polytopes
Abstract: In this talk I will describe two families of lattice polytopes one can construct from a graph: symmetric edge polytopes and cosmological polytopes. Besides being interesting objects for combinatorialists, they often pop up in other areas of mathematics and physics, such as the study of finite metric spaces, optimal transport and cosmology. Our general goal is to understand how geometric invariants of these polytopes (their Ehrhart theory, volume) are related to the combinatorics of the underlying graph. In the first part I will discuss a conjecture due to Ohsugi and Tsuchiya predicting gamma-positivity of the h^*-vector of symmetric edge polytopes, and present partial results. In the second part I will focus on cosmological polytopes and show the existence of regular unimodular triangulations. This is joint work with D’Alì, Juhnke and Köhne and with Juhnke and Solus.
Posters
Anouk Brose (University of California, Davis): Computing Lattice Diameters of Lattice Polygons
Finding a hyperplane that intersects a polytope in maximal volume can be computed in polynomial time. This is recent work of M. Brandenburg, J.A. De Loera and C. Meroni. As a discrete analog, we study lattice polytopes, and aim to find hyperplanes that maximize the number of lattice points in the intersection. We present an algorithm for the 2-dimensional case, which finds the lattice diameter of a lattice polygon, i.e. the line that contains maximally many lattice points. Further, we show that computing the lattice diameter of semi-algebraic convex bodies in dimensions greater than 2 is NP-hard. This is joint work with J. A. De Loera, G. López, and A. Torres.
Carsten Peterson (Sorbonne University IMJ-PRG): A degenerate version of Brion's formula
Let $V$ be a real vector space, $\mathfrak{p} \subset V$ a polytope, $\Lambda \subset V$ a lattice, and $\xi \in V^*_{\mathbb{C}}$ a functional. Brion's formula is an elegant formula for expressing $\int_{\mathfrak{p}} \exp(\langle \xi, x \rangle) dx$ as well as $\sum_{\mathfrak{p} \cap \Lambda} \exp(\langle \xi, \lambda \rangle)$. However a naive version of the formula breaks down whenever $\xi$ is constant on some positive-dimensional face of $\mathfrak{p}$. We derive a ``degenerate'' version of Brion's formula that works for any $\xi$. When $\xi$ is generic our formula reduces to the usual Brion's formula, and when $\xi = 0$ our formula reduces to the Ehrhart quasi-polynomial. Our motivations for seeking such a formula arose from analysis on symmetric spaces and affine buildings; in that setting our formula may be seen as an analogue of the method of stationary phase. Preprint at arXiv:2409.09544.
Dhruv Bhasin (Indian Institute of Science Education & Research Pune, India): A Cubical Perspective on Complements of Union-Closed Families of Sets
Complements of union-closed families of sets, over a finite ground set, are known as simply rooted families of sets. Cubical sets are widely studied topological objects having applications in computational homology. In this paper, we look at simply rooted families of sets from the perspective of cubical sets. That is, for every family $\mathcal F$ of subsets of a finite set, we construct a natural cubical set $X(\mathcal F)$ (corresponding to it). We show that for every simply rooted family \mathcal F$, containing the empty set, the cubical set $X(\mathcal F)$ is always acyclic (that is, it has trivial reduced cubical homology). As a consequence of this, using the Euler-Poincar\`{e} formula, we obtain a formula satisfied by all simply rooted families of sets which contain the empty set. We also provide an elementary proof of this formula.
This is based on: https://arxiv.org/abs/2409.17050
Jhon Bladimir Caicedo Portilla (Universität Osnabrück): Unimodular Triangulations and Ehrhart-Negativity for s-Lecture Hall Simplices
Given a sequence of positive integers s = (s_1, ..., s_n), the s-lecture hall simplex is defined as P_n^s = conv{(0, ..., 0), (0, ..., s_n), ..., (s_1, ..., s_n)}. Hibi et al. [1] conjectured that for any sequence s, P_n^s admits a UT (unimodular triangulation). Partial results for this conjecture have been provided by Bränden & Solus in [2] and by Hibi et al. in [1].
In this work, we provide further evidence for this conjecture by showing that if P_n^s admits a UT, then so does P_n^{s'}, where s'=(s_1,...,s_n+1). Additionally, given s = (a, ..., a, a+1)\in \Z^{n} with a\in\Z^+ and n > 4, we show that P_n^s is not Ehrhart positive for a large enough. This result provides a partial answer to a question posed by Olsen in [3]. This is joint work with Martina Juhnke-Kubitzke and Germain Poullot.
Joseph Briggs (Auburn University): Discretized Brunn-Minkowski and Cayley Graph Isoperimetry
Given a Cayley graph G on an integer lattice, what set of n vertices in G has smallest neighbourhood? Rusza used discrete approximations of Brunn-Minkowski to give asymptotics. Moreover Wang-Wang and Radcliffe-Veomett gave exact answers for every n specifically for the l_1 and l_\infty lattices where optimizers are nested. Barber-Erde asked whether such beautiful behaviour occurs for all possible G, but (with Wells) we exhibit examples with isoperimetric phase transitions showing some convexity is necessary.
Tanja Stojadinović (University of Belgrade): Between graphical zonotope and graph-associahedron
We introduce a finite collection of generalized permutohedra associated to a simple graph. The first polytope of this collection is the graphical zonotope of the graph and the last is the graph-associahedron associated to it. We describe the weighted integer points enumerators for polytopes in this collection as Hopf algebra morphisms of combinatorial Hopf algebras of decorated graphs.
This is a joint work with Marko Pešović.
Leonie Mühlherr (University of Bielefeld): Arrangements and Likelihood
In the project this poster presents, we develop novel tools for computing the likelihood correspondence of an arrangement of hypersurfaces in a projective space.
This uses the module of logarithmic derivations, which is well-studied in the linear case, when the hypersurfaces are hyperplanes. This poster presents the basic ideas and how they are related to each other and exemplifies this by focusing on the graphic arrangement case.
This is joint work with Thomas Kahle, Lukas Kühne, Bernd Sturmfels and Maximilian Wiesmann.
Teemu Lundström (Aalto University): f-vector inequalities for order and chain polytopes.
The order and chain polytopes are two polytopes constructed from a finite poset. They are 0/1-polytopes whose vertices and facets are easily described as corresponding to certain parts of the underlying poset. The face lattice of the order polytope is isomorphic with a certain lattice of partitions of the underlying poset, but no similar description is known for the chain polytope. The focus of this presentation is on how the f-vector of the order polytope a poset P corresponds to the f-vector of the chain polytope of P. In 2016, it was conjectured by Hibi and Li that the f-vector of the chain polytope of P coordinate-wise dominates the f-vector of the order polytope of P. Our main theorem confirms this conjecture for a large class of posets built inductively using ordinal sums and disjoint unions of posets. This is joint work with Ragnar Freij-Hollanti.
Venkitesh Iyer (Tel Aviv University): Matroids and Polytopes from Standard Young Tableaux
The Catalan matroid C_n (Ardila, 2003) can be defined by a collection of bases given by Dyck paths from (0,0) to (n,n) in the nonnegative integer quadrant. These are a subclass of shifted matroids (Welsh, 1969; Oxley et al., 1982; Klivans, 2003), and the more general lattice path matroids (Bonin et al., 2002). Motivated by the one-to-one correspondence between Dyck paths from (0,0) to (n,n), and standard Young tableaux of shape (n,n), we consider a new family of matroids defined by restricted standard Young tableaux of arbitrary shape.
Yuan Yao (MIT): Fine Mixed Subdivisions of Dilated Simplices
A mixed subdivision is a generalization of zonotope tiling that applies to any Minkowski sums of polytopes. (Fine) mixed subdivisions of dilated simplices have received particular attention in recent years due to their connections to tropical geometry and matroid theory. We will present some progress towards resolving Ardila and Billey's \emph{Spread-out Simplices Conjecture}, a central question in this field.