direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments


Omid Amini (École polytechnique)16.11.2216:30MA 850

MaRDI Annual Meeting09.11.22------ ---

Raman Sanyal (Goethe-Universität Frankfurt)02.11.2216:30MA 850

Leonid Monin (MPI MiS Lepzig)19.10.2216:30MA 850

Yulia Alexandr (UC Berlekey)12.10.2217:00Online

Matthias Schymura (BTU Cottbus-Senftenberg)05.10.2216:30MA 141 On the maximal number of columns of a Delta-modular integer matrix

We are interested in a combinatorial question related to the recent and ongoing interest in understanding the complexity of integer linear programming with bounded subdeterminants. Given a number Delta and a full-rank integer matrix A with m rows such that the absolute value of every m-by-m minor of A is bounded by Delta, at most how many pairwise distinct columns can A have? The case Delta = 1 is the classical result of Heller (1957) saying that the maximal number of pairwise distinct columns of a totally unimodular integer matrix with m rows equals m^2 + m + 1. If m >= 3 and Delta >= 3, the precise answer to this combinatorial question is not known, but bounds of order O(Delta^2 m^2) have been proven by Lee et al. (2021). In the talk, I will discuss our approach to the problem which rests on counting columns of A by residue classes of a suitably defined integer lattice. As a result, we obtain the first bound that is linear in Delta and polynomial (of low degree) in the dimension m. Moreover, I explain how one can approach the corresponding classification problem and how this results in the construction of counterexamples to the previously conjectured value of the maximum above. The talk is based on a joint work with Gennadiy Averkov, see https://arxiv.org/abs/2111.06294.

Jesús A. De Loera (UC Davis)28.09.2216:30MA 144 Open problems arising from trying to understand the Simplex Method

The simplex method is one of the most famous and popular algorithms in optimization, it was even named on the top 10 algorithms of the 20th century by SIAM and IEEE. But despite its great success and fame we do not fully understand it. There are several natural open questions arising from the analysis of its performance This talk highlights several fascinating geometric and combinatorial problems we wish to answer. Many open questions will be available for the eager young researcher. I promise!
In the first part I re-introduce natural geometric-topological structure one can associate to the set of all possible monotone paths of a linear program, I will then use this structure, first introduced by Billera and Sturmfels, to study How long can the longest monotone paths on a linear program become? How many different monotone paths can there be on a linear program? We report on two papers, the first joint work with M. Blanchard and Q. Louveaux, and another with C. Athanasiadis and Z. Zhang. Next, the engine of any version of the simplex method is a *pivot rule* that selects the outgoing arc for a current vertex. Pivot rules come in many forms, definitions, and types, but after 80 years we are still ignorant whether there is one that can make the simplex method run in polynomial time. Can we classify all pivot rules? How many possible different pivot rules can there be on a linear Program? Do these questions even make sense? In the second half of my talk will present two recent positive results: For 0/1 polytopes there are explicit pivot rules for which the number of non-degenerate pivots is polynomial and even linear (joint work with A. Black, S. Kafer, L. Sanita). I also present a parametric analysis for all pívot rules. We construct a polytope, the pivot rule polytope, that parametrizes all memoryless pívot rules of a given LP. Its construction is a generalization of the Fiber polytope construction of Billera Sturmfels. This is an attempt to get a complete picture of the structure “space of all pivot rules of an LP” (joint work with A. Black, N.Lütjeharms, and R. Sanyal).

SFB/TRR 195 meeting20.09.22------ ---

DMV annual meeting13.09.22------ ---

Geometry meets combinatorics in Bielefeld06.09.22------ ---

Benjamin Schröter (KTH) 24.08.2216:30H 1029 Valuative Invariants for Matroids

Valuations on polytopes are maps that combine the geometry of polytopes with relations in a group. It turns out that many important invariants of matroids are valuative on the collection of matroid base polytopes, e.g., the Tutte polynomial and its specializations or the Hilbert–Poincaré series of the Chow ring of a matroid. In this talk I will present a framework that allows us to compute such invariants on large classes of matroids, e.g., sparse paving and elementary split matroids, explicitly. The concept of split matroids introduced by Joswig and myself is relatively new. However, this class appears naturally in this context. Moreover, (sparse) paving matroids are split. I will demonstrate the framework by looking at Ehrhart polynomials and Hilbert–Poincaré series of elementary split matroids. This talk is based on the preprint `Valuative invariants for large classes of matroids' which is joint work with Luis Ferroni.

Anton Dochtermann (Texas State University20.07.22 16:30 MA 141 Root polytopes, tropical types, and toric edge ideals

We consider arrangements of tropical hyperplanes, where the apices of the hyperplanes can be `taken to infinity' in certain directions. Such an arrangement defines a decomposition of Euclidean space where a cell is defined by its `type' data, analogous to the covectors of an oriented matroid. By work of Develin-Sturmfels and Fink-Rincon it is known that these `tropical complexes' are dual to (regular) subdivisions of root polytopes, which in turn are in bijection with mixed subdivisions of certain generalized permutohedra. Extending previous work with Joswig-Sanyal, we show how a natural monomial labeling of these complexes describes polynomial relations (syzygies) among `type ideals' which arise naturally from the combinatorial data of the arrangement. In particular, we show that the cotype ideal is Alexander dual to a squarefree initial ideal of the lattice ideal of a root polytope corresponding to the Stanley-Reisner ideal of a regular triangulation of the root polytope. This in turn leads to novel ways of studying algebraic properties of various monomial and lattice ideals. For instance, our methods of studying the dimension of a tropical complex provide new bounds on homological invariants of toric edge ideals of bipartite graphs, which have been extensively studied in the commutative algebra community. This is joint work with Ayah Almousa and Ben Smith.

Büsra Sert13.07.22 16:30 MA 141 The Half-Plane Property of Matroids, Related Concepts, and an Algorithm

Studies on homogeneous polynomials with the half-plane property were initially motivated by the physical theory of electrical networks. They later became of interest in convex optimization. In particular, a homogeneous polynomial with the half-plane property is hyperbolic with respect to every point in the positive orthant, having an associated hyperbolicity cone. Feasible sets of semi-definite programming, i.e., spectrahedral cones, are hyperbolicity cones for some polynomials. For the converse, the generalized Lax conjecture states that every hyperbolicity cone is spectrahedral.
Considering that the basis generating polynomials of matroids are homogeneous and multiaffine, a natural approach is investigating the mentioned properties of matroids. For instance, the combinatorial structure of matroids was used by Brändén to give a counter example for a stronger version of the conjecture.
In this talk, we present our results on the operations on matroids that preserve related properties. Moreover, we give an algorithm for testing the half-plane property of matroids that uses Macaulay2 packages SumsOfSquares, Matroids and the Julia package Homotopy Continuation.jl. We illustrate the outcome of the classification of matroids on at most 8 elements with respect to the half-plane property and provide our test results on matroids on 9 elements.
This is joint work with Mario Kummer.

Matthias Beck (SFSU)22.06.22 16:30 MA 141 \(f^*\)- and \(h^*\)-vectors

If \(P\) is a lattice polytope (i.e., \(P\) is the convex hull of finitely many integer points in \({\bf R}^d\)), Ehrhart's theorem asserts that the integer-point counting function \(L_P(m) = \#(mP \cap {\bf Z}^d)\) is a polynomial in the integer variable $m$. Our goal is to study structural properties of Ehrhart polynomials---essentiallly asking variants of the (way too hard) question which polynomials are Ehrhart polynomials? Similar to the situations with other combinatorial polynomials, it is useful to express \(L_P(m)\) in different bases. E.g., a theorem of Stanley (1976) says that \(L_P(m)\), expressed in the polynomial basis \(\binom m d, \binom{m+1} d, \dots, \binom{m+d} d\), has nonnegative coefficients; these coefficiencts form the \(h^*\)-vector of \(P\). More recent work of Breuer (2012) suggests that one ought to also study \(L_P(m)\) as expressed in the polynomial basis \(\binom {m-1} 0, \binom {m-1} 1, \binom {m-1} 2, \dots\); the coefficiencts in this basis form the \(f^*\)-vector of \(P\). We will survey some old and new results (the latter joint work with Danai Deligeorgaki, Max Hlavaczek, and Jerónimo Valencia) about \(f^*\)- and \(h^*\)-vectors, including analogues and dissimiliarieties with \(f\)- and \(h\)-vectors of polytopes and polyhedral complexes.

Julian Pfeifle (UPC)15.06.22 16:30 Online Coming soon to polymake: (sometimes) disproving convex realizability of spheres

