Seminar der Arbeitsgruppen Diskrete Mathematik / Geometrie & Diskrete Geometrie   📅

Homepage
https://www3.math.tu-berlin.de/combi/dmg/seminar/
Institute
TU Berlin
Head
Michael Joswig
Number of talks
157
June 2024
Discrete Math
Wed, 26.06.24 at 16:30
EN 058
Martin Ulirsch Goethe University Frankfurt am Main Link Icon
What is the tropicalization of a matrix?
Abstract. Tropicalization is a process that associates to an algebro-geometric object a piecewise linear polyhedral shadow that captures its essential combinatorial structure. In this talk, I will give an overview of the numerous ways on how to extract tropical information from a matrix over a non-Archimedean field. Each perspective will give rise to inherently quite different phenomena. Central instances of this rich panorama include the tropical geometry of vector bundles, logarithmic concavity results for valuated (bi-)matroids (using techniques from combinatorial Hodge theory), and the geometry of affine buildings.This talk draws from joint work with Andreas Gross and Dmitry Zakharov; Andreas Gross, Inder Kaur, and Annette Werner; Felix Röhrle; Jeff Giansiracusa, Felipe Rincon, and Victoria Schleis; Luca Battistella, Kevin Kühn, Arne Kuhrs, and Alejandro Vargas; as well as with Desmond Coles.
Discrete Math
Wed, 19.06.24 at 16:30
EN 058
Simon Schmidt Ruhr-Universität Bochum Link Icon
Introduction to nonlocal games and graph isomorphism games
Abstract. A nonlocal game consists of two players that collaborate to win a game against a referee. Comparing their performance with and without access to shared entangled particles allows us to probe the capabilities of entanglement. In this talk, we will give an introduction to nonlocal games. We will focus on the graph isomorphism game, in which the players try to convince the referee that they know an isomorphism between a fixed pair of graphs.
Discrete Math
Wed, 12.06.24 at 16:30
EN 058
Tristram Bogart Los Andes Link Icon
Discrete Math
Wed, 05.06.24 at 16:30
EN 058
Rene Brandenberg TU München Link Icon
Discrete Math
Wed, 05.06.24 at 16:30
EN 058
Tristram Bogart Los Andes Link Icon
Numerical Semigroups via Projections and via Quotients
Abstract. A numerical semigroup is any cofinite subset of the natural numbers that is closed under addition and contains 0. Numerical semigroups and their higher-dimensional cousins, known as affine semigroups, arise in optimization as well as in the study of toric ideals and varieties in algebraic geometry. Every numerical semigroup S has a unique minimal generating set, whose cardinality is called the embedding dimension e(S). If e(S) is large, it is natural to ask whether S can be ''encapsulated'' by some larger semigroup T with smaller embedding dimension. One notion of ''encapsulation'' is that S is the quotient of a numerical semigroup T by a number d, that is: S = T / d = {x: dx belongs to T\} Another, more geometric notion, is that S can be obtained as a coordinate projection of an affine semigroup T. Our main result is that these two forms of encapsulation are essentially equivalent. We also give various families of semigroups that both do and do not admit encapsulation. This project is joint work with Christopher O'Neill and Kevin Woods.
May 2024
Discrete Math
Wed, 22.05.24 at 16:30
EN 058
Paul Mücksch Leibniz Universität Hannover Link Icon
Combinatorial models of fibrations for hyperplane arrangements and oriented matroids
Abstract. The complement of an arrangement of hyperplanes in a complex vector space is a much studied interesting topological space. A fundamental problem is to decide when this space is aspherical, i.e. its universal covering space is contractible. For special classes of arrangements, such as the braid arrangements or more generally supersolvable arrangements, this can be achieved by utilizing fibrations which connect complements of arrangements of different rank. Another prominent space associated to an arrangement is its Milnor fiber -- the typical fiber of the evaluation map of the defining polynomial of the arrangement on its complement which is a smooth fibration by Milnor's famous result. This is a much more subtle topological invariant and it is still an open problem to understand its homology or even its first Betti number in conjunction with the combinatorial structure of the arrangement. I will present a new combinatorial approach to study such fibrations for arrangements which can be defined over the reals via oriented matroids. This is partly joint work with Masahiko Yoshinaga (Osaka University).
Discrete Math
Wed, 15.05.24 at 16:30
EN 058
John Abbott Link Icon
Determinants of Integer Matrices
Abstract. Computing the determinant of an integer matrix is a fundamental operation, and also the basis for determinant of other types of matrix e.g. with rational number or polynomial entries. Its utility means it is also a well-studied problem with several solutions which are ''good'' for certain classes of matrix. We present a new technique which is markedly better for ''awkward'' matrices where the existing methods all perform poorly. We consider only dense unstructured matrices.We recall briefly the most practical existing methods, then present the new approach. We combine these ''ingredients'' into an algorithm which is never worse than the best existing methods, and is markedly better for ''awkward'' matrices. An implementation will be included in OSCAR 1.1.No special knowledge is required, but it is helpful to know what Hadamard's determinant bound is.
Discrete Math
Wed, 08.05.24 at 16:30
EN 058
Tobias Boege Link Icon
Polyhedra in information theory
Abstract. A central object in information theory is the entropy region. Its closure in the euclidean topology is a convex cone and the elements of its dual cone are known as ''linear information inequalities''. They form a large portion of the arsenal of information theorists for solving channel capacity problems. In this talk, I will survey techniques for finding new information inequalities via so-called extension properties and conditional information inequalities. All of these techniques are secretly powered by polyhedra geometry. Hence, they can be implemented, automated and freely combined using the common language of linear programming. My vision is that information inequalities will be stored and thoroughly catalogued as discrete geometric objects.
April 2024
Discrete Math
Wed, 17.04.24 at 16:30
EN 058
Dmitrii Pavlov MPI Leipzig Link Icon
Santaló Geometry of Convex Polytopes
Abstract. The Santaló point of a convex polytope is the interior point which leads to a polar dual of minimal volume. This minimization problem is relevant in interior point methods for convex optimization, where the logarithm of the dual volume is known as the universal barrier function. When translating the facet hyperplanes, the Santaló point traces out a semi-algebraic set. In my talk I will describe this geometry and dive into connections with statistics, optimization and physics.
March 2024
Discrete Math
Wed, 20.03.24 at 16:30
EN 058
Yassine El Maazouz Link Icon
Discrete Math
Wed, 20.03.24 at 16:30
EN 058
George Balla and Marcel Wack and Lena Weis Link Icon
Arxiv Seminar
Discrete Math
Wed, 13.03.24 at 16:30
EN 058
Marina Garrote-López MPI MIS Link Icon
Identifiability of level-1 species networks from gene tree quartets
Abstract. Understanding evolutionary relationships, particularly in the context of hybridization and horizontal gene transfer, requires the inference of phylogenetic networks rather than traditional trees. While standard phylogenetic methods can infer gene trees from genetic data, these trees only indirectly reflect the species network topology due to horizontal inheritance and incomplete lineage sorting. Previous research has shown that certain network topologies and numerical parameters can be identified, but gaps remain in understanding the full topology of level-1 phylogenetic networks under the Network Multispecies Coalescent model. In this talk, we will give an overview of the inference of gene trees and address the identifiability problem of the topology of species networks, by investigating the ideals defined by quartet concordance factors for topological semi-directed networks. This is a joint work with Elizabeth S. Allman, Hector Baños and John A. Rhodes
Discrete Math
Wed, 13.03.24 at 16:30
EN 058
Marina Garrote MPI MIS Link Icon
Discrete Math
Wed, 06.03.24 at 16:30
EN 058
Nikola Sadovek Link Icon
Convex equipartitions inspired by the little cubes operad
Abstract. Nandakumar & Ramana Rap conjecture in the plane asks whether it is possible to divide a given convex polygon into n convex pieces such that the pieces have equal area and equal perimeter. A decade ago, two groups of authors (Karasev, Hubard & Aronov, and Blagojević & Ziegler) have shown that the regular convex partitions of a Euclidean space into n parts yield a solution to the (higher-dimensional analogue of the) Nandakumar & Ramana Rao conjecture when n is a prime power. This was obtained by parametrising the space of regular equipartitions of a given convex body by the classical configuration space. We repeat the process of regular convex partitions many times, first partitioning the Euclidean space into n_1 parts, then each part into n_2 parts, and so on. After doing this process k times, we obtain an ‘iterated' equipartion of a given convex body into n=n_1...n_k parts. We parametrise such iterated partitions by the (wreath) product of classical configuration spaces, and develop a new test-map scheme for solving the (higher dimensional analogue of) Nandakumar & Ramana Rao conjecture. The new scheme yields a solution to the conjecture if and only if all the n_i's are powers of the same prime number. Outside of this case, the conjecture remains open. This talk is based on the joint work with Pavle Blagojević.
February 2024
Discrete Math
Wed, 28.02.24 at 16:30
EN 058
Diane Maclagan Link Icon
Toric Bertini theorems in arbitrary characteristic
Abstract. The classical Bertini theorem on irreducibility when intersecting by hyperplanes is a standard part of the algebraic geometry toolkit. This was generalised recently, in characteristic zero, by Fuchs, Mantova, and Zannier to a toric Bertini theorem for subvarieties of an algebraic torus, with hyperplanes replaced by subtori. I will discuss joint work with Gandini, Hering, Mohammadi, Rajchgot, Wheeler, and Yu in which we give a different proof of this theorem that removes the characteristic assumption. The proof surprisingly hinges on better understanding algebraically closed fields containing the field of rational functions in n variables, which involve polyhedral constructions. An application is a tropical Bertini theorem.
Discrete Math
Wed, 21.02.24 at 16:30
EN 058
Saul Schleimer Link Icon
Solving the word problem in the mapping class group in quasi-linear time
Abstract. The word problem for the mapping class group was first posed, and first solved, by Dehn [1922] in his Breslau lectures. His method was rediscovered, and greatly extended, by Thurston [1970-80's]. Mosher [1995] proved that the mapping class group is automatic and so found a quadratic-time algorithm for the word problem. Hamidi-Tehran [2000] and Dynnikov [2023] gave quadratic-time algorithms using train-tracks. We give the first sub-quadratic-time algorithm. We combine the work of Dynnikov with a generalisation of the half-GCD algorithm to obtain an algorithm running in time O(n log^3(n)). This is joint work with Mark Bell.
Discrete Math
Tue, 20.02.24 at 16:30
EN 058
Yassine El Maazouz Link Icon
Discrete Math
Wed, 14.02.24 at 16:30
EN 058
Matthias Schymura TU Cottbus Link Icon
Deep lattice points in lattice zonotopes
Abstract. Given a polytope P and a point w in its interior one may want to measure the centrality (or the depth) of w within P. An established way to do so is via the so-called coefficient of asymmetry. This notion has been studied extensively in the realm of Hensley’s conjecture on the maximal volume of a d-dimensional lattice polytope that contains a fixed positive number of interior lattice points. Motivated by the Lonely Runner Conjecture from Diophantine approximation, we prove the existence of interior lattice points in lattice d-zonotopes, for which the coefficient of asymmetry is bounded above by an explicit function in O(d * log log d). In the general case of arbitrary lattice polytopes such a bound necessarily must be double exponential in the dimension. This is based on joint work with Matthias Beck.
Discrete Math
Wed, 07.02.24 at 16:30
EN 058
Alexander Kasprzyk University of Nottingham Link Icon
Machine learning detects terminal singularities
Abstract. I shall explain how we recently used machine learning to accurately determine when certain Q-factorial Fano toric varieties have (at worst) terminal singularities. Inspired by the success of the machine, we were then able to prove an elegant new combinatorial characterisation, although this result is certainly not what the machine had learnt. This is joint work with Tom Coates and Sara Veneziale (and a machine)
January 2024
Discrete Math
Wed, 31.01.24 at 16:30
EN 058
Ben Hollering TU Munich Link Icon
Computing Implicitizations of Multi-Graded Polynomial Maps
Abstract. In this talk, we'll introduce a new method for computing the kernel of a polynomial map which is homogeneous with respect to a multigrading. We first demonstrate how to quickly compute a matrix of maximal rank for which the map has a positive multigrading. Then in each graded component we compute the minimal generators of the kernel in that multidegree with linear algebra. We have implemented our techniques in Macaulay2 and show that our implementation can compute many generators of low degree in examples where Gröbner basis techniques have failed. This includes several examples coming from phylogenetics where even a complete list of quadrics and cubics were unknown. When the multigrading refines total degree, our algorithm is embarassingly parallel. This is joint work with Joseph Cummings.
Discrete Math
Wed, 24.01.24 at 16:30
EN 058
Victoria Schleis Universität Tübingen Link Icon
Tropical Quiver Grassmannians
Abstract. Grassmannians and flag varieties are important moduli spaces in algebraic geometry. Quiver Grassmannians are generalizations of these spaces arising in representation theory as the moduli spaces of quiver subrepresentations. These represent arrangements of vector subspaces satisfying linear relations provided by a directed graph.The methods of tropical geometry allow us to study these algebraic objects combinatorially and computationally. We introduce matroidal and tropical analoga of quivers and their Grassmannians obtained in joint work with Alessio Borzì and separate joint work with Giulia Iezzi; and describe them as affine morphisms of valuated matroids and linear maps of tropical linear spaces.
Discrete Math
Wed, 17.01.24 at 16:30
EN 058
Nikola Sadovek FU Berlin Link Icon
Convex equipartitions inspired by the little cubes operad
Abstract. Nandakumar & Ramana Rap conjecture in the plane asks whether it is possible to divide a given convex polygon into n convex pieces such that the pieces have equal area and equal perimeter. A decade ago, two groups of authors (Karasev, Hubard & Aronov, and Blagojević & Ziegler) have shown that the regular convex partitions of a Euclidean space into n parts yield a solution to the (higher-dimensional analogue of the) Nandakumar & Ramana Rao conjecture when n is a prime power. This was obtained by parametrising the space of regular equipartitions of a given convex body by the classical configuration space. We repeat the process of regular convex partitions many times, first partitioning the Euclidean space into n_1 parts, then each part into n_2 parts, and so on. After doing this process k times, we obtain an ‘iterated' equipartion of a given convex body into n=n_1...n_k parts. We parametrise such iterated partitions by the (wreath) product of classical configuration spaces, and develop a new test-map scheme for solving the (higher dimensional analogue of) Nandakumar & Ramana Rao conjecture. The new scheme yields a solution to the conjecture if and only if all the n_i's are powers of the same prime number. Outside of this case, the conjecture remains open.This talk is based on the joint work with Pavle Blagojević.
Discrete Math
Wed, 10.01.24 at 16:30
EN 058
Amos Onn Link Icon
Single Cell Lineage Reconstruction using Short Tandem Repeats
Abstract. Inferring the lineage relationships of single cells is a useful tool for an answer to a wide variety of fundamental questions. Current sequencing-based approaches rely on either genetic editing - not applicable for living humans - or on extensive coverage, which is non-scalable and might be affected by functional bias. Here we will present a scalable, low-cost method, which is based on targeted sequencing of Short Tandem Repeats (STRs), genomic regions known to be highly mutable. The unique mutation pattern of STRs and their high mutation rates present us with challenges specific to our method. In addition, since these regions are difficult to analyze and have no known biological function, they have not been studied very extensively. From read alignment, through mutations occurring in-vitro, to separate and compare alleles - we have developed various custom solutions, including ones using signal processing approaches, in order to analyze STRs, and were able to successfully reconstruct lineage trees, demonstrated by testing on data with a known reference. In this lecture I will describe the challenges of the analysis, our solutions to them, and the current state of the method, including open questions and directions for further research. I also want to go in depth into a specific application of the method in getting insight into the development of cancer metastasis.
December 2023
Discrete Math
Wed, 20.12.23 at 16:30
EN 058
Zoe Geiselmann TU Berlin Link Icon
Two ways of constructing graph associahedra
Abstract. A tube of a connected graph G is a subset of its vertices, inducing a connected subgraph, whereas a tubing of G is a non-intersecting, non-adjacent set of tubes. The poset of tubings, ordered by reverse inclusion can be realized by the face lattice of a polytope, called the graph associahedron. We will take a look at two ways to construct graph associahedra. The first consists of consecutively truncating particular faces of a simplex and yields a whole class of polytopes. For the complete graph, one instance of this class is the permutahedron. The second way uses the nice hyperplane description of the permutahedron and removes some of the hyperplanes - however this will not always yield the desired polytope. We will see under which condition we can employ this method.
Discrete Math
Wed, 13.12.23 at 15:00
EN 058
Rosa Preiß U Potsdam Link Icon
An algebraic geometry of paths via the iterated-integrals signature
Abstract. Contrary to previous approaches bringing together algebraic geometry and signatures of paths, we introduce a Zariski topology on the space of paths itself, and study path varieties consisting of all paths whose signature satisfies certain polynomial equations. Particular emphasis lies on the role of the non-associative halfshuffle, which makes it possible to describe varieties of paths that satisfy certain relations all along their trajectory. Specifically, we may understand the set of paths on a given classical algebraic variety in R^d starting from a fixed point as a path variety. While halfshuffle varieties are stable under stopping paths at an earlier time, we furthermore study varieties that are stable under concatenation of paths. We point out how the notion of dimension for path varieties crucially depends on the fact that they may be reducible into countably infinitely many subvarieties. Finally, we see that studying halfshuffle varieties naturally leads to a generalization of classical algebraic curves, surfaces and affine varieties in finite dimensional space, where these generalized algebraic sets are now described through iterated-integral equations. Keywords. path variety, shuffle ideal, halfshuffle, deconcatenation coproduct, tensor algebra, Zariski topology, concatenation of paths, Chen's identity, tree-like equivalence, regular map, generalized variety
Discrete Math
Wed, 06.12.23 at 16:30
EN 058
Viktor Levandovskyy U Kassel Link Icon
Gröbner bases over free associative algebras: Algorithmics, Implementation, and Applications
Abstract. In this talk we will make a journey to the constructive methods for ideals of free associative algebra. These methods, especially those based on Gröbner bases are important constituents in a vast number of applications. However, there are numerous intrinsic complications to be treated: for example, a typical computation of a Gröbner basis will not terminate after finitely many steps. Balancing on the edge of decidability we will show, what is possible to compute and how these computations are implemented. Our implementation, providing a lof of functionality at a decent speed, is called Singular:Letterplace and it is OSCAR-aware.Slides
November 2023
Discrete Math
Wed, 22.11.23 at 16:30
EN 058
Daniel Dadush CWI Amsterdam Link Icon
Interior point methods are not worse than Simplex
Abstract. https://arxiv.org/abs/2206.08810
Discrete Math
Wed, 15.11.23 at 16:30
EN 058
Giulia Codenotti FU Berlin Link Icon
Lattice-reduced and complete convex bodies
Abstract. Reduced and complete convex bodies are classical objects in convex geometry. We introduce and study discrete analogues of these bodies in the presence of a lattice, which we call lattice-reduced and lattice-complete bodies. As we will see, these convex bodies are necessarily polytopes and have strong restrictions on the number of vertices and facets. We will in particular discuss the case of bodies that are both lattice-reduced and lattice-complete, exploring their characteristics and giving conditions on their existence.To conclude, we will see one of the main motivations for these definitions, namely the connection with the celebrated flatness theorem. This theorem establishes, in fixed dimension, a maximum lattice width of convex bodies that do not contain lattice points in the interior. In particular, we will explore how the study of lattice-reduced bodies can help determine the maximum width constants of the theorem.
Discrete Math
Wed, 01.11.23 at 16:30
BEL 301
Mara Belotti TU Berlin Link Icon
Tangency and point constraints in computational geometry
Abstract. Wissenschaftliche Aussprache
October 2023
Discrete Math
Wed, 25.10.23 at 16:30
EN 058
Justin Lanier U Sydney Link Icon
Mapping class groups and dense conjugacy classes
Abstract. I’ll start by introducing mapping class groups and infinite-type surfaces—those with infinite genus or infinitely many punctures. One difference from the finite-type setting is that these mapping class groups come with natural non-discrete topologies. I’ll discuss joint work with Nick Vlamis where we fully characterize which surfaces have mapping class groups with dense conjugacy classes, so that there exists an element that well approximates every mapping class, up to conjugacy.
Discrete Math
Wed, 11.10.23 at 16:30
EN 058
Matthew Maat U Twente Link Icon
The connection between linear programs and games
Abstract. The simplex algorithm is a well-known combinatorial algorithm that is commonly used to solve linear programs (LPs). It requires a pivot rule to decide which steps it takes. Despite the algorithm being fast in practice, for many different pivot rules it has been shown that in the worst case the number of steps may be exponential, and it is not known whether there exists a pivot rule with better worst-case bounds. In order to gain more understanding of the worst case behaviour, we consider a class of LPs that come from games, specifically mean payoff games and parity games. We show that strategy improvement (a well-known combinatorial algorithm for solving these games) is equivalent to the simplex method in the LP formulation. We use this result to derive lower bounds for pivot rules that only use certain combinatorial information. Finally, we shortly discuss combinatorial types for these types of games.
Discrete Math
Wed, 04.10.23 at 16:30
EN 058
Sayan Mukherjee MPI-MiS Leipzig Link Icon
Modeling shapes and surfaces - Geometry meets machine learning
Abstract. We will consider modeling shapes and fields via topological and lifted-topological transforms. Specifically, we show how the Euler Characteristic Transform and the Lifted Euler Characteristic Transform can be used in practice for statistical analysis of shape and field data. We also state a moduli space of shapes for which we can provide a complexity metric for the shapes. We also provide a sheaf theoretic construction of shape space that does not require diffeomorphisms or correspondence. A direct result of this sheaf theoretic construction is that in three dimensions for meshes, 0-dimensional homology is enough to characterize the shape. We will also discuss Gaussian processes on fiber bundles and applications to evolutionary questions about shapes. Applications in biomedical imaging and evolutionary anthropology will be stated throughout the talk.
September 2023
Discrete Math
Wed, 13.09.23 at 16:30
MAR 4.064, Marchs...
Ievgen Makedonskyi BIMSA Link Icon
Semi-infinite Pluecker relations and the snake formula
Abstract. We study a certain infinitization of the Pluecker algebra. This is the so-called arc ring of the classical algebra generated by minors of a matrix and it also has a natural representation-theoretical meaning. We prove that this ring is defined by relations of degree 2 and give a combinatorial formula of the graded components of this algebra. We call it the ''snake formula''. I will explain the method used to study this ring. It is an arc analogue of the standard monomial theory and can be applied to a wide family of arc rings.
Discrete Math
Wed, 06.09.23 at 16:30
EN 058
Ji Hoon Chun TU Berlin Link Icon
Finite Sphere Packings and the Sausage Conjecture
Abstract. The Sausage Conjecture of L. Fejes Tóth (1975) states that for all dimensions $d \geq 5$, the densest packing of any finite number of spheres in $\mathbb{R}^{d}$ occurs if and only if the sphere centers are all placed as closely as possible on one line, i.e., a 'sausage.' We discuss the progress made in the literature, including the result of Betke and Henk (1998) that the Sausage Conjecture is true for all $d \geq 42$. Our work builds upon the methods of Betke and Henk to improve the lower bound to $d \geq 36$ with the aid of interval arithmetic for certain complicated portions. Joint work with Martin Henk.
August 2023
Discrete Math
Wed, 23.08.23 at 16:30
MAR 4.064, Marchs...
Fabian Lenzen TU München Link Icon
Computation of two-parameter persistent (co)homology
Abstract. Persistent homology is a central tool in topological data analysis (TDA) that seeks to understand the topological structure of data. Given a filtered topological space, persistent homology tracks the changes in the homology of that space along the filtration, and assigns to the filtration an invariant called the barcode. It can be efficiently computed, and many different implementations are available. However, persistent homology has some shortcomings. Most notably, it is susceptible to outliers. A possible remedy is seen in multi-parameter persistent homology, which tracks the changes in homology of a space filtered in several parameters. However, multi-parameter persistent homology is much harder to compute. In this talk, I explain a common approach for the computation of a minimal free resolution of persistent homology in the special case of two-parameter persistence. Motivated by observations from (ordinary) one-parameter persistence, I will show how computation of cohomology (instead of homology) can be used to obtain other efficient algorithms for the computation of minimal free resolutions of one-parameter persistence.
Discrete Math
Sun, 20.08.23 at 16:30
MAR 4.064, Marchs...
Antony Della Vecchia TU Berlin Link Icon
A FAIR File Format for Mathematical Software
Abstract. Due to the complexity of mathematical objects, storing data so it is FAIR has its challenges. We describe a generic \texttt{JSON} based file format which is suitable for computations in computer algebra, highlighting some design decisions and demonstrating some of the benefits with an emphasis on interoperability and reproducibility. This is implemented in the computer algebra system \texttt{OSCAR}, but we also show how it can be used in a different context. This is joint work with Michael Joswig and Benjamin Lorenz.
Discrete Math
Wed, 02.08.23 at 16:30
MAR 4.064, Marchs...
Michael Joswig TU Berlin Link Icon
Smooth Fano Polytopes and Their Triangulations
Abstract. The classification of the d-dimensional simplicial, terminal, and reflexive polytopes with at least 3d-2 vertices is presented. It turns out that all of them are smooth Fano polytopes. This builds on and improves previous results of Casagrande (2006) and Obro (2008). The second half of the presentation is concerned with triangulations of such polytopes. Joint work with Benjamin Assarf, Andreas Paffenholz and Julian Pfeifle.
July 2023
Discrete Math
Wed, 26.07.23 at 16:30
MPI Leipzig
Claudia Yun MPI Leipzig Link Icon
Amalgamating groups via linear programming
Abstract. A compact group $A$ is called an amalgamation basis if, for every way of embedding $A$ into compact groups $B$ and $C$, there exist a compact group $D$ and embeddings $B\to D$ and $C\to D$ that agree on the image of $A$. Bergman in a 1987 paper studied the question of which groups can be amalgamation bases. A fundamental question that is still open is whether the circle group $S^1$ is an amalgamation basis in the category of compact Lie groups. Further reduction shows that it suffices to take $B$ and $C$ to be the special unitary groups. In our work, we focus on the case when $B$ and $C$ are the special unitary group in dimension three. We reformulate the amalgamation question into an algebraic question of constructing specific Schur-positive symmetric polynomials and use integer linear programming to compute the amalgamation. We conjecture that $S^1$ is an amalgamation basis based on our data. This is joint work with Michael Joswig, Mario Kummer, and Andreas Thom.
Discrete Math
Wed, 19.07.23 at 16:30
MAR 6.051 6th flo...
Jonathan Spreer University of Sydney Link Icon
An algorithm to compute the crosscapnumber of a knot
Abstract. The crosscap number of a knot is the non-orientable counterpart of its genus. It is defined as the minimum of one minus the Euler characteristic of S, taken over all non-orientable surfaces S bounding the knot. Computing thecrosscap number of a knot is tricky, since normal surface theory - the usualtool to prove computability of problems in 3-manifold topology, does notdeliver the answer 'out-of-the-box'.In this talk, I will review the strengths and weaknesses of normal surfacetheory, focusing on why we need to work to obtain an algorithm to computethe crosscap number. I will then explain the theorem stating that an algorithm due to Burton and Ozlen can be used to give us the answer.This is joint work with Jaco, Rubinstein, and Tillmann.
Discrete Math
Wed, 05.07.23 at 16:30
MAR 6.051 6th flo...
Stephanie Mui NYU Link Icon
The $L^{p}$ dual Minkowski problem: an overview and new results for $p<0$
Abstract. The $L^{p}$ dual curvature measure was introduced by Lutwak, Yang, and Zhang in 2018. The associated Minkowski problem, known as the $L^{p}$ dual Minkowski problem, asks about existence of a convex body with prescribed $L^{p}$ dual curvature measure. This question unifies the previously disjoint $L^{p}$ Minkowski problem with the dual Minkowski problem, two open questions in convex geometry. Among its important cases are the classical Minkowski problem, the Aleksandrov problem, and the log Minkowski problem. The case of negative $p$ is still largely unsolved, with the centro-affine Minkowski problem included in this region. We have obtained existence results assuming origin-symmetry for $-1 < p < 0$, $q < 1+p$, $p\neq q$. In this talk, we will also discuss the extensive history of the problem, critical cases, and more existence results in the negative $p$ region assuming bounded absolute continuity of the given data.
June 2023
Discrete Math
Thu, 22.06.23 at 16:30
FH-303
Guillermo Pineda-Villavicencio Deakin University Link Icon
Some results and conjectures on convex polytopes: from edge-connectivity of their graphs to lower bound conjectures on their faces
Abstract. In the talk, we will first discuss a recent theorem on edge cuts of minimal cardinality in the graph of a simplicial d-polytope of dimension d≥3: such a graph has no nontrivial minimum edge cut with fewer than d(d+1)/2 edges, hence the graph is min{δ,d(d+1)/2}-edge-connected where δ denotes the minimum degree. When d=3, this implies that every minimum edge cut in a plane triangulation is trivial. When d≥4, we construct a simplicial d-polytope whose graph has a nontrivial minimum edge cut of cardinality d(d+1)/2, proving that the aforementioned result is best possible. This is a joint work with Julien Ugon (Deakin University) and Vincent Pilaud (CNRS & LIX, École Polytechnique) In the second part of the talk, we will propose two Lower bound conjectures: one for d-polytopes with at most 3d-1 vertices and another for d-polytopes whose facets are all combinatorially isomorphic to a pyramid over a (d-2)-cube. Finally, if time permits, I will explore the notion of neighbourly d-polytopes beyond the simplicial and cubical case.
Discrete Math
Wed, 21.06.23 at 16:30
Seminar room at A...
Theo Grundhöfer U Würzburg Link Icon
Groups and nearfields
Abstract. Nearfields are easy to define: just omit one of the two distributive laws in the definition of skew fields. We explain the connection of nearfields to sharply 2-transitive permutation groups. Every nearfield has an intrinsic vector space structure, hence one can study nearfields in terms of groups of linear transformations. All finite nearfields have been classified by Zassenhaus in 1936. We report on classification results for infinite nearfields, and we construct some `wild´ nearfields which are far away from skew fields.
Discrete Math
Wed, 07.06.23 at 16:30
MA 750
Jacob Matherne Universität Bonn, MPI Link Icon
Polynomials in combinatorics and representation theory
Abstract. Many polynomials in combinatorics (and in other areas of mathematics) have nice properties such as having all of their roots being real numbers, or having all of their coefficients being nonnegative. By surveying recent advances in the Hodge theory of matroids (namely, the nonnegativity of Kazhdan-Lusztig polynomials of matroids and Dowling and Wilson's top-heavy conjecture for the lattice of flats of a matroid), I will give several examples of well-behaved polynomials, and I will indicate some connections of these properties to geometry and representation theory. The talk should be understandable to everyone, and should appeal to those with interests in at least one of the following topics: hyperplane arrangements, matroids, log-concavity, real-rooted polynomials, lattice theory, Coxeter groups, and the representation theory of Lie algebras. It will contain results that are joint work with Tom Braden, Luis Ferroni, June Huh, Nicholas Proudfoot, Matthew Stevens, Lorenzo Vecchi, and Botong Wang.
May 2023
Discrete Math
Wed, 31.05.23 at 16:30
MA 750
Martin Winter Warwick Link Icon
Rigidity, Tensegrity and Reconstruction of Polytopes under Metric Constraints
Abstract. In how far is it possible to reconstruct a convex polytope (up to isometry, affine equivalence or combinatorial equivalence) from its edge-graph and some 'graph-compatible metric data', such as its edge-lengths? In this talk we explore this question and pose the following conjecture: a convex polytope P is uniquely determined by its edge-graph, its edge length and the distance of each vertex from some common interior point of P, across all dimensions and combinatorial types. We conjecture even stronger, that two polytopes P and Q are already isometric if they have the same edge-graph, edges in P are at most as long as in Q, and vertex-point distances in P are at least as long as in Q. In other word, a convex polytope cannot become 'bigger' while its edges become shorter. We verify the conjectures in three special cases: if P and Q are combinatorically equivalent, if P and Q are centrally symmetric, and if Q is a slight perturbation of P. These results were obtained using techniques from the intersection of convex geometry and spectral graph theory.
Discrete Math
Wed, 24.05.23 at 16:30
MA 750
Kris Shaw University of Oslo Link Icon
Real phase structures on matroid fans and matroid orientations
Abstract. In this talk, I will propose a first definition of real structures on polyhedral complexes. I’ll explain that in the case of matroid fans, specifying such a structure is cryptomorphic to providing an orientation of the underlying matroid. Real phase structures are used to patchwork the real part of a tropical variety in any codimension and this gives a closed chain in the real part of a toric variety. This provides a link between oriented matroids and real toric varieties and an obstruction to the orientability of matroids via the homology groups of toric varieties. This is based on joint work with Johannes Rau and Arthur Renaudineau.
Discrete Math
Wed, 17.05.23 at 16:30
MA 750
Aryaman Jal KTH Link Icon
Polyhedral geometry of bisectors and bisection fans
Abstract. Every symmetric convex body induces a norm on its affine hull. The object of our study is the bisector of two points with respect to this norm. A topological description of bisectors is known in the 2 and 3-dimensional cases and recent work of Criado, Joswig and Santos (2022) expanded this to a fuller characterisation of the geometric, combinatorial and topological properties of the bisector. A key object introduced was the bisection fan of a polytope which they were able to explicitly describe in the case of the tropical norm. We discuss the bisector as a polyhedral complex, introduce the notion of bisection cones and describe the bisection fan corresponding to other polyhedral norms. This is joint work with Katharina Jochemko.
Discrete Math
Wed, 10.05.23 at 16:30
MA 750
Andreas Löhne Universität Jena Link Icon
Stable algorithms for the 3-dimensional vertex enumeration problem
Abstract. Vertex enumeration is the fundamental computational problem to determine the vertices of a convex polytope given by affine inequalities. The converse problem, called convex hull problem, is equivalent to polarity.Large instances of vertex enumeration problems frequently appear as subproblems in various applications. In practice, they are often treated by algorithms implemented in floating point arithmetic. Typically, correctness of these algorithms is only known for exact (rational) arithmetic, which can be too slow for practical requirements. Imprecise computations caused by floating point arithmetic can result in wrong results which are not even an approximation of the correct results in some suitable sense. Therefore, one is interested in stable algorithms where such kind of bad behavior can be excluded. Surprisingly, stability seems to be established so far only for the 2-dimensional vertex enumeration problem.We present two algorithms for the 3-dimensional vertex enumeration problem which are stable in some sense which needs to be explained further. We also discuss possible extensions to dimension 4.
April 2023
Discrete Math
Wed, 19.04.23 at 16:30
MA 750
Leonid Monin EPFL Link Icon
Combinatorics of toric bundles
Abstract. Toric bundles are fibre bundles which have a toric variety as a fiber. One particularly studied class of toric bundles are horospherical varieties which are toric bundles over generalized flag varieties. Similar to toric varieties, toric bundles admit a combinatorial description via polyhedral geometry. In my talk, I will explain such a combinatorial description, and describe a couple of results which rely on it. In particular, I will present a generalization of the BKK theorem and the Fano criterion for toric bundles.
Discrete Math
Wed, 12.04.23 at 16:30
TBD
Frank Sottile Texas A&M University Link Icon
Galois groups in Enumerative Geometry and Applications
Abstract. In 1870 Jordan explained how Galois theory can be applied to problems from enumerative geometry, with the group encoding intrinsic structure of the problem. Earlier Hermite showed the equivalence of Galois groups with geometric monodromy groups, and in 1979 Harris initiated the modern study of Galois groups of enumerative problems. He posited that a Galois group should be `as large as possible' in that it will be the largest group preserving internal symmetry in the geometric problem. I will describe this background and discuss some work in a long-term project to compute, study, and use Galois groups of geometric problems, including those that arise in applications of algebraic geometry. A main focus is to understand Galois groups in the Schubert calculus, a well-understood class of geometric problems that has long served as a laboratory for testing new ideas in enumerative geometry.
Discrete Math
Wed, 05.04.23 at 16:30
TBD
Jeffrey Giansiracusa Durham University Link Icon
An E-infinity structure on the matroid Grassmannian
Abstract. The matroid Grassmannian is the space of oriented matroids. 30 years ago MacPherson showed us that understanding the homotopy type of this space can have significant implications in manifold topology. In some easy cases, the matroid Grassmannian is homotopy equivalent to the ordinary real Grassmannian, but in most cases we have no idea whether or not they are equivalent. This is known as MacPherson's conjecture. I'll show that one of the important homotopical structures of the ordinary Grassmannians has an analogue on the matroid Grassmannian, namely the monoidal product tof direct sum that is commutative up to all higher homotopies.
February 2023
Discrete Math
Wed, 22.02.23 at 16:30
online
Vadim Semenov NYU Link Icon
The Gauss Image Problem
Abstract. The Gauss Image problem is a generalization to the question originally posed by Aleksandrov who studied the existence of the convex body with the prescribed Aleksandrov's integral curvature. A simple discrete case of the Gauss Image Problem can be formulated as follows: given a finite set of directions in Euclidian space and the same number of unit vectors, does there exist a convex polytope in this space containing the origin in its interior with vertices at given directions such that each normal cone at the vertex contains exactly one of the given vectors. In this talk, we are going to discuss the discrete Gauss Image Problem, and its relation to other Minkowski-type problems. Two different proofs of the problem are going to be addressed: A smooth proof based on transportation polytopes and a discrete proof based on Helly’s theorem. Time permitting, we will also discuss the uniqueness statement for the problem.
Discrete Math
Wed, 15.02.23 at 16:30
online
Dustin Ross San Francisco State University Link Icon
Putting the “volume” back in “volume polynomials”
Abstract. Recent developments in tropical geometry and matroid theory have led to the study of “volume polynomials” associated to tropical varieties, the coefficients of which record all possible degrees of top powers of tropical divisors. In this talk, I’ll discuss a volume-theoretic interpretation of volume polynomials of tropical fans; namely, they measure volumes of polyhedral complexes obtained by truncating the tropical fan with normal hyperplanes. I’ll also discuss how this volume-theoretic interpretation inspires a general framework for studying an analogue of the Alexandrov-Fenchel inequalities for degrees of divisors on tropical fans. Parts of this work are joint with Anastasia Nathanson, Lauren Nowak, and Patrick O’Melveny.
Discrete Math
Wed, 08.02.23 at 16:30
MA 850
Iskander Aliev Cardiff University Link Icon
Sparse integer points in rational polyhedra: bounds for the integer Carathéodory rank
Abstract. We will give an overview of the recent results on sparse integer points (that is the integer points with relatively large number of zero coordinates) in the rational polyhedra of the form {x: Ax=b, x>=0}, where A is an integer matrix and b is an integer vector. In particular, we will discuss the bounds on the Integer Caratheodory rank in various settings and proximity/sparsity transference results.
Discrete Math
Wed, 01.02.23 at 16:30
online
Igor Makhlin Skoltech Link Icon
Poset polytopes and toric degenerations
Abstract. In the 1980s Stanley introduced the order polytope and chain polytope associated with a poset while Hibi considered the closely related notions of the Hibi ideal and Hibi ring (as they are now known) associated with a distributive lattice. During the subsequent decades it was realized that these concepts can be applied to the construction and study of toric degenerations of Grassmannians and flag varieties. Moreover, virtually all sufficiently explicit and sufficiently general constructions of such degenerations known today can be interpreted in terms of poset polytopes and Hibi ideals. I will give an overview of these notions and explain how they lead to toric degenerations, reviewing some foundational and some very recent results in this direction.
January 2023
Discrete Math
Wed, 25.01.23 at 16:30
MA 850
Adam Afandi University of Münster Link Icon
An Ehrhart Theory For Tautological Intersection Numbers
Abstract. The tautological intersection theory of the moduli space of stable pointed curves is an active field of research in modern algebraic geometry. In this talk, I'll explain how Ehrhart theory can give a novel perspective on tautological intersection numbers. In particular, one can arrange tautological intersection numbers into families of evaluations of Ehrhart polynomials of partial polytopal complexes. The proof of this result relies on a theorem of Breuer, which classifies the Ehrhart polynomials of partial polytopal complexes. Time permitting, I will also discuss my current attempts to generalize this Ehrhart phenomenon.
Discrete Math
Wed, 18.01.23 at 16:30
MA 850
Emre Sertöz Leibniz University of Hannover Link Icon
Limit periods, arithmetic, and combinatorics
Abstract. With Spencer Bloch and Robin de Jong, we recently proved that in a nodal degeneration of smooth curves, the periods of the resulting limit mixed Hodge structure (LMHS) contain arithmetic information. More precisely, if the nodal fiber is identified with a smooth curve C glued at two points p and q then the LMHS relates to the Neron--Tate height of p-q in the Jacobian of C. In making this relation precise, we observed that a "tropical correction term" is required that is based on the degenerate fiber. In this talk, I will explain this circle of ideas with the goal of arriving at the tropical correction term.
Discrete Math
Wed, 11.01.23 at 16:30
online
Catherine Babecki University of Washington Link Icon
Structure and Complexity of Graphical Designs for Weighted Graphs through Eigenpolytopes
Abstract. We extend the theory of graphical designs, which are quadrature rules for graphs, to positively weighted graphs. Through Gale duality for polytopes, we show that there is a bijection between graphical designs and the faces of eigenpolytopes associated to the graph. This bijection proves the existence of graphical designs with positive quadrature weights, and upper bounds the size of a graphical design. We further show that any combinatorial polytope appears as the eigenpolytope of a positively weighted graph. Through this universality, we establish two complexity results for graphical designs: it is strongly NP-complete to determine if there is a graphical design smaller than the mentioned upper bound, and it is #P-complete to count the number of minimal graphical designs. Joint work with David Shiroma. https://arxiv.org/abs/2209.06349.
November 2022
Discrete Math
Wed, 30.11.22 at 16:30
MA 850
Zafeirakis Zafeirakopoulos Gebze Technical University Link Icon
Polyhedral Omega (+ applications)
Abstract. Polyhedral Omega is an algorithm for solving linear Diophantine systems (LDS), i.e., for computing a multivariate rational function representation of the set of all non-negative integer solutions to a system of linear equations and inequalities. Polyhedral Omega combines methods from partition analysis with methods from polyhedral geometry. In particular, we combine MacMahon’s iterative approach based on the Omega operator and explicit formulas for its evaluation with geometric tools such as Brion decomposition and Barvinok’s short rational function representations. This synthesis of ideas makes Polyhedral Omega by far the simplest algorithm for solving linear Diophantine systems available to date. After presenting the algorithm, we will see some applications and generalizations.
Discrete Math
Wed, 23.11.22 at 16:30
MA 850
Katherina von Dichter TU München / Cottbus Link Icon
Mean inequalities for symmetrizations of convex sets
Abstract. The arithmetic-harmonic mean inequality can be generalized for convex sets, considering the intersection, the harmonic and the arithmetic mean, as well as the convex hull of two convex sets. We study those relations of symmetrization of convex sets, i.e., dealing with the means of some convex set C and -C. We determine the dilatation factors, depending on the asymmetry of C, to reverse the containments between any of those symmetrizations, and tighten the relations proven by Firey and show a stability result concerning those factors near the simplex.
Discrete Math
Wed, 16.11.22 at 16:30
MA 850
Omid Amini \'Ecole Polytechnique Link Icon
Polyhedral geometry in higher rank and non-linear settings
Abstract. New types of polyhedral geometry and combinatorial structures emerge in the study of asymptotic geometry of complex manifolds. This includes a multi-scale version of polyhedral geometry, with links to a theory of higher rank combinatorial structures, which combine parts living in different scales at infinity, and a theory of convexity in a piecewise linear setting. The talk presents some features of these recent developments, and discusses applications in complex geometry. Based on joint works with Hernan Iriarte, with Noema Nicolussi, and with Matthieu Piquerez.
Discrete Math
Wed, 02.11.22 at 16:30
MA 850
Raman Sanyal Goethe-Universität Frankfurt Link Icon
Monotone paths on matroids, pivot rules, and flag polymatroids
Abstract. The well-known greedy algorithm on matroids was adapted by Edmonds to polymatroid polytopes or, essentially equivalent, generalized permutahedra. For a given objective function, the greedy algorithm traces a monotone path in the graph of the polymatroid polytope. The starting point of this work is the observation that this path is precisely the path taken by the shadow-vertex simplex algorithm. It turns out that all monotone paths are greedy paths and all are coherent in the sense of Billera-Sturmfels. Thus, monotone paths are parametrized by the associated monotone path polytope. We show that these monotone path polytope are again a generalized permutahedron and in the case of matroids are the underlying flag matroids. In this talk I will explain the geometry of these “flag polymatroids” and the connection to certain nestohedra associated to lattices of flats via so-called pivot rule polytopes. If time permits, I will also discuss relations to sorting networks and the enumeration of Young tableaux. This is joint work with Alex Black.
October 2022
Discrete Math
Wed, 26.10.22 at 11:00
MA 313/314
Stephane Gaubert INRIA / CMAP École Polytechnique Link Icon
Ambitropical convexity, injective hulls of metric spaces, and mean-payoff games
Abstract. Hyperconvexity was introduced by Aronszajn and Panichpadki in the 50', to study nonexpansive mappings between metric spaces. We study a new kind of convexity, defined in terms of lattice properties. We call it ``ambitropical'' as it includes both tropical convexity and its dual, and we relate it with hyperconvexity and mean-payoff games.Ambitropical convex sets coincide with hyperconvex sets with an additional requirement: stability by an additive group action of the real numbers. They also coincide with the fixed-point sets of Shapley operators, i.e., of dynamic programming operators of (undiscounted) zero-sum games. In this way, ambitropical convex sets provide geometric representations of (calibrated) optimal stationary strategies of mean-payoff games. Moreover, there is a notion of ``ambitropical hull'', unique up to isomorphism, which we construct as the range of a tropical analogue of the Petrov-Galerkin projector, providing an alternative to the ``tight-span'' construction of Isbell and Dress for the injective hull, in the special case of an ambitropical convex set. We finally consider ambitropical polyhedra, defined as ambitropical convex sets that have a cell decomposition in terms of alcoved polyhedra. We relate them with deterministic games and order preserving retracts of the Boolean hypercube.This talk is based on a joint work with Marianne Akian and Sara Vannucci. A preliminary account of the results appeared in arXiv:2108.07748.
Discrete Math
Wed, 19.10.22 at 16:30
MA 850
Leonid Monin MPI MiS Leipzig Link Icon
Polyhedral models for K-theory
Abstract. One can associate a commutative, graded algebra which satisfies Poincare duality to a homogeneous polynomial f on a vector space V. One particularly interesting example of this construction is when f is the volume polynomial on a suitable space of (virtual) polytopes. In this case the algebra A_f recovers cohomology rings of toric or flag varieties. In my talk I will explain these results and present their recent generalizations. In particular, I will explain how to associate an algebra with Gorenstein duality to any function g on a lattice L. In the case when g is the Ehrhardt function on a lattice of integer (virtual) polytopes, this construction recovers K-theory of toric and full flag varieties.
Discrete Math
Wed, 12.10.22 at 17:00
online
Yulia Alexandr UC Berkeley Link Icon
Logarithmic Voronoi cells
Abstract. Logarithmic Voronoi cells are convex sets, which arise as fibers of the maximum likelihood estimation map. For discrete models, they live inside their log-normal polytopes, and for certain families of statistical models, the two sets coincide. In particular, logarithmic Voronoi cells for such families are polytopes. I will introduce these notions and investigate when this property holds. I will also talk about how this theory generalizes to Gaussian models, with lots of examples. This talk is based on joint works with Alex Heaton and Serkan Hosten.
Discrete Math
Wed, 05.10.22 at 16:30
MA 141
Matthias Schymura BTU Cottbus-Senftenberg Link Icon
On the maximal number of columns of a Delta-modular integer matrix
Abstract. 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.
September 2022
Discrete Math
Wed, 28.09.22 at 16:30
MA 144
Jesús A. De Loera UC Davis Link Icon
Open problems arising from trying to understand the Simplex Method
Abstract. 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&uumltjeharms, and R. Sanyal).
August 2022
Discrete Math
Wed, 24.08.22 at 16:30
H 1029
Benjamin Schröter KTH Link Icon
Valuative Invariants for Matroids
Abstract. 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.
July 2022
Discrete Math
Wed, 20.07.22 at 16:30
MA 141
Anton Dochtermann Texas State University Link Icon
Root polytopes, tropical types, and toric edge ideals
Abstract. 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.
Discrete Math
Wed, 13.07.22 at 16:30
MA 141
Büsra Sert Link Icon
The Half-Plane Property of Matroids, Related Concepts, and an Algorithm
Abstract. 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.
June 2022
Discrete Math
Wed, 22.06.22 at 16:30
MA 141
Matthias Beck SFSU Link Icon
\(f^*\)- and \(h^*\)-vectors
Abstract. 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&oacutenimo Valencia) about \(f^*\)- and \(h^*\)-vectors, including analogues and dissimiliarieties with \(f\)- and \(h\)-vectors of polytopes and polyhedral complexes.
Discrete Math
Wed, 15.06.22 at 16:30
online
Julian Pfeifle UPC Link Icon
Coming soon to polymake: (sometimes) disproving convex realizability of spheres
Abstract. 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.
Discrete Math
Wed, 01.06.22 at 16:30
MA 141
Enis Kaya MPI MiS Leipzig Link Icon
Determining reduction types of Picard curves via tropical invariants
Abstract. 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.
May 2022
Discrete Math
Wed, 25.05.22 at 16:30
MA 141
Zoe Wellner Carnegie Mellon University Link Icon
Colorful Borsuk-Ulam Results, Their Generalizations and Applications
Abstract. 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.
Discrete Math
Wed, 18.05.22 at 16:30
MA 141
Niels Lindner ZIB Link Icon
On the tropical and zonotopal geometry of periodic timetabling
Abstract. 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.
Discrete Math
Wed, 04.05.22 at 16:30
MA 141
Alex Elzenaar MPI MiS Leipzig Link Icon
Aspects of computation in hyperbolic geometry
Abstract. 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).
April 2022
Discrete Math
Wed, 27.04.22 at 16:30
online
Thomas Blomme University of Geneva Link Icon
Enumeration of tropical curves in abelian surfaces
Abstract. 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.
Discrete Math
Wed, 20.04.22 at 16:30
online
Michael Joswig TU Berlin Link Icon
Lattice polygons and real roots
Abstract. 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.
March 2022
Discrete Math
Wed, 16.03.22 at 16:30
online
Marie Brandenburg MPI MiS Leipzig Link Icon
Competitive Equilibrium and Lattice Polytopes
Abstract. 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.
Discrete Math
Wed, 09.03.22 at 16:30
online
Lorenzo Venturello KTH Link Icon
On the gamma-vector of symmetric edge polytopes
Abstract. 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.
February 2022
Discrete Math
Wed, 16.02.22 at 16:30
online
Lei Xue University of Washington Link Icon
A Proof of Grünbaum’s Lower Bound Conjecture for polytopes, lattices, and strongly regular pseudomanifolds
Abstract. In 1967, Gr&uumlnbaum 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.
Discrete Math
Wed, 09.02.22 at 16:30
online
Mara Belotti TU Berlin Link Icon
An enumerative problem for cubic (hyper)surfaces: point and line conditions
Abstract. 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.
Discrete Math
Wed, 02.02.22 at 16:30
online
Sara Griffith Brown University Link Icon
The Torelli theorem, or how to determine a graph from its algebraic data
Abstract. 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.
January 2022
Discrete Math
Wed, 26.01.22 at 16:30
online
Paco Santos Universidad de Cantabria Link Icon
Multitriangulations and tropical Pfaffians
Abstract. 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).
Discrete Math
Wed, 19.01.22 at 16:30
online
Jonathan Boretsky Harvard Link Icon
The Totally Non-Negative Complete Flag Variety and its Tropicalization
Abstract. 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.
December 2021
Discrete Math
Wed, 15.12.21 at 16:30
online
Katharina Jochemko KTH Link Icon
The Eulerian transformation
Abstract. 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.
Discrete Math
Wed, 08.12.21 at 16:30
online
Matthias Köppe UC Davis Link Icon
sagemath-polyhedra: A modularized Sage distribution
Abstract. 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.
Discrete Math
Wed, 01.12.21 at 16:30
online
Benjamin Schröter KTH Link Icon
Ehrhart Polynomials of Rank-Two Matroids
Abstract. 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.
November 2021
Discrete Math
Wed, 24.11.21 at 16:00
online
Alexander Stoimenow GIST College Link Icon
Exchange moves and non-conjugate braid representatives of links
Abstract. 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.
Discrete Math
Wed, 17.11.21 at 16:30
online
Sinai Robins Universidade de São Paulo Link Icon
The null set of a polytope, and the Pompeiu property for polytopes
Abstract. 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.
Discrete Math
Wed, 10.11.21 at 16:30
online
Austin Alderete UT Austin Link Icon
A polymake extension for computing the homology groups of minor-closed classes of matroids
Abstract. 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.
October 2021
Discrete Math
Wed, 27.10.21 at 16:30
H 0107
Davide Lofano TU Berlin Link Icon
Hadamard Matrix Torsion
Abstract. 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.
Discrete Math
Wed, 20.10.21 at 16:30
H 0107
Sylvain Spitz TU Berlin Link Icon
Generalized Permutahedra and Optimal Auctions
Abstract. 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.
Discrete Math
Wed, 13.10.21 at 16:30
online
Petter Brändén KTH Link Icon
Lorentzian polynomials on cones and the Heron-Rota-Welsh conjecture
Abstract. 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.
August 2021
Discrete Math
Wed, 25.08.21 at 16:30
online
Georg Loho University of Twente Link Icon
Generalized permutahedra and complete classes of valuated matroids
Abstract. 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.
Discrete Math
Wed, 04.08.21 at 16:30
online
Chiara Meroni MPI MiS Link Icon
Fiber convex bodies
Abstract. 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.
July 2021
Discrete Math
Wed, 28.07.21 at 16:30
online
Tobias Boege Universität Magdeburg Link Icon
The Gaussian conditional independence inference problem
Abstract. 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.
Discrete Math
Wed, 14.07.21 at 16:30
online
Claudia Yun Brown University Link Icon
The S_n-equivariant rational homology of the tropical moduli spaces \Delta_{2,n}
Abstract. 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.
Discrete Math
Wed, 07.07.21 at 16:30
online
Ilia Itenberg Sorbonne Université Link Icon
Planes in cubic fourfolds
Abstract. 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.
June 2021
Discrete Math
Wed, 30.06.21 at 16:30
online
Holger Eble TU Berlin Link Icon
Enumerating Chambers of Hyperplane Arrangements with Symmetry
Abstract. 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.
Discrete Math
Wed, 23.06.21 at 16:30
online
Manuel Radons TU Berlin Link Icon
Edge-unfolding nested prismatoids
Abstract. 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.
Discrete Math
Wed, 16.06.21 at 16:30
online
Christoph Hertrich TU Berlin Link Icon
Towards Lower Bounds on the Depth of ReLU Neural Networks
Abstract. 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.
Discrete Math
Wed, 09.06.21 at 16:30
online
Matteo Gallet RICAM Link Icon
Mobile Icosapods
Abstract. 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.
Discrete Math
Wed, 02.06.21 at 16:30
online
Marieke van der Wegen Utrecht University Link Icon
Computing stable gonality is hard
Abstract. 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.
May 2021
Discrete Math
Wed, 26.05.21 at 16:30
online
Guido Montúfar MPI Leipzig and UCLA Link Icon
Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums
Abstract. 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.
Discrete Math
Wed, 19.05.21 at 16:30
online
Simon Telen MPI MiS Leipzig Link Icon
Likelihood equations and scattering amplitudes
Abstract. 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.
Discrete Math
Wed, 12.05.21 at 16:30
online
Sophie Rehberg FU Berlin Link Icon
Combinatorial reciprocity theorems for generalized permutahedra, hypergraphs, and pruned inside-out polytopes
Abstract. 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.
Discrete Math
Wed, 05.05.21 at 16:30
online
Sandra Di Rocco KTH Link Icon
Iterated discriminants
Abstract. 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.
April 2021
Discrete Math
Wed, 28.04.21 at 16:30
online
Daniel Corey University of Wisconsin-Madison Link Icon
Initial degenerations of Grassmannians and spinor varieties
Abstract. 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.
Discrete Math
Wed, 21.04.21 at 16:30
online
Mario Kummer TU Dresden Link Icon
Iso Edge Domains
Abstract. 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ć.
Discrete Math
Wed, 14.04.21 at 16:30
online
Antony Della Vecchia Link Icon
One Relator Groups and Regular Sectional Curvature
Abstract. 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.
March 2021
Discrete Math
Wed, 10.03.21 at 16:30
online
Nicholas Williams University of Leicester Link Icon
New interpretations of the higher Stasheff–Tamari orders
Abstract. 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.
Discrete Math
Wed, 03.03.21 at 16:30
online
Kaie Kubjas Aalto University Link Icon
Identifying 3D Genome Organization in Diploid Organisms via Euclidean Distance Geometry
Abstract. 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.
February 2021
Discrete Math
Wed, 24.02.21 at 16:30
online
Malte Renken TU Berlin Link Icon
What does the Cyclic Polytope have to do with Visibility Graphs?
Abstract. 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)
Discrete Math
Wed, 10.02.21 at 17:00
online
Jorge Olarte TU Berlin Link Icon
The tropical symplectic Grassmannian
Abstract. 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.
Discrete Math
Wed, 10.02.21 at 16:30
online
Oguzhan Yürük TU Berlin Link Icon
Detecting the Regions of Multistaionarity in CRNT via Symbolic Nonnegativity Certificates
Abstract. 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.
Discrete Math
Wed, 03.02.21 at 16:30
online
Siddarth Kannan Brown University Link Icon
Symmetries of tropical moduli spaces of curves
Abstract. 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.
January 2021
Discrete Math
Wed, 27.01.21 at 16:30
Online
Abhishek Rathod TU Munich Link Icon
Parameterized inapproximability of Morse matching
Abstract. 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.
Discrete Math
Wed, 20.01.21 at 16:30
Online
Christian Steinert RWTH Aachen University Link Icon
A Diagrammatic Approach to String Polytopes
Abstract. 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.
Discrete Math
Wed, 13.01.21 at 16:30
Online
Dhruv Ranganathan University of Cambridge Link Icon
Donaldson-Thomas theory and the secondary polytope
Abstract. 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).
Discrete Math
Tue, 12.01.21 at 16:30
online
Dante Luber TU Berlin Link Icon
Generalized permutahedra and positive flag Dressians
Abstract. 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
December 2020
Discrete Math
Wed, 09.12.20 at 16:30
Online
Michael Joswig TU Berlin Link Icon
Moduli of tropical curves - data and algorithms
Abstract. 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.
Discrete Math
Wed, 02.12.20 at 16:30
Online
Melody Chan Brown University Link Icon
Tropical abelian varieties
Abstract. 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.
November 2020
Discrete Math
Wed, 25.11.20 at 16:30
Online
Kemal Rose TU Berlin Link Icon
Certifying roots of polynomial systems using interval arithmetic
Abstract. 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.
Discrete Math
Wed, 18.11.20 at 16:30
Online
Benjamin Schröter KTH Stockholm Link Icon
Reconstructing Matroid Polytopes
Abstract. 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
Discrete Math
Wed, 11.11.20 at 16:30
Online
Nick Early Perimeter Institute for Theoretical Physics Link Icon
Combinatorial Geometries: From Polyhedral Subdivisions to Scattering Amplitudes
Abstract. 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.
Discrete Math
Wed, 04.11.20 at 16:30
Online
Dominic Bunnett TU Berlin Link Icon
Embedded stacky fans and tropical moduli spaces
Abstract. 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.
October 2020
Discrete Math
Wed, 28.10.20 at 16:30
Online
Rainer Sinn University of Leipzig Link Icon
Realization spaces of polytopes
Abstract. 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.
Discrete Math
Wed, 21.10.20 at 16:30
Online
Federico Castillo MPI Leipzig Link Icon
The space of Minkowski Summands
Abstract. 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.
Discrete Math
Wed, 14.10.20 at 16:30
Online
Leonid Monin University of Bristol Link Icon
Inversion of matrices, ML-degrees and the space of complete quadrics
Abstract. 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.
Discrete Math
Wed, 07.10.20 at 16:30
Online
Karin Schaller FU Link Icon
Mirror symmetry constructions for quasi-smooth Calabi-Yau hypersurfaces in weighted projective spaces
Abstract. 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.
September 2020
Discrete Math
Wed, 30.09.20 at 16:30
Online
Lukas Kühne Hebrew Universiy of Jerusalem Link Icon
The Resonance Arrangement
Abstract. 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.
August 2020
Discrete Math
Wed, 26.08.20 at 16:30
Online
Jaeho Shin Seoul National University Link Icon
Polytropes and Tropical Linear Spaces
Abstract. 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.
July 2020
Discrete Math
Wed, 29.07.20 at 16:30
Online
Yue Ren Swansea University Link Icon
Discrete Math
Wed, 08.07.20 at 16:30
Online
Stephane Gaubert INRIA and CMAP, Ecole polytechnique, CNRS Link Icon
Understanding and monitoring the evolution of the Covid-19 epidemic from medical emergency calls: the example of the Paris area
Abstract. 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.
June 2020
Discrete Math
Wed, 24.06.20 at 16:30
Online
Mara Belotti SISSA Link Icon
Topology of rigid isotopy classes of geometric graphs
Abstract. 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.
Discrete Math
Wed, 17.06.20 at 16:30
Online
Raman Sanyal Goethe University Frankfurt Link Icon
Inscribable fans, type cones, and reflection groupoids
Abstract. 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).
Discrete Math
Wed, 03.06.20 at 16:30
Online
Taylor Brysiewicz Texas A&M University Link Icon
The degree of Stiefel manifolds
Abstract. 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)
May 2020
Discrete Math
Wed, 27.05.20 at 16:30
Online
Thorsten Theobald Goethe University Frankfurt Link Icon
Conic stabilility of polynomials and spectrahedra
Abstract. 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.
Discrete Math
Wed, 20.05.20 at 16:30
Online
Luis Carlos Garcia Lirola Kent State University Link Icon
Volume product and metric spaces
Abstract. 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.
Discrete Math
Wed, 13.05.20 at 16:30
Online
Georg Loho London School of Economics Link Icon
Oriented Matroids from Triangulations of Products of Simplices
Abstract. 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.
Discrete Math
Wed, 06.05.20 at 16:30
Online
Martin Winter TU Chemnitz Link Icon
Edge-Transitive Polytopes
Abstract. 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.
April 2020
Discrete Math
Wed, 29.04.20 at 17:00
Online
Marek Kaluba Link Icon
Random polytopes in Machine Learning
Abstract. 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).
Discrete Math
Wed, 29.04.20 at 16:30
Online
Francisco Criado Link Icon
Borsuk’s problem
Abstract. 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 63In 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.
Discrete Math
Wed, 22.04.20 at 16:30
MA 621
Jonathan Spreer University of Sydney Link Icon
Linking topology and combinatorics: Width-type parameters of 3-manifolds
Abstract. 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
Discrete Math
Wed, 15.04.20 at 17:00
Online
Ayush Kumar Tewari Link Icon
Forbidden patterns in tropical planar curves and Panoptagons
Discrete Math
Wed, 15.04.20 at 16:30
Online
Dominic Bunnett Link Icon
Geometric discriminants and moduli
Abstract. 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.
Discrete Math
Wed, 08.04.20 at 16:30
Online
Robert Loewe Link Icon
Minkowski decompositions of generalized associahedra
Abstract. 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.
Discrete Math
Wed, 01.04.20 at 16:30
Online
Lars Kastner Link Icon
Hyperplane arrangements in polymake
Abstract. 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.
March 2020
Discrete Math
Wed, 25.03.20 at 17:00
Online
Paul Vater Link Icon
Patchworking real tropical hypersurfaces
Abstract. 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.
Discrete Math
Wed, 25.03.20 at 16:30
Online
Andrew Newman Link Icon
A two-step random polytope model
Abstract. 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.
Discrete Math
Wed, 11.03.20 at 16:30
MA 621
Oguzhan Yuruk Link Icon
Understanding the Parameter Regions of Multistationarity in Dual Phosporylation Cycle via SONC
Abstract. 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.
February 2020
Discrete Math
Wed, 26.02.20 at 16:30
MA 621
Ralph Morrison Williams College Link Icon
Tropically planar graphs: geometry and combinatorics
Abstract. 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.
Discrete Math
Wed, 12.02.20 at 16:30
MA 621
Antonio Macchia FU Berlin Link Icon
Binomial edge ideals of bipartite graphs
Abstract. 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
Discrete Math
Wed, 05.02.20 at 16:30
MA 621
Amy Wiebe FU Berlin Link Icon
Combining Realization Space Models of Polytopes
Abstract. 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.
January 2020
Discrete Math
Wed, 29.01.20 at 16:30
MA 621
Matias Villagra Pontifical Catholic University of Chile Link Icon
On a canonical symmetry breaking technique for polytopes
Abstract. 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.
Discrete Math
Wed, 22.01.20 at 16:30
MA 621
Andres R. Vindas Melendez University of Kentucky Link Icon
The Equivariant Ehrhart Theory of the Permutahedron
Abstract. 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).
Discrete Math
Wed, 15.01.20 at 16:30
MA 621
Simon Telen KU Leuven Link Icon
Numerical Root Finding via Cox Rings
Abstract. 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.