GMZ 60

Affine projections and sections of polytopes are also polytopes. These (essentially dual) operations are at the heart of polytope theory, since every polytope with n vertices and m facets can be represented as a projection of an \((n-1)\)-simplex or as a section of an \((m-1)\)-simplex. In this talk, I will present three ongoing projects revolving around these two operations:

• Gale diagrams were introduced by Perles, and have been greatly used in the study of high-dimensional polytopes with few vertices. They can be interpreted as an instance of Ziegler's projection lemma for the canonical projection of a simplex onto a polytope. Using the same schema with other projections gives rise to the concept of generalized Gale diagrams. A dual interpretation can be given for sections of polytopes. I will present a unified approach that combines projections and sections. Many existing objects fit in this framework. In particular, it models non-negative matrix factorizations and extended formulations of polytopes.
• Given a (generic enough) linear projection onto \(\mathbb{R}^{k+1}\), one defines the k-top and k-bottom of a polytope as the set of its k-faces that form the upper and lower envelopes of its image. A k-cellular string of a polytope P is then a sequence of faces of P of dimension \(>\)k in which the k-bottom of each face intersects the top of its predecessor. They were used by Kapranov and Voevodsky in 1991 to study formal compositions of k-morphisms in higher category theory. In this context, it is very important for k-cellular string to be loop-free. I will show that, contrary to Kapranov and Voevodsky's original claim, polytopal k-cellular strings can present loops. This is joint work in progress with Anibal M. Medina-Mardones and Guillaume Laplante-Anfossi.
• Nested complexes are simplicial complexes associated to building sets of a meet semi-lattice. They were defined by Feichtner and Kozlov motivated by De Concini and Procesi's wonderful compactification. For building sets of the boolean lattice, they are realized by polytopes called nestohedra, constructed as a Minkowski sum of faces of a standard simplex. Motivated by poset associahedra, recently introduced by Galashin, we provide a new polytopal realization for nested complexes of building sets of polytopal face lattices as linear sections of (boolean) nestohedra. This is joint work in progress with Chiara Mantovani and Vincent Pilaud.

One of many definitions gives the rank of an \(m \times n\) matrix \(M\) as the smallest natural number \(r\) such that \(M\) can be factorized as \(AB\), where \(A\) and \(B\) are \(m \times r\) and \(r \times n\) matrices respectively. In many applications, one is interested in factorizations of a particular form. For example, factorizations with nonnegative entries define the nonnegative rank which is a notion that is used in data mining applications, statistics, complexity theory etc. Nonnegative rank has geometric characterizations using nested polytopes. I will give an overview how these nested polytopes are related to characterizations of the set of matrices of given nonnegative rank and uniqueness of nonnegative matrix factorizations.

Let \(V = \binom{[n]}{2}\) label the possible diagonals among the vertices of a convex n-gon. A subset of size \(k+1\) is called a \((k+1)\)-crossing if all elements mutually cross, and a general subset is called \((k+1)\)-crossing free if it does not contain a \(k\)-crossing. \((k+1)\)-crossing free subsets form a simplicial complex that we call the \(k\)-associahedron and denote \(\mathrm{Ass}_k(n)\) since for \(k=1\) one (essentially) recovers the simplicial associahedron. The \(k\)-associahedron on the \(n\)-gon is known to be a shellable sphere of dimension \(k(n-2k-1)\) and conjectured to be polytopal (Jonsson 2003). It is also a subword complex in the root system of type \(A\) and, moreover, every (spherical) subword complex is a link in some \(k\)-associahedron. In particular, polytopality of \(k\)-associahedra would imply the same for spherical subword complexes (in type \(A\)), a question asked by Knutson and Miller in 2004.

The dimension of the \(k\)-associahedron happens to coincide with that of any abstract rigidity matrix of dimension \(2k\) on \(n\) elements. This made Pilaud and Santos (2010) conjecture that \(k\)-triangulations are generically isostatic graphs in dimension \(2k\), in the usual bar-and-joint rigidity theory. This was meant as a step towards the construction of the \(k\)-associahedron as a polytope (or at least as a complete fan) by taking as facet normal the rows of the corresponding rigidity matroid. We explore this possibility and find out that:

• restricted to the moment curve, bar-and-joint rigidity coincides with another two classical forms of rigidity: Whiteley's cofactor rigidity and Kalai's hyperconnectivity. The former is particularly suitable to model k-triangulations since it is based on configurations of points in the plane (the parameter k represents the degree of the algebraic structures involved). The latter connects rigidity and k-triangulations with the variety of Pfaffians of antisymmetric matrices of size \(2k\).
• suitable choices of points along the moment curve allow us to find realisations of the k-associahedron, or at least its fan, for all values of \((k,n)\) with \(n \le 13\), except for \((3,12)\) and \((3,13)\).
• no choice of points along the moment curve can provide realisations of the k-associahedron for any \(n \ge 2k+6\) and \(k \ge 3\). This includes the cases \((3,12)\) and \((3,13)\) mentioned above.

We consider this last result as an indication that Jonsson's conjecture (and hence Knutson-Miller's question) might fail. The talk is based on joint work with Luis Crespo and will introduce the needed rigidity theory ideas.