Every so often, we find a family of simplicial spheres with interesting combinatorial properties, and would like to know if they are realizable as boundaries of convex polytopes. For instance, this happened recently to Zheng; to Novik and Zheng; and to Criado and Santos.
We focus on algorithmically *disproving* the convex realizability of a given simplicial sphere. All previous successful approaches made essential use of integer or linear programming, which severely limits the practical applicability due to memory and runtime constraints. In our new implementation, we instead perform a combinatorial search using optimized data structures, which lets us decide in seconds examples that are completely out of reach of the best alternative implementation by Gouveia, Macchia, and Wiebe.
Our code has now undergone the third complete rewrite, and is almost ready to be merged into the polymake tree. If time permits, we will discuss some of the lessons learned during the implementation, and mention further conceptual improvements that bring us tantalizingly close to deciding the long-standing open problem of convex realizability of multitriangulations.

CG Week08.06.22 FU Berlin CG Week

Enis Kaya (MPI MiS Leipzig)01.06.22 16:30 MA 141 Determining reduction types of Picard curves via tropical invariants

For a separable binary form of degree n over a complete non-archimedean field, there is a canonical metric tree on n leaves associated to it. Furthermore, for every degree n, there are only finitely many tree types, which gives rise to a partition of the space of all non-archimedean binary forms of degree n.
In this talk, we will focus on the particular case where n = 5. Then, there are exactly 3 unmarked and 5 marked tree types. We will give a set of tropical invariants, valuations of certain elements coming from invariant theory for binary quintics, and show that these invariants allow us to distinguish the tree types algorithmically. As an application, we will express the reduction types of Picard curves in terms of tropical invariants of the associated binary quintics.
This is joint work with Yassine El Maazouz and Paul Alexander Helminck.

Zoe Wellner (Carnegie Mellon University)25.05.22 16:30 MA 141 Colorful Borsuk-Ulam Results, Their Generalizations and Applications

In combinatorics and discrete geometry there are many colorful and rainbow results. Additionally topological tools have proven to be useful in generating interesting combinatorial results. In this line of approach we prove a colorful generalization of the Borsuk–Ulam theorem. We give a short proof of Ky Fan’s Lemma and generalize it from involutions to larger symmetry groups Z/p for prime p. We also present colorful generalizations of these nonexistence results for equivariant maps. As consequences we derive a colorful generalization of the Ham–Sandwich theorem and the necklace splitting theorem among other applications of Borsuk-Ulam. This is joint work with Florian Frick.

Niels Lindner (ZIB)18.05.22 16:30 MA 141 On the tropical and zonotopal geometry of periodic timetabling

The timetable is the core of every public transportation system. The standard mathematical tool for optimizing periodic timetabling problems is the Periodic Event Scheduling Problem (PESP). A solution to PESP consists of three parts: a periodic timetable, a periodic tension, and integer periodic offset values. While the space of periodic tension has received much attention in the past, we explore geometric properties of the other two components, establishing novel connections between periodic timetabling and discrete geometry. Firstly, we study the space of feasible periodic timetables, and decompose it into polytropes, i.e., polytopes that are convex both classically and in the sense of tropical geometry. We then study this decomposition and use it to outline a new heuristic for PESP, based on the tropical neighbourhood of the polytropes. Secondly, we recognize that the space of fractional cycle offsets is in fact a zonotope. We relate its zonotopal tilings back to the hyperrectangle of fractional periodic tensions and to the tropical neighbourhood of the periodic timetable space. Finally, we also use this new understanding to give tight lower bounds on the minimum width of an integral cycle basis in terms of the number of spanning trees.

Alex Elzenaar (MPI MiS Leipzig)04.05.22 16:30 MA 141 Aspects of computation in hyperbolic geometry

Low-dimensional topology has the advantage that it is relatively easy to visualise-the key word being relatively. Some people have amazing powers of visualisation (famously, William Thurston); but most of us need to rely on visual aids to try to understand what is going on. There is a long history of computer experimentation in the area of hyperbolic geometry and Kleinian groups (groups which arise dually to hyperbolic 3-manifolds), from the Thurston days (Robert Riley's work on knot groups in the 1970s and Jeff Weeks' study of triangulations of 3-manifolds in the 1980s) to the modern era (including but not limited to work by David Mumford, Caroline Series, and David Wright; Masaaki Wada; and Sabetta Matsumoto and Henry Segerman). This talk will discuss some of the highlights of computation in hyperbolic geometry with an emphasis on visualisation, focusing on groups and manifolds related to two-bridge knots (parameterised by the so-called Riley slice).

Thomas Blomme (University of Geneva)27.04.22 16:30 Online Enumeration of tropical curves in abelian surfaces

Tropical geometry is a powerful tool that allows one to compute enumerative algebraic invariants through the use of some correspondence theorem, transforming an algebraic problem into a combinatorial problem. Moreover, the tropical approach also allows one to twist definitions to introduce mysterious refined invariants, obtained by counting tropical curves with polynomial multiplicities. So far, this correspondence has mainly been implemented in toric varieties. In this talk we will study enumeration of curves in abelian surfaces and use the tropical geometry approach to prove a multiple cover formula that enables an simple and elegant computation of enumerative invariants of abelian surfaces.

Michael Joswig (TU Berlin)20.04.22 16:30 Online Lattice polygons and real roots

It is known from theorems of Bernstein, Kushnirenko and Khovanskii from the 1970s that the number of complex solutions of a system of multivariate polynomial equations can be expressed in terms of subdivisions of the Newton polytopes of the polynomials. For very special systems of polynomials Soprunova and Sottile (2006) found an analogue for the number of real solutions. In joint work with Ziegler we could give a simple combinatorial formula and an elementary proof for the signature of foldable triangulation of a lattice polygon. Via the Soprunova-Sottile result this translates into lower bounds for the number of real roots of certain bivariate polynomial systems.

PhD Students of DM/G (TU Berlin)13.04.22 16:30 Online Scientific Writing

Marie Brandenburg (MPI MiS Leipzig)16.03.22 16:30 Online Competitive Equilibrium and Lattice Polytopes

The question of existence of a competitive equilibrium is a game theoretic question in economics. It can be posed as follows: In a given auction, can we make an offer to all bidders, such that no bidder has an incentive to decline our offer? We consider a mathematical model of this question, in which an auction is modelled as weights on a simple graph. The existence of an equilibrium can then be translated to a condition on certain lattice points in a lattice polytope. In this talk, we discuss this translation to the polyhedral language. Using polyhedral methods, we show that in the case of the complete graph a competitive equilibrium is indeed guaranteed to exist. This is based on joint work with Christian Haase and Ngoc Mai Tran.

Lorenzo Venturello (KTH)09.03.22 16:30 Online On the gamma-vector of symmetric edge polytopes

Symmetric edge polytopes (SEPs) are special lattice polytopes constructed from a simple graph. They play a role in physics, in the study of metric spaces and optimal transport. We study a numerical invariant of symmetric edge polytopes, called the gamma-vector, whose entries are linear combinations of the \(h^*\) numbers. In particular, we target a conjecture of Ohsugi and Tsuchiya which predicts nonnegativity of the gamma-vector of every SEP. In a joint work with Alessio D'Alì, Martina Juhnke-Kubitzke and Daniel Köhne, we prove nonnegativity for one of the entries of the gamma-vector, and descriube the graphs whose SEP attains equality. Moreover, we consider random graphs in the Erdős–Rényi model, and we obtain asymptotic nonnegativity of the whole gamma-vector in certain regimes.

Lei Xue (University of Washington)16.02.22 16:30 Online A Proof of Grünbaum’s Lower Bound Conjecture for polytopes, lattices, and strongly regular pseudomanifolds

In 1967, Grünbaum conjectured that any \(d\)-dimensional polytope with \(d +s \leq 2d\) vertices has at least \( \phi_k (d + s, d) = {d +1 \choose k + 1} + { d \choose k + 1} - { d + 1 - s \choose k + 1} \) \(k\)-faces. In the talk, we will prove this conjecture and discuss equality cases. We will then extend our results to lattices with diamond property (the inequality part) and to strongly regular normal pseudomanifolds (the equality part). We will also talk about recent results on \(d\)-dimensional polytopes with \(2d + 1\) or \(2d + 2\) vertices.

Mara Belotti (TU Berlin)09.02.22 16:30 Online An enumerative problem for cubic (hyper)surfaces: point and line conditions

The moduli space of smooth cubic hypersurfaces in \(\mathbb{P}^n\) is an open subset of a projective space. We construct a compactification of the latter which allows us to count the number of smooth cubic hypersurfaces tangent to a prescribed number of lines and passing through a given number of points. We term it a \(1\)-complete variety of cubic hypersurfaces in analogy to the space of complete quadrics. Paolo Aluffi explored the case of plane cubic curves. Starting from his work, we construct such a space in arbitrary dimensions by a sequence of five blow-ups. The counting problem is then reduced to the computation of five total Chern classes. Finally, we arrive at the desired numbers in the case of cubic surfaces. This is joint work with Alessandro Danelon, Claudia Fevola, Andreas Kretschmer.

Sara Griffith (Brown University)02.02.22 16:30 Online The Torelli theorem, or how to determine a graph from its algebraic data

The Torelli theorem for graphs, due to Caporaso-Viviani and Su-Wagner, shows that with mild hypotheses a graph's matroid can be obtained from the integral lattice in its vector space of flows. New results of the speaker show that the graph itself can be recovered using additional data related to winnable chip firing games on the graph.

Paco Santos (Universidad de Cantabria)26.01.22 16:30 Online Multitriangulations and tropical Pfaffians

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 \(Ass_k{n}\) since for \(k=1\) one (essentially) recovers the simplicial associahedron. The \(k\)-associahedron on the \(n\)-gon is known to be (essentially ) 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 the A.
The Pfaffian of an anti-symmetric matrix of size \(2k+2\) is the square root of its determinant, and it is a homogeneous polynomial of degree \(k+1\) with one monomial for each possible complete matching among \(2k+2\) nodes representing the rows and columns. Thus, monomials correspond to certain \((k+1)\)-subsets of \(V\) and among them there is a unique \((k+1)\)-crossing. Calling \(I_k(n)\) the ideal of all Pfaffians of degree \(k+1\) in an antisymmetric matrix of size \(n\), it is known (Jonsson and Welker 2007) that for certain term orders the corresponding initial ideal equals the Stanley-Reisner ideal of the \(k\)-associahedron.
In this talk we explore the relation between Pfaffians and the \(k\)-associahedron from the tropical perspective. We show that the part of the tropical Pfaffian variety \(trop(I_k(n))\) lying in the ``four-point positive orthant’’ realises the \(k\)-associahedron as a fan, and that this intersection is contained in (but is not equal to, except for \(k=1\)) the totally positive tropical Pfaffian variety \(trop^+(I_k(n))\). We hope this to be a step towards realising the \(k\)-associahedron as a complete fan, but have only attained this for \(k=1\): we show that for any seed triangulation \(T\), the projection of \(trop^+(I_1(n))\) to the coordinates corresponding to diagonals in T produces a complete polytopal simplicial fan, that is, the normal fan of an associahedron. In fact, the fans we obtain are linearly isomorphic to the \(g\)-vector fans in cluster algebras of type \(A\), as realized by Hoheweg-Pilaud-Stella (2018).

Jonathan Boretsky (Harvard)19.01.22 16:30 Online The Totally Non-Negative Complete Flag Variety and its Tropicalization

A complete flag in \(\mathbb{R}^n\) is a collection of linear subspaces \(\{0\}=V_0\subsetneq V_1\cdots \subsetneq V_n=\mathbb{R}^n\). The set of all complete flags in \(\mathbb{R}^n\) form a variety called the complete flag variety. We give a combinatorial parameterization of the totally non-negative part of this variety. We also give a simple coordinate-wise characterization of which flags lie in the totally non-negative flag variety. We will also define the notion of a tropical variety and the non-negative part of a tropical variety. There are two tropical varieties that can be described using tropical versions of the equations cutting out the complete flag variety. One, the flag Dressian, can be thought of as describing flags of tropical linear spaces and the second, the tropical flag variety, can be thought of as describing realizable flags of tropical linear space. While these tropical varieties are generally different, we will use our parameterization of the non-negative complete flag variety to show that their non-negative parts coincide.

Dante Luber (TU Berlin)12.01.21 16:30 Online Generalized permutahedra and positive flag Dressians

A well known result relates matroid subdivisions of hypersimplices to tropical linear spaces. We continue the study of subdivisions of generalized permutahedra into cells that are generalized permutahedra. This talk will focus on subdivisions of the regular permutahedron into cells that correspond to flag matroids and intervals in a partial ordering on the symmetric group. This is joint work with Michael Joswig, Georg Loho, and Jorge Olarte

Katharina Jochemko (KTH)15.12.21 16:30 Online The Eulerian transformation

Many polynomials arising in combinatorics are known or conjectured to have only real roots. One approach to these questions is to study transformations that preserve the real-rootedness property. This talk is centered around the Eulerian transformation which is the linear transformation that sends the i-th standard monomial to the i-th Eulerian polynomial. Eulerian polynomials appear in various guises in enumerative and geometric combinatorics and have many favorable properties, in particular, they are real-rooted and symmetric. We discuss how these properties carry over to the Eulerian transformation. In particular, we disprove a conjecture by Brenti (1989) concerning the preservation of real roots, extend recent results on binomial Eulerian polynomials and provide enumerative and geometric interpretations. This is joint work with Petter Brändén.

Matthias Köppe (UC Davis)08.12.21 16:30 Online sagemath-polyhedra: A modularized Sage distribution

SageMath is an open-source general-purpose mathematical system based on Python that integrates computer algebra facilities and general computational packages. Sage, initially developed by Stein and first released in 2005, in over 1.5 decades of incubation in its pseudo-distribution comprising over 300 software packages, has grown to provide over 500 Cython and over 2000 of its own Python modules, ranging from sage.algebras.* over sage.geometry.* to sage.tensor.*, with a total of over 2.2 million lines of code.
I will give an outline of a project, ongoing since 2020, to modularize the Sage library so that parts of it can be flexibly installed and used by other Python projects. One of the first products of the project is the modularized distribution sagemath-polyhedra, which provides computations and constructions with convex polyhedra with multiple backends, including PPL, Normaliz, and polymake.
The project to modularize the Sage library does not conflict with the software integration goals of SageMath. As an example of progress on the latter, I will show the integration of sage.geometry.polyhedron and sage.manifolds, introduced in Sage 9.4.

Benjamin Schröter (KTH)01.12.21 16:30 Online Ehrhart Polynomials of Rank-Two Matroids

There are many questions that are equivalent to the enumeration of lattice points in convex sets. Ehrhart theory is the systematic study of lattice point counting in dilations of polytopes. Over a decade ago De Loera, Haws and Köppe conjectured that the lattice point enumerator of dilations of matroid basis polytopes is a polynomial with positive coefficients. This intensively studied conjecture has recently been disproved in all ranks greater than or equal to three. However, the questions of what characterizes these polynomials remain wide open.
In this talk I will report on my work, with Luis Ferroni and Katharina Jochemko, in which we complete the picture on Ehrhart polynomials of matroid basis polytopes by showing that they have indeed only positive coefficients in low rank. Moreover, we also prove that the closely related $h^∗$-polynomials of sparse paving matroids of rank two are real-rooted, which implies that their coefficients form log-concave and unimodal sequences.

Alexander Stoimenow (GIST College)24.11.21 16:00 Online Exchange moves and non-conjugate braid representatives of links

The braid groups $B_n$ were introduced in the 1930s in the work of Artin. An element in the braid group $B_n$ is called an $n$-braid. Alexander related braids to knots and links in 3-dimensional space, by means of a closure operation. In that realm, it became important to understand the braid representatives of a given link. Markov's theorem relates these representatives by two moves, conjugacy in the braid group, and (de)stabilization, which passes between braid groups. Markov's moves and braid group algebra have become fundamental in Jones' pioneering work and its later continuation towards quantum invariants. Conjugacy is, starting with Garside's, and later many others' work, now relatively well group-theoretically understood. In contrast, the effect of (de)stabilization on conjugacy classes of braid representatives of a given link is in general difficult to control. Only in very special situations can these conjugacy classes be well described.
We are concerned with the question when infinitely many conjugacy classes of $n$-braid representatives of a given link occur. Birman and Menasco introduced a move called exchange move, and proved that it necessarily underlies the switch between many conjugacy classes of $n$-braid representatives of a given link.
After some very brief general introduction to knots and braids and their applications, we will discuss several results when the exchange move is also sufficient for generating infinitely many conjugacy classes of braid representatives.

Sinai Robins (Universidade de São Paulo)17.11.21 16:30 Online The null set of a polytope, and the Pompeiu property for polytopes

We study the null set $N(\P)$ of the Fourier transform of a polytope P in $\R^d$, and we find that this null set does not contain (almost all) circles in $\R^d$. As a consequence, the null set does not contain the algebraic varieties $\{ z \in \C^d \mid z_1^2 + \cdots + z_d^2 = \alpha \}$, for each fixed $\alpha \in \C$. In 1929, Pompeiu asked the following question. Suppose we have a convex subset P in R^d, and a function f, defined over R^d, such that the integral of f over P vanishes, and all of the integrals of f, taken over each rigid motion of P, also vanish. Does it necessarily follow that f = 0? If the answer is affirmative, then the convex body P is said to have the Pompeiu property. It is a conjecture that in every dimension, balls are the only convex bodies that do not have the Pompeiu property. Here we get an explicit proof that the Pompeiu property is true for all polytopes, by combining our work with the work of Brown, Schreiber, and Taylor from 1973. Our proof uses the Brion-Barvinok theorem in combinatorial geometry, together with some properties of the Bessel functions. The original proof that polytopes (as well as other bodies) possess the Pompeiu property was given by Brown, Schreiber, and Taylor (1973) for dimension 2. In 1976, Williams observed that the same proof also works for $d>2$ and, using eigenvalues of the Laplacian, gave another proof valid for $d \geq 2$ that polytopes indeed have the Pompeiu property. The null set of the Fourier transform of a polytope has also been used in a different direction, by various researchers, to tackle problems in multi-tiling Euclidean space. Thus, the null set of a polytope is interesting for several applications, including discrete versions of this problem that we will mention, which are generally unsolved. This is joint work with Fabrício Caluza Machado.