A secret-sharing scheme is a protocol that distributes shares of a secret amongst participants such that only certain authorized subsets can retrieve the secret using their shares. In this talk, I will explore connections between these secret-sharing schemes and matroids. Using group theoretic word problem instances we will see that the existence of optimal secret-sharing schemes is undecidable in general.

Based on joint work with Geva Yashfe.

The Ehrhart polynomial of a lattice polytope counts the number of lattice points in positive integer dilates of the polytope. A fundamental theorem by Stanley states that the Ehrhart polynomial, expressed in a particular binomial basis, has only nonnegative coefficients. In this talk, we present generalizations of this and related results to weighted integer point counting in rational polytopes where the weights are given by polynomial functions. In particular, we show that Stanley's Nonnegativity Theorem extends to weights given by homogeneous polynomials decomposable as sums of products of linear forms that are nonnegative over the polytope. This is joint work with Esme Bajo, Robert Davis, Jesús de Loera, Alexey Garber, Sofía Garzón Mora and Josephine Yu.

We all know that communicating mathematics can be hard. Especially when it comes to the negotiation of meaning in the public sphere. The MIP.labor combines practical design-based research of format development with empirical research. It is an experimental laboratory for innovative science journalism in mathematics, computer science, and physics. With fellowships, we enable established and aspiring science journalists to develop journalistic projects in these fields over six or twelve months. The project is funded by Klaus Tschira Stiftung.

Mathematics is the foundation for the technology that increasingly shapes our modern lives — we hear sentences like that a lot, and it has never been more true than today where we are opening a new chapter of artificially intelligent devices and services. But who really understands the mathematics behind the technology? Who informs the public? While we are used to read about the latest discoveries in astronomy or biotechnology in popular media, math reporting is a niche phenomenon. And if journalists talk about math, they tend to cherry-pick examples that they think they can convey to their readers — stacking oranges, finding big prime numbers. But the cutting edge of math (that even a majority of mathematicians have problems wrapping their heads around) is deemed to be “too complicated” by most editors. But in recent years, there have been efforts to report on “serious” math in compelling and excellently written journalistic articles. The internet has made it possible to publish stories at any level of complexity, and online magazines like “Quanta” prove that complex and relevant mathematics can be a subject for a broader audience.

A main theme in Günter Ziegler's PhD Thesis, entitled “Algebraic combinatorics of hyperplane arrangements”, was “the surprisingly high degree to which [the poset of intersections] controls and determines the topological invariants of an arrangement”. I will revisit this theme in the context of arrangements of hypersurfaces. In this less structured setting, the interplay between combinatorics and topology is even subtler, and ever so surprising!

In my talk I will focus on arrangements in abelian Lie groups (e.g., arrangements in complex tori and in products of elliptic curves). After defining the main characters I will survey current developments and some open questions in the field.

Let \(X\) be the integer points contained in a polytope. The relaxation complexity \(\mathrm{rc}(X)\) is the smallest number of facets of any polyhedron \(P\) such that the integer points in \(P\) coincide with \(X\). It is a useful tool to investigate the existence of compact linear descriptions of \(X\). In particular, it provides the minimum number of inequalities needed in any integer programming formulation of \(X\). Moreover, when restricting the polyhedra \(P\) to be rational, \(\mathrm{rc}_\mathbb{Q}(X)\) denotes the corresponding rational relaxation complexity of \(X\).

In this presentation, I discuss several algorithmic aspects of finding the relaxation complexity. First, a natural question is whether \(\mathrm{rc}(X)\) is computable. While this question is notoriously open in general, I present an algorithm that finds \(\mathrm{rc}(X)\) in dimension 2. Second, \(\mathrm{rc}_\mathbb{Q}(X)\) is an upper bound on \(\mathrm{rc}(X)\). A natural idea is thus to provide computable lower bounds on \(\mathrm{rc}(X)\) and computable upper bounds on \(\mathrm{rc}_\mathbb{Q}(X)\). If these bounds match, \(\mathrm{rc}(X)\) and \(\mathrm{rc}_\mathbb{Q}(X)\) have been found. I show that we can indeed find a matching upper bound on \(\mathrm{rc}_\mathbb{Q}(X)\), whereas I discuss why finding a matching lower bound for \(\mathrm{rc}(X)\) seems to be more challenging. Finally, the previously sketched idea only allows to compute \(\mathrm{rc}(X)\) and \(\mathrm{rc}_\mathbb{Q}(X)\) if both quantities coincide. I conclude this presentation by a brief outline that \(\mathrm{rc}(X)\) can be strictly smaller than \(\mathrm{rc}_\mathbb{Q}(X)\).

This is joint work with Manuel Aprile, Gennadiy Averkov, Marco Di Summa, and Matthias Schymura.

An early success story of topological methods in discrete geometry is the Ham Sandwich theorem, which states that any \(d\) finite point sets in \(\mathbb{R}^d\) can simultaneously be cut in half by an affine hyperplane. I will discuss generalizations to multiple hyperplanes, unbalanced cuts, and hyperplane transversals. Dolnikov's theorem states that any \(d\) pairwise intersecting families of polytopes in \(\mathbb{R}^d\) can be simultaneously pierced by one hyperplane. This generalizes the Ham Sandwich theorem. I will present variants of Dolnikov's theorem for multiple hyperplanes.