Austin Alderete (UT Austin)10.11.21 16:30 Online A polymake extension for computing the homology groups of minor-closed classes of matroids

We present a polymake extension for performing computations in the intersection ring of matroids. Addition in the ring is carried out on the indicator vectors of maximal chains of flats while the product is the usual matroid intersection when the intersection is loopfree and zero otherwise. The primary feature of this extension is the ability to compute the homology groups of the intersection ring induced by deletion and contraction as well as those of any subring generated by a minor-closed class of matroids.

MaRDI03.11.21 16:30 MPI Leipzig MaRDI Kickoff Workshop

Davide Lofano (TU Berlin)27.10.21 16:30 H 0107 Hadamard Matrix Torsion

After a brief overview about torsion in homology and examples of complexes with small torsion and few vertices we will focus our attention on a particular series of examples. In particular, we will construct a series HMT(n) of 2-dimensional simplicial complexes with huge torsion, |H_1(HMT(n))|=|det(H(n))|=n^(n/2), where the construction is based on the Hadamard matrices H(n) and they have linearly many vertices in n. Our explicit series improves a previous construction by Speyer, narrowing the gap to the highest possible asymptotic torsion growth achieved by Newman via a randomized construction.

Sylvain Spitz (TU Berlin)20.10.21 16:30 H 0107 Generalized Permutahedra and Optimal Auctions

We study a family of convex polytopes, called SIM-bodies, which were introduced by Giannakopoulos and Koutsoupias (2018) to analyze so-called Straight-Jacket Auctions. First, we show that the SIM-bodies belong to the class of generalized permutahedra. Second, we prove an optimality result for the Straight-Jacket Auctions among certain deterministic auctions. Third, we employ computer algebra methods and mathematical software to explicitly determine optimal prices and revenues.

Petter Brändén (KTH) 13.10.21 16:30 Online Lorentzian polynomials on cones and the Heron-Rota-Welsh conjecture

We extend the theory of Lorentzian polynomials to convex cones. This is used to give a short proof of the log-concavity of the coefficients of the reduced characteristic polynomial of a matroid, and reprove the Hodge-Riemann relations of degree one for the Chow ring of a matroid. This is joint work with Jonathan Leake.

Georg Loho (University of Twente)25.08.21 16:30 Online Generalized permutahedra and complete classes of valuated matroids

Generalized permutahedra form an important class of polytopes occurring explicitly or implicitly in several branches of mathematics and beyond. I start with an overview of concepts related with generalized permutahedra from optimization and Discrete Convex Analysis. Valuated generalized matroids give rise to a particularly interesting subclass. I show some fundamental constructions for these objects. This leads to an answer to two open questions from auction theory and discrete convex analysis.

Chiara Meroni (MPI MiS)04.08.21 16:30 Online Fiber convex bodies

Given a convex polytope P and a projection map it is possible to construct the associated fiber polytope, that intuitively is the average of the fibers of P under this projection and has interesting combinatorial properties. In this joint work with Léo Mathis we study this construction for all convex bodies. The aim is to relate aspects of the original convex body with those of its fiber body. I will discuss theoretical results as well as some concrete examples.

Tobias Boege (Universität Magdeburg)28.07.21 16:30 Online The Gaussian conditional independence inference problem

Conditional independence is a ternary relation on subsets of a finite vector of random variables \xi. The CI statement \xi_i \CI \xi_j \mid \xi_K asserts that ``whenever the outcome of all the variables \xi_k, k \in K, is known, learning the outcome of \xi_i provides no further information on \xi_j''.
These relations are highly structured, in particular under assumptions about the joint distribution. The goal is to describe this by CI inference rules: given that certain CI statements hold, which other (disjunctions of) CI statements are implied under the distribution assumption?
This talk is about regular Gaussian distributions where conditional independence has an algebraic characterization in terms of subdeterminants of the covariance matrix and inference becomes a geometric problem concerning the vanishing of certain polynomials on varieties inside the cone of positive-definite matrices.
I first show that the inference problem for Gaussians is just as difficult as deciding whether a polynomial system with integer coefficients has a solution over the real numbers. Then, I present some approximations to the inference problem which exploit the special structure of the polynomials which are relevant for conditional independence. In these formulations, SAT solvers and linear programming are able to prove some (but not all) valid inference rules and they terminate much faster than a general method.

Claudia Yun (Brown University)14.07.21 16:30 Online The S_n-equivariant rational homology of the tropical moduli spaces \Delta_{2,n}

Fix non-negative integers g and n such that 2g-2+n>0, the tropical moduli space \Delta_{g,n} is a topological space that parametrizes isomorphism classes of n-marked stable tropical curves of genus g with total volume 1. These spaces are important because their reduced rational homology is identified equivariantly with the top weight cohomology of the algebraic moduli spaces M_{g,n}, with respect to the S_n-action of permuting marked points. In this talk, we focus on the genus 2 case and compute the characters of \tilde{H}_i(\Delta_{2,n};Q) as S_n-representations for n up to 8. To carry out the computations, we use a cellular chain complex for symmetric \Delta-complexes, a technique developed by Chan, Galatius, and Payne. We will also briefly mention work in progress that extends the computations to n=10, in collaboration with Christin Bibby, Melody Chan, and Nir Gadish. All computations are done in SageMath.

Ilia Itenberg (Sorbonne Université)07.07.21 16:30 Online Planes in cubic fourfolds

We discuss possible numbers of 2-planes in a smooth cubic hypersurface in the 5-dimensional projective space. We show that, in the complex case, the maximal number of planes is 405, the maximum being realized by the Fermat cubic. In the real case, the maximal number of planes is 357. The proofs deal with the period spaces of cubic hypersurfaces in the 5-dimensional complex projective space and are based on the global Torelli theorem and the surjectivity of the period map for these hypersurfaces, as well as on Nikulin's theory of discriminant forms. Joint work with Alex Degtyarev and John Christian Ottem.

Holger Eble (TU Berlin)30.06.21 16:30 Online Enumerating Chambers of Hyperplane Arrangements with Symmetry

We introduce a new algorithm for enumerating chambers of hyperplane arrangements which exploits their underlying symmetry groups. Our algorithm counts the chambers of an arrangement as a byproduct of computing its characteristic polynomial. We showcase our julia implementation, based on OSCAR, on examples coming from hyperplane arrangements with applications to physics and computer science. This is joint work with Taylor Brysiewicz and Lukas Kuehne.

Manuel Radons (TU Berlin)23.06.21 16:30 Online Edge-unfolding nested prismatoids

A 3-Prismatoid is the convex hull of two convex polygons A and B which lie in parallel planes H_A, H_B in R^3. Let A' be the orthogonal projection of A onto H_B. A prismatoid is called nested if A' is properly contained in B, or vice versa. We show that every nested prismatoid has an edge-unfolding to a non-overlapping polygon in the plane.

Christoph Hertrich (TU Berlin)16.06.21 16:30 Online Towards Lower Bounds on the Depth of ReLU Neural Networks

We contribute to a better understanding of the class of functions that is represented by a neural network with ReLU activations and a given architecture. Using techniques from mixed-integer optimization, polyhedral theory, and tropical geometry, we provide a mathematical counterbalance to the universal approximation theorems which suggest that a single hidden layer is sufficient for learning tasks. In particular, we investigate whether the class of exactly representable functions strictly increases by adding more layers (with no restrictions on size). We also present upper bounds on the sizes of neural networks required for exact function representation.

Matteo Gallet (RICAM)09.06.21 16:30 Online Mobile Icosapods

Pods are mechanical devices constituted of two rigid bodies, the base and the platform, connected via spherical joints by a number of other rigid bodies, called legs. The maximal number, when finite, of legs of a mobile pod is 20. In 1904, Borel designed a technique to construct examples of such 20-pods over the complex numbers. We show that recent results about spectrahedra provide a way to determine real solutions for Borel’s construction. This is a joint work with Georg Nawratil, Jon Selig, and Josef Schicho.

Marieke van der Wegen (Utrecht University)02.06.21 16:30 Online Computing stable gonality is hard

Based on analogies between algebraic curves and graphs, there are several graph parameters defined. In this talk we will study the so-called stable gonality. The stable gonality is a measure for the complexity of a graph and is defined using morphisms from a graph to a tree. We show that computing the stable gonality of a graph is NP-hard. This is joint work with Dion Gijswijt and Harry Smit.

Guido Montúfar (MPI Leipzig and UCLA)26.05.21 16:30 Online Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums

We present results on the number of linear regions of the functions that can be represented by artificial feedforward neural networks with maxout units. A rank-k maxout unit is a function computing the maximum of k linear functions. For networks with a single layer of maxout units, the linear regions correspond to the upper vertices of a Minkowski sum of polytopes. We obtain face counting formulas in terms of the intersection posets of tropical hypersurfaces or the number of upper faces of partial Minkowski sums, along with explicit sharp upper bounds for the number of regions for any input dimension, any number of units, and any ranks, in the cases with and without biases. Based on these results we also obtain asymptotically sharp upper bounds for networks with multiple layers. This is joint work with Yue Ren and Leon Zhang.

Simon Telen (MPI MiS Leipzig)19.05.21 16:30 Online Likelihood equations and scattering amplitudes

We identify the scattering equations from particle physics as the likelihood equations for a particular statistical model. The scattering potential plays the role of the log-likelihood function. We employ recent methods from numerical nonlinear algebra to solve challenging instances of the scattering equations. We revisit the theory of stringy canonical forms proposed by Arkani-Hamed, He and Lam, introducing positive statistical models and their amplitudes. This is joint work with Bernd Sturmfels.

Sophie Rehberg (FU Berlin)12.05.21 16:30 Online Combinatorial reciprocity theorems for generalized permutahedra, hypergraphs, and pruned inside-out polytopes

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). Our proof relies, aside from the reciprocity for generalized permutahedra, only on elementary geometric and combinatorial properties of hypergraphs and their associated polytopes.

Sandra Di Rocco (KTH)05.05.21 16:30 Online Iterated discriminants

The Hyperdeterminant is a celebrated tool in tensor theory, geometrically it represents the discriminant of a Segre embedding. The Segre embedding is a toric map associated to a Cayley sum, probably the basic example of Cayley polytopes. Unlike other discriminants the hyperdeterminant is at times accessible to computation due to a decomposition method developed by Schäfli. We propose a generalisation of the Schäfli method to discriminants associated to general Cayley sums and show how this can be treated as a discriminant of a system of polynomials. This is joint work with A. Dickenstein and R. Morrison.

Daniel Corey (University of Wisconsin-Madison)28.04.21 16:30 Online Initial degenerations of Grassmannians and spinor varieties

We construct closed immersions from initial degenerations of Gr_0(d,n)---the open cell in the Grassmannian Gr(d,n) given by the nonvanishing of all Plücker coordinates---to limits of thin Schubert cells associated to diagrams induced by the face poset of the corresponding tropical linear space. These are isomorphisms in many cases, including (d,n) equal to (2,n), (3,6) and (3,7). As an application, Gr_0(3,7) is schön, and the Chow quotient of Gr(3,7) by the maximal torus in PGL(7) is the log canonical compactification of the moduli space of 7 points in P^2 in linear general position, making progress on a conjecture of Hacking, Keel, and Tevelev. Finally, I will discuss recent work on extending these results to the Lie-type D setting.

Mario Kummer (TU Dresden)21.04.21 16:30 Online Iso Edge Domains

A Conjecture by Conway and Sloane from the 90s can be phrased as ''Every tropical abelian variety is determined by its tropical theta constants''. It was proved by Conway and Sloane in dimension up to 3 and by Vallentin in dimension 4. We prove it in dimension 5. The prove relies on the classification of iso-edge domains in dimension 5: These are a variant of the iso-Delaunay decomposition introduced by Baranovskii and Ryshkov. We further characterize the so-called matroidal locus in terms of the tropical theta constants in dimension up to 5 and point out connections to the tropical Schottky problem. The talk is based on a joint work with Mathieu Dutour Sikirić.

Antony Della Vecchia14.04.21 16:30 Online One Relator Groups and Regular Sectional Curvature

We present the notion of regular sectional curvature for angled 2-complexes. It is known that fundamental groups of angled 2-complexes with negative or nonpositive regular section curvature are coherent and, in certain cases, locally quasi-convex. We state some open problems for one-relator groups, describe a construction of angled 2-complexes for one-relator groups and provide some computer generated results supporting the claims.

Nicholas Williams (University of Leicester)10.03.21 16:30 Online New interpretations of the higher Stasheff–Tamari orders

The higher Stasheff–Tamari orders are two partial orders introduced in the 1990s by Kapranov, Voevodsky, Edelman and Reiner on the set of triangulations of a cyclic polytope. Edelman and Reiner conjectured these two orders to coincide, which remains an open problem today. In this talk we give new combinatorial interpretations of the orders. These interpretations differ depending on whether the cyclic polytope is 2d-dimensional or (2d + 1)-dimensional, but are expressed in each case in terms of the d-skeleton of the triangulation. This naturally leads us to also characterise the d-skeletons of triangulations of (2d + 1)-dimensional cyclic polytopes, complementing the description of the d-skeleton of a 2d-dimensional triangulation given by Oppermann and Thomas. Our results make the conjectured equivalence of the orders a more tractable problem, and we use them to run computational experiments checking the conjecture, to which we find no counter-examples. Our results also have interpretations in the representation theory of algebras, but we will not discuss these connections.

Kaie Kubjas (Aalto University)03.03.21 16:30 Online Identifying 3D Genome Organization in Diploid Organisms via Euclidean Distance Geometry

The 3D organization of the genome plays an important role for gene regulation. Chromosome conformation capture techniques allow one to measure the number of contacts between genomic loci that are nearby in the 3D space. In this talk, we study the problem of reconstructing the 3D organization of the genome from whole genome contact frequencies in diploid organisms, i.e. organisms that contain two indistinguishable copies of each genomic locus. In particular, we study the identifiability of the 3D organization of the genome and optimization methods for reconstructing it. This talk is based on joint work with Anastasiya Belyaeva, Lawrence Sun and Caroline Uhler.

Malte Renken (TU Berlin)24.02.21 16:30 Online What does the Cyclic Polytope have to do with Visibility Graphs?

In the 90's the study of visibility graphs prompted the definition of "persistent graphs", a class of vertex-ordered graphs defined by three simple combinatorial properties. We reveal a surprising connection of these persistent graphs to the triangulations of the 3-dimensional cyclic polytope via a natural bijection.
(Joint work with Vincent Froese)

Jorge Olarte (TU Berlin)10.02.2021 17:00 Online The tropical symplectic Grassmannian

The symplectic Grassmannian SpGr(k,2n) is the space of a all linear subspaces of dimension k of a vector space of dimension 2n which are isotropic with respect to a symplectic form. We look at several equivalent characterizations of isotropic linear subspaces and formulate a tropical analog for each, such as, for example, being in the tropicalization of the symplectic Grassmannian. It turns out that in the tropical world these characterizations are no longer equivalent and we will see exactly for which k and n does one characterization imply another. This is joint work with George Balla.

Oguzhan Yürük (TU Berlin)10.02.2021 16:30 Online Detecting the Regions of Multistaionarity in CRNT via Symbolic Nonnegativity Certificates

Parameterized ordinary differential equation systems are crucial for modeling in biochemical reaction networks under the assumption of mass-action kinetics. Various questions concerning the signs of multivariate polynomials in positive orthant arise from studying the solutions' qualitative behavior with respect to parameter values, in particular the existence of multistationarity. In this work, we revisit a method of detecting multistationarity, in which we utilize the circuit polynomials to find symbolic certificates of nonnegativity for 2-site phosphorylation cycle in a recent work of the speaker joint with Elisenda Feliu, Nidhi Kaihnsa and Timo de Wolff. Moreover, we will give a description of all possible certificates that can arise from 2-site phosphorylation cycle, and provide further insight into the number of positive steady states of the n-site phosphorylation cycle model.

Siddarth Kannan (Brown University)03.02.2021 16:30 Online Symmetries of tropical moduli spaces of curves

I will briefly introduce the moduli space of n-marked stable tropical curves of genus g, and then discuss the combinatorial calculation of its automorphism group. I will conclude by talking about natural follow-up questions to this result, motivated by connections to the Deligne-Mumford moduli stack of marked stable algebraic curves and the mapping class group.

Abhishek Rathod (TU Munich)27.01.202116:30Online Parameterized inapproximability of Morse matching

In this talk, we look at the problem of minimizing the number of critical simplices (Min-Morse) from the point of view of inapproximability and parameterized complexity. Let n denote the size of a simplicial complex. We first show that Min-Morse can not be approximated within a factor of 2^{\log^{(1-\epsilon)}n}- \delta, for any \epsilon,\delta>0, unless NP \subseteq QP. Our second result shows that Min-Morse is WP-hard with respect to the standard parameter. Next, we show that Min-Morse with standard parameterization has no FPT-approximation algorithm for any approximation factor \rho, unless WP = FPT. Since the gadgets involved in our reduction are 2-complexes, the above hardness results are applicable for all complexes of dimension \geq 2.

Christian Steinert (RWTH Aachen University)20.01.202116:30Online A Diagrammatic Approach to String Polytopes

It is a common principle of mathematics to translate problems from one area of research to another and solve them there. A very particular example of this approach is the study of string polytopes, originally introduced and studied by Berenstein and Zelevinsky as well as Littelmann. Their original motivation stems from representation theory but they also provide fruitful tools in the algebraic geometry of flag varieties and more as studied by Caldero as well as Alexeev and Brion. Although these string polytopes have been around for more than 30 years, results on their combinatorial properties are scarce.
After a brief introduction to the history and motivation behind those polytopes, we will present a recent integrality criterion for a special family of string polytopes. For its proof we will explain a diagrammatic way to classify the vertices of a given string polytope. As a corollary one can show that each partial flag variety admits a toric degeneration to a Gorenstein Fano variety.

Dhruv Ranganathan (Universtiy of Cambridge)13.01.202116:30Online Donaldson-Thomas theory and the secondary polytope

Donaldson-Thomas theory extracts numerical invariants from an algebraic variety X by examining the geometry of the Hilbert schemes of X. While the sister subject of Gromov-Witten theory has had a long and rich interaction with tropical and polyhedral methods, the relationship between the Hilbert scheme and tropical geometry is less developed. I will give an introduction to tropical and logarithmic aspects of Donaldson-Thomas theory, from the point of view of the GKZ secondary polytope construction, and generalizations thereof. This is based on joint work with Davesh Maulik (MIT).

Michael Joswig (TU Berlin)09.12.202016:30Online Moduli of tropical curves - data and algorithms

In joint work with Sarah Brodsky, Ralph Morrison and Bernd Sturmfels in 2015 we computed the moduli of tropical plane curves of genus $\leq 4$. After a brief summary of the mathematical results the focus of this presentation is about the computational methods and the 400MB of data produced. We will see how this is being used for further research (ongoing joint work with Dominic Bunnett). On the way we will touch upon general questions concerning data in mathematics.

Melody Chan (Brown University)02.12.202016:30Online Tropical abelian varieties

I'll give an introduction to the moduli space of tropical abelian varieties, assuming no background in tropical geometry. Lots of different combinatorics arises, including the beautiful century-old combinatorics of Voronoi reduction theory, perfect quadratic forms, regular matroids, and metric graphs. On the geometric side, it relates to toroidal compactifications of the classical moduli space A_g of abelian varieties. I'll explain how, and, time permitting, I'll report on work-in-progress in which we use tropical techniques to find new rational cohomology classes in A_g in a previously inaccessible range. Joint work with Madeline Brandt, Juliette Bruce, Margarida Melo, Gwyneth Moreland, and Corey Wolfe.

Kemal Rose (TU Berlin)25.11.202016:30Online Certifying roots of polynomial systems using interval arithmetic

We report on an implementation of the Krawczyk method which establishes interval arithmetic as a practical tool for certification in numerical algebraic geometry. Our software HomotopyContinuation.jl now has a built-in function certify, which proves the correctness of an isolated solution to a square system of polynomial equations. This implementation dramatically outperforms earlier approaches to certification.

Benjamin Schröter (KTH Stockholm)18.11.202016:30Online Reconstructing Matroid Polytopes

This talk deals with two fundamental objects of discrete mathematics that are closely related - (convex) polytopes and matroids. Both appear in many areas of mathematics, e.g., algebraic geometry, topology and optimization.
A classical question in polyhedral combinatorics is 'Does the vertex-edge graph of a d dimensional polytope determine its face lattice?'. In general the answer is no, but a famous result of Blind and Mani, and later Kalai is a positive answer of that question for simple polytopes. In my talk I discuss this reconstructability question for the special class of matroid (base) polytopes. Matroids encode an abstract version of dependency and independency, and thus generalize graphs, point configurations in vector spaces and algebraic extensions of fields. Maximal independent sets in a matroid satisfy a basis-exchange axiom. The exchanges correspond to edges in the basis-exchange graph which is the vertex-edge graph of the matroid polytope.
This is joint work with Guillermo Pineda-Villavicencio

Nick Early (Perimeter Institute for Theoretical Physics)11.11.202016:30Online Combinatorial Geometries: From Polyhedral Subdivisions to Scattering Amplitudes

In 1948, Richard Feynman introduced a formalism in Quantum Field Theory to organize the expansion of a scattering amplitude as a sum of elementary rational functions, labeled by graphs. These graphs, now called Feynman diagrams, specify which singularities of the amplitude are compatible and can appear simultaneously.
In the past year this question of compatibility has been given the following interpretation: given two matroid subdivisions of the second hypersimplex $\Delta_{2,n}$, when is their common refinement also a matroid subdivision?
Motivated in part by recent joint works with Cachazo, and Cachazo Guevara and Mizera, I will discuss how basic constructions in tropical geometry allow this question to be reformulated -- and generalized to arbitrary hypersimplices $\Delta_{k,n}$ -- as a statement about weakly separated collections, in the case when the maximal cells in the subdivisions are positroid polytopes.

Dominic Bunnett (TU Berlin)04.11.202016:30Online Embedded stacky fans and tropical moduli spaces

Stacky fans are orbifold objects in discrete geometry with a rich combinatorial structure. They arise naturally as the moduli spaces of tropical curves. Explicitly, a stacky fan is built from polyhedral cones quotiented out by finite groups.
We study stacky fans embedded in others and offer algorithms to compute their relative homology. We then apply this to specific loci of tropically smooth plane curves embedded in the moduli of genus 3 tropical curves. This is joint ongoing work with Michael Joswig.

Rainer Sinn (University of Leipzig)28.10.202016:30Online Realization spaces of polytopes

We study a simple model of the realization space of a polytope that lends itself to the application of the implicit function theorem. We explore how far this basic tool can carry us. Combined with quite elementary combinatorial arguments, this recovers most of the known results of “nice” realization spaces.

Federico Castillo (MPI Leipzig)21.10.202016:30Online The space of Minkowski Summands

Given a polytope P we study the set of all possible Minkowski summands. Being a Minkowski summand is equivalent to normal (or strongly combinatorial) equivalence. Different points of views provide different looking (but equivalent) parametrizations of the space of Minkowski summands as a polyhedral cone. We will go over several examples like polygons, permutohedra, cubes, and more.

Leonid Monin (University of Bristol)14.10.202016:30Online Inversion of matrices, ML-degrees and the space of complete quadrics

In my talk I will discuss the following questions: (1) How many quadrics go through *k* generic points and are tangent to *m * generic hyperplanes? (2) What is the maximum likelihood degree of a general linear concentration model? (3) What is the degree of the variety *L-1* obtained as the closure of the set of inverses of matrices from a generic linear subspace *L* of Sym*n*? In fact, all three questions are equivalent! First I will briefly explain why this is the case, and then I will describe several approaches to the above questions and possible answers they lead to. This is joint work in progress with Laurent Manivel, Mateusz Michalek, Tim Seynnaeve, Martin Vodicka, Andrzej Weber, and Jaroslaw A. Wisniewski.

Karin Schaller (FU)07.10.202016:30Online Mirror symmetry constructions for quasi-smooth Calabi-Yau hypersurfaces in weighted projective spaces

We consider a general combinatorial framework for constructing mirrors of quasi-smooth Calabi-Yau hypersurfaces defined by weighted homogeneous polynomials. Our mirror construction shows how to obtain mirrors being Calabi-Yau compactifications of non-degenerate affine hypersurfaces associated to certain Newton polytopes. This talk is based on joint work with Victor Batyrev.

Lukas Kühne (Hebrew Universiy of Jerusalem)30.09.202016:30Online The Resonance Arrangement

The resonance arrangement is the arrangement of hyperplanes which has all nonzero 0/1-vectors in R^n as normal vectors. It is also called the all-subsets arrangement. Its chambers appear in algebraic geometry, in mathematical physics and as maximal unbalanced families in economics.
In this talk, I will present a universality result of the resonance arrangement. Subsequently, I will report on partial progress on counting its number of chambers. Along the way, I will review some basics of the combinatorics of general hyperplane arrangements.

Jaeho Shin (Seoul National University)26.08.202016:30Online Polytropes and Tropical Linear Spaces

A polytrope is a convex polytope that is expressed as the tropical convex hull of a finite number of points. It is well known that every bounded cell of a tropical linear space is a polytrope, and its converse statement has been a conjecture. We develop an elementary approach to the relationship between tropical convexity and tropical linearity, and show that the conjecture holds in dimension up to 3 and fails in every higher dimension. Thus, tropical convexity is strictly bigger than tropical linearity.

Yue Ren (Swansea University)29.07.202016:30Online TBA

Stephane Gaubert (INRIA and CMAP, Ecole polytechnique, CNRS)08.07.202016:30Online Understanding and monitoring the evolution of the Covid-19 epidemic from medical emergency calls: the example of the Paris area

We portray the evolution of the Covid-19 epidemic during the crisis of March-April 2020 in the Paris area, by analyzing the medical emergency calls received by the EMS of the four central departments of this area (Centre 15 of SAMU 75, 92, 93 and 94). Our study reveals strong dissimilarities between these departments. We show that the logarithm of each epidemic observable can be approximated by a piecewise linear function of time. This allows us to distinguish the different phases of the epidemic, and to identify the delay between sanitary measures and their influence on the load of EMS. This also leads to an algorithm, allowing one to detect epidemic resurgences. We rely on a transport PDE epidemiological model, and we use methods from Perron-Frobenius theory and tropical geometry.

Mara Belotti (SISSA)24.06.202016:30Online Topology of rigid isotopy classes of geometric graphs

We study the topology of rigid isotopy classes of geometric graphs on n vertices in a d-dimensional Euclidean space. We consider in particular two different regimes: a large number of vertices for the graphs (n large) and a large dimension of the space in which the graphs live (d large). In both cases we make considerations on the number of such classes and study their Betti numbers. In particular, for the second case we register a "shift to infinity of the topology". This is joint work with A.Lerario and A.Newman.

Raman Sanyal (Goethe University Frankfurt)17.06.202016:30Online Inscribable fans, type cones, and reflection groupoids

Steiner posed the question if any 3-dimensional polytope had a realization with vertices on a sphere. Steinitz constructed the first counter examples and Rivin gave a complete resolution. In dimensions 4 and up, Mnev's universality theorem renders the question for inscribable combinatorial types hopeless. In this talk, I will address the following refined question: Given a polytope P, is there a normally equivalent polytope with vertices on a sphere? That is, can P be deformed into an inscribed polytope while preserving its normal fan? It turns out that the answer gives a rich interplay of geometry and combinatorics, involving local reflections and type cones. This is based on joint work with Sebastian Manecke (who will continue the story in the FU discrete geometry seminar next week).

Taylor Brysiewicz (Texas A&M University)03.06.202016:30Online The degree of Stiefel manifolds

The Stiefel manifold is the set of orthonormal bases for k-planes in an n-dimensional space. We compute its degree as an algebraic variety in the space of k-by-n matrices using techniques from classical algebraic geometry, representation theory, and combinatorics. We give a combinatorial interpretation of this degree in terms of non-intersecting lattice paths. (This is joint work with Fulvio Gesmundo)

Thorsten Theobald (Goethe University Frankfurt)27.05.202016:30Online Conic stabilility of polynomials and spectrahedra

In the geometry of polynomials, the notion of stability is of prominent importance. The purpose of the talk is to discuss its recent generalization to conic stability. Given a convex cone K in real n-space, a multivariate polynomial f in C[z] is called K-stable if it does not have a root whose vector of the imaginary parts is contained in the interior of $K$. If $K$ is the non-negative orthant, then $K$-stability specializes to the usual notion of stability of polynomials. In particular, we focus on $K$-stability with respect to the positive semidefinite cone and develop stability criteria building upon the connection to the containment problem for spectrahedra, to positive maps and to determinantal representations. These results are based on joint work with Papri Dey and Stephan Gardoll.

Luis Carlos Garcia Lirola (Kent State University)20.05.202016:30Online Volume product and metric spaces

Given a finite metric space M, the set of Lipschitz functions on M with Lipschitz constant at most 1 can be identified with a convex polytope in R^n. In this talk, we will show that there is a strong connection between the geometric properties of this polytope (as the vertices and the volume product) and the properties of the metric space M. We will also relate this study with a famous open problem in Convex Geometry, the Mahler conjecture, on the product of the volume of a convex body and its polar. This is a joint work with M. Alexander, M. Fradelizi, and A. Zvavitch.

Georg Loho (London School of Economics)13.05.202016:30Online Oriented Matroids from Triangulations of Products of Simplices

Classically, there is a rich theory in algebraic combinatorics surrounding the various objects associated with a generic real matrix. Examples include regular triangulations of the product of two simplices, coherent matching fields, and realizable oriented matroids. In this talk, we will extend the theory by skipping the matrix and starting with an arbitrary triangulation of the product of two simplices instead. In particular, we show that every polyhedral matching field induces oriented matroids. The oriented matroid is composed of compatible chirotopes on the cells in a matroid subdivision of the hypersimplex. Furthermore, we give a corresponding topological construction using Viro’s patchworking. This talk will also sketch the relationship between Baker-Bowler’s matroids over hyperfields and our work. This is joint work with Marcel Celaya and Chi-Ho Yuen.

Martin Winter (TU Chemnitz)06.05.202016:30Online Edge-Transitive Polytopes

Despite the long history of the study of symmetric polytopes, aside from two extreme cases, the general transitivity properties of convex polytopes are still badly understood. For example, it has long been known that there are five flag-transitive (aka. regular) polyhedra (called, Platonic solids), six flag-transitive 4-polytopes and exactly three flag-transitive d-polytopes for any d>=5. The symmetry requirement of flag-transitivity is therefore quite restrictive for convex polytopes. On the other end of the spectrum, the class of vertex-transitive (aka. isogonal) polytopes is as rich as the category of finite groups. There seems to be little known about intermediate symmetries, like transitivity on edges or k-faces for any k>=2, and their interactions.
In this talk we discuss the next most accessible transitivity, namely, edge-transitivity of convex polytopes. That is, we ask for a classification of convex polytopes in which all edges are identical under the symmetries of the polytope. Despite this restriction feeling more similar to vertex-transitivity than to flag-transitivity, we will see that the contrary seems to be the case: the class of edge-transitive polytopes appears to be quite restricted. We give, what we believe to be, a complete list of all edge-transitive polytopes, as well as a full classification for certain interesting sub-classes. Thereby, we show how edge-transitive polytopes can be studied with the tools of spectral graph theory.

Marek Kaluba29.04.202017:00Online Random polytopes in Machine Learning

In this talk I will describe very recent work on analyzing different models of auto-encoder neural networks using random polytopes. In general, a class of neural networks known as auto-encoders can be understood as a low- dimensional (piecewise linear) embedding ℝᴺ → ℝⁿ (with N >> n), where points in the domain are e.g. images (in their pixel form) and each dimension the range extracts a single "feature".
Although understanding the properties of these embedings is crucial for explainability (e.g. interpreting the decisions taken by the network), the research in this direction has been undertaken only from the statistical point of view. We introduce `random polytope descriptors` which try to approximate datasets in the feature space by possibly tight convex bodies. This is the first attempt at understanding the very coarse geometry of embeddings provided by neural networks. Using such descriptors one can answer e.g. if the natural clusters of of images has been preserved or distorted by the neural network, and if the embedding actually separates them (the question of entanglement).
We use random polytope descriptors to examine the behaviour of auto-encoder networks in both vanilla and variational form, and provide first evidence for susseptibility of the latter to out-of-distribution attacks.
This is joint work with L.Ruffs (TUB, Department of Electrical Engineering and Computer Science) and M.Joswig (TUB, Chair of Discrete Mathematics/Geometry; MPI for Mathematics in the Sciences, Leipzig).

Francisco Criado29.04.202016:30Online Borsuk’s problem

In 1932, Borsuk proved that every 2-dimensional convex body can be divided in three parts with strictly smaller diameter than the original. He also asked if the same would hold for any dimension d: is it true that every d-dimensional convex body can be divided in (d+1) pieces of strictly smaller diameter?
The answer to this question is positive in 3 dimensions (Perkal 1947), but in 1993, Kahn and Kalai constructed polytopal counterexamples in dimension 1325. Nowadays, we know that the answer is "no" for all dimensions d>=64 (Bondarenko and Jenrich 2013). It remains open for every dimension between 4 and 63
In this talk we introduce the problem, and we show the proofs for dimension 2 and 3. plus computational ideas on how to extend these solutions to dimension 4.

Jonathan Spreer (University of Sydney)22.04.202016:30MA 621 Linking topology and combinatorics: Width-type parameters of 3-manifolds

Many fundamental topological problems about 3-manifolds are algorithmically solvable in theory, but continue to withstand practical computations. In recent years some of these problems have been shown to allow efficient solutions, as long as the input 3-manifold comes with a sufficiently "thin" presentation.
More specifically, a 3-manifold given as a triangulation is considered thin, if the treewidth of its dual graph is small. I will show how this combinatorial parameter, defined on a triangulation, can be linked back to purely topological properties of the underlying manifold. From this connection it can then be followed that, for some 3-manifolds, we cannot hope for a thin triangulation.
This is joint work with Kristóf Huszár and Uli Wagner

Ayush Kumar Tewari15.04.202017:00Online Forbidden patterns in tropical planar curves and Panoptagons

Dominic Bunnett15.04.202016:30Online Geometric discriminants and moduli

A discriminant is a subset of a function space consisting of singular functions. We shall consider discriminants of finite dimensional vector spaces of polynomials defining hypersurfaces in a toric variety. In the best case scenario (for plane curves for example), the discriminant is an irreducible hypersurface, however this is not the case for almost any other toric variety. We discuss positive results on the geometry of discriminants of weighted projective spaces and how to compute them via the A-discriminants of Gelfand, Kapranov and Zelevinsky.

Robert Loewe08.04.202016:30Online Minkowski decompositions of generalized associahedra

We give an explicit subword complex description of the rays of the type cone of the g-vector fan of an finite type cluster algebra with acyclic initial seed. In particular, this yields a non-recursive description of the Newton polytopes of the F-polynomials as conjectured by Brodsky and Stump. We finally show that for finite type cluster algebras, the cluster complex is isomorphic to the totally positive part of the tropicalization of the cluster variety as conjectured by Speyer and Williams.

Lars Kastner01.04.202016:30Online Hyperplane arrangements in polymake

I will report on the implementation of hyperplane arrangements in polymake. Hyperplane arrangements appear in a wide variety of applications in tropical and algebraic geometry. An important construction is the induced subdivision. We will discuss the new HyperplaneArrangement object, its properties and our simple algorithm for constructing the cell subdivision.
This is joint work with Marta Panizzut.

Paul Vater25.03.202017:00Online Patchworking real tropical hypersurfaces

We take a look at the tropical version of Viro's combinatorial patchworking method, as well as a recent implementation in polymake. In particular we investigate an efficient way of computing the homology with Z_2 coefficients of such a patchworked hypersurface.

Andrew Newman25.03.202016:30Online A two-step random polytope model

We consider a model for generating non-simple, non-simplicial random polytopes. The first step of the random process generates a random polytope P via random hyperplanes tangent to the d-dimensional sphere; the second step is given by the convex hull of a binomial sample of the vertices of P. In this talk we will discuss some ongoing work establishing results about the expected complexity of such polytopes.

Oguzhan Yuruk11.03.202016:30MA 621 Understanding the Parameter Regions of Multistationarity in Dual Phosporylation Cycle via SONC

Parameterized ordinary differential equation systems are crucial for modeling in biochemical reaction networks under the assumption of mass-action kinetics. Existence of multiple positive solutions in systems arising from biochemical reaction network are crucial since it is linked to cellular decision making and memory related on/off responses. Recent developments points out that the multistationarity, along with some other qualitative properties of the solutions, is related to various questions concerning the signs of multivariate polynomials in positive orthant. In this work, we provide further insight to the set of kinetic parameters that enable or preclude multistationarity of dual phosphorylation cycle by utilizing circuit polynomials to find symbolic certificates of nonnegativity. This is a joint work with Elisenda Feliu, Nidhi Kaihnsa and Timo de Wolff.

Ralph Morrison (Williams College)26.02.202016:30MA 621 Tropically planar graphs: geometry and combinatorics

Tropically planar graphs are graphs that arise as the skeletons of smooth tropical plane curves, which are dual to regular unimodular triangulations of lattice polygons. In this talk we study what geometric properties such graphs have in the moduli space of metric graphs, as well as the combinatorial properties these graphs satisfy. This talk will include older work with Brodsky, Joswig, and Sturmfels; newer work with Coles, Dutta, Jiang, and Scharf; and ongoing work with Tewari.

Antonio Macchia (FU Berlin)12.02.202016:30MA 621 Binomial edge ideals of bipartite graphs

Binomial edge ideals are ideals generated by binomials corresponding to the edges of a graph, naturally generalizing the ideals of 2-minors of a generic matrix with two rows. They also arise naturally in the context of conditional independence ideals in Algebraic Statistics.
We give a combinatorial classification of Cohen-Macaulay binomial edge ideals of bipartite graphs providing an explicit construction in graph-theoretical terms. In the proof we use the dual graph of an ideal, showing in our setting the converse of Hartshorne's Connectedness theorem.
As a consequence, we prove for these ideals a Hirsch-type conjecture of Benedetti-Varbaro.
This is a joint work with Davide Bolognini and Francesco Strazzanti. Organizer: DM/G

Amy Wiebe (FU Berlin)05.02.202016:30MA 621 Combining Realization Space Models of Polytopes

In this talk I will present a model for the realization space of a polytope which represents a polytope by its slack matrix. This model provides a natural algebraic relaxation for the realization space, and comes with a defining ideal which can be used as a computational engine to answer questions about the realization space. We will see how this model is related to more classical realization space models (representing realizations by Gale diagrams or points of the Grassmannian). In particular, we will see these relationships can be used to improve computational efficiency of the slack model.

Matias Villagra (Pontifical Catholic University of Chile)29.01.202016:30MA 621 On a canonical symmetry breaking technique for polytopes

Given a group of symmetries of a polytope, a Fundamental Domain is a set of R^n that aims to select a unique representative of symmetric vectors, i.e. such that each point in the set is a unique representative under its G-orbit, effectively eliminating all isomorphic points of the polytope. The canonical Fundamental Domain found in the literature, which can be constructed for any permutation group, is NP-hard to separate even for structurally simple groups whose elements are disjoint involutions (Babai & Luks 1983).
We consider a recent set of inequalities that has been implemented in CPLEX as a symmetry breaking technique for arbitrary finite permutation groups (Salvagnin 2018). We show a strong connection of this set with the set of lexicographically maximal vectors (LEX), and show that it defines a Fundamental Domain with quadratic many facets on the dimension, yielding a polynomial time separation algorithm. Moreover, we study when LEX defines a closed set, which suggests a stronger way of breaking symmetries.
This is joint work with José Verschae and Léonard von Niederhäusern.

Andres R. Vindas Melendez (University of Kentucky)22.01.202016:30MA 621 The Equivariant Ehrhart Theory of the Permutahedron

In 2010, Stapledon described a generalization of Ehrhart theory with group actions. In 2018, Ardila, Schindler, and I made progress towards answering one of Stapledon's open problems that asked to determine the equivariant Ehrhart theory of the permutahedron. We proved some general results about the fixed polytopes of the permutahedron, which are the polytopes that are fixed by acting on the permutahedron by a permutation. In particular, we computed their dimension, showed that they are combinatorially equivalent to permutahedra, provided hyperplane and vertex descriptions, and proved that they are zonotopes. Lastly, we obtained a formula for the volume of these fixed polytopes, which is a generalization of Richard Stanley's result of the volume for the standard permutahedron. Building off of the work of the aforementioned, we determine the equivariant Ehrhart theory of the permutahedron, thereby resolving the open problem. This project presents combinatorial formulas for the Ehrhart quasipolynomials and Ehrhart Series of the fixed polytopes of the permutahedron, along with other results regarding interpretations of the equivariant analogue of the Ehrhart series. This is joint work with Federico Ardila (San Francisco State University) and Mariel Supina (UC Berkeley).

Simon Telen (KU Leuven)15.01.202016:30MA 621 Numerical Root Finding via Cox Rings

In this talk, we consider the problem of solving a system of (sparse) Laurent polynomial equations defining finitely many nonsingular points on a compact toric variety. The Cox ring of this toric variety is a generalization of the homogeneous coordinate ring of projective space. We work with multiplication maps in graded pieces of this ring to generalize the eigenvalue, eigenvector theorem for root finding in affine space. We use numerical linear algebra to compute the corresponding matrices, and from these matrices a set of homogeneous coordinates of the solutions. Several numerical experiments show the effectiveness of the resulting method, especially for solving (nearly) degenerate, high degree systems in small numbers of variables.


8th polymake workshop
February 2-4, 2017
TU Berlin
8th polymake workshop [1]
7th polymake workshop
January 28-30, 2016
TU Berlin
7th polymake workshop [2]
Meeting on Algebraic Vision 2015
October 8-9, 2015
TU Berlin
MAV [3]
Tropical geometry in Europe
March 30-31, 2015
TGE [4]
6th polymake workshop
December 5,2014
TU Berlin
6th polymake workshop [5]
5th polymake workshop
March 28, 2014
TU Berlin
5th polymake workshop [6]
4th polymake conference and developer meeting at TU Berlin
November 1-2, 2013
TU Berlin
4th polymake conference and developer meeting [7]
Delaunay Geometrie: Polytopes, Triangulations and Spheres
October 7-9,2013
FU Berlin
Second ERC "SDModels" Workshop [8]



------ Links: ------

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe

Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.
Copyright TU Berlin 2008