Roxana
Radulescu
Discrete Geometry and Topological Combinatorics Seminar  đ
Institute
Head
Georg Loho
and
GĂŒnter M. Ziegler
Description
The seminar revolves broadly around Discrete Geometry, Combinatorics and Topology with connections to Optimization, Computer Science and Algebra as well as applications of these areas.
Usual time
Thursdays at 14:15
Usual venue
villa
Number of talks
291
January 2025
December 2024
Hana
Kourimska
November 2024
Eleonore
Bach
EPFL
Smoothed analysis of the Simplex method: nearly tight noise dependence
Abstract.
Smoothed analysis is a method for analysing the performance of algorithms, used especially for those algorithms whose running time in practice is significantly better than what can be proven through worst-case analysis. Given an arbitrary linear program with $d$ variables and $n$ inequality constraints, we prove that there is a simplex method with smoothed complexity upper bounded by $O(\sigma^{-1/2} d^{11/4} \log(n/\sigma)^{7/4})$ pivot steps improving over the current best bound of $O(\sigma^{-3/2} d^{13/4} \log(n)^{7/4})$ pivot steps due to Huiberts, Lee and Zhang (STOC '23). For the same method we prove a lower bound on its smoothed complexity of $0.03 \sigma^{-1/2} d^{-1/4}\ln(n)^{-1/4}$ pivot steps for $n = (4/\sigma)^d$ inequality constraints. Here $\sigma > 0$ is the standard deviation of Gaussian distributed noise added to the original LP data. This nearly closes the gap between the upper and lower bounds in regards to their dependence on the noise parameter $\sigma$. In this talk we will discuss the algorithmic improvements that we used for the above new upper bound. This is joint work with Sophie Huiberts.
Enrico
Bortoletto
ZIB
and
Berenike
Masing
ZIB
On the Tropical and Zonotopal Geometry of Periodic Timetables
Abstract.
The Periodic Event Scheduling Problem (PESP) is a fundamental tool for optimizing periodic timetables in public transport. While periodic tension spaces have been well-studied, this talk focuses on the geometry of timetables and cycle offsets through tropical and zonotopal frameworks. We examine the feasible timetable space as a union of polytropes and propose a heuristic for PESP, based on polytrope neighborhood relations. Additionally, we recognize the space of fractional cycle offsets as a zonotope and analyze its tilings in relation to timetable polytropes. We conclude with new bounds on cycle bases, as well as some new and developing questions.
Alex
Black
October 2024
Sebastian
Meyer
TU Dresden
A topological CSP dichotomy
Abstract.
Many decision problems from mathematics and theoretical computer science, such as graph colorings and solving linear equations, can be modeled as constraint satisfaction problems (CSPs). It is known that finite CSPs are NP-complete or in P and how to distinguish them algebraically. We give a topological description of this dichotomy. This implies a dichotomy for simplicial complexes and a possibility to reprove the Hell-NeĆĄetĆil-Theorem.
Matthew
Dupraz
FU Berlin
Tropical linear series
Abstract.
Tropicalization is a process that allows us to obtain from algebro-geometric objects combinatorial ones, while preserving many interesting properties. For example, we may tropicalize an algebraic curve to obtain a metric graph, and study divisors on the latter. Surprisingly, certain properties, like the Riemann-Roch theorem stay true for systems of divisors on a metric graph, and so we may wonder just how much are these objects related. In this talk I would like to introduce the tropical analog of linear series, and mention some interesting properties that they exhibit.
Stefan
Felsner
TU Berlin
On the number of arrangements of pseudolines: upper and lower bounds
Abstract.
Arrangements of pseudolines are classic objects in discrete and computational geometry. They have been studied with increasing intensity since their introduction almost 100 years ago. The study of the number Bn of non-isomorphic simple arrangements of n pseudolines goes back to Goodman and Pollack, Knuth, and others. It is known that Bn is in the order of 2^Î(n^2) and finding asymptotic bounds on bn = log2(Bn)/n^2 remains a challenging task. I will present the ideas that lead to improvements of upper and lower bounds over the last 15 years. In particular I will present the recent progress obtained with Fernando CortĂ©s KĂŒhnast, Justin Dallant, and Manfred Scheucher (SoCG'24).
July 2024
Adélie
Garin
EPFL
Topological Data Analysis meets Geometric Group Theory: Stratifying the space of barcodes using Coxeter complexes
Abstract.
At the intersection of data science and algebraic topology, topological data analysis (TDA) is a recent field of study, which provides robust mathematical, statistical and algorithmic methods to analyze the topological and geometric structures underlying complex data. TDA has proved its utility in many applications, including biology, material science and climate science, and it is still rapidly evolving. Barcodes are frequently used invariants in TDA. They provide topological summaries of the persistent homology of a filtered space. Understanding the structure and geometry of the space of barcodes is hence crucial for applications.<br><br>In this talk, we use Coxeter complexes to define new coordinates on the space of barcodes.These coordinates define a stratification of the space of barcodes with n bars where the highest dimensional strata are indexed by the symmetric group. This creates a bridge between the fields of TDA, geometric group theory and permutation statistics, which could be exploited by researchers from each field.<br><br>No prerequisite on TDA or Coxeter complexes are required.
Germain
Poullot
Uni OsnabrĂŒck
Deformed Permutahedra: Let's visit the submodular cone together!
Abstract.
The permutahedron is a famous polytope whose combinatorics encapsulates the combinatorics of permutations (seen as a Coxeter group). This talk aims at illustrating what happens when we "deform" the permutahedron, that is to say we glide the facets of the permutahedron, keeping the same normal vectors. Each deformation can hence be thought as a sub-combinatorics of the combinatorics of permutations, endowed with a polytopal realization. We will first give two ways of thinking about deformations in general, and then look at the case of the permutahedron. The set of deformations of a polytope forms a cone: in the case of the permutahedron, this cone is named the "submodular cone", and has a lot of nice but complicated properties. The last part of the talk will be devoted to the illustration of some fun facts, obtained thanks to numerical experiments, on the submodular cone.
Eleonore
Bach
EPFL
June 2024
Karel
Devriendt
MPI-MiS
Spanning trees, effective resistances and curvature on graphs
Abstract.
Kirchhoff's celebrated matrix tree theorem expresses the number of spanning trees of a graph as the maximal minor of the Laplacian matrix of the graph. In modern language, this determinantal counting formula reflects the fact that spanning trees form a regular matroid. In this talk, I will discuss some consequences of this matroidal perspective for the study of a related quantity from electrical circuit theory: the effective resistance. I will give a characterization of effective resistances in terms of a certain polytope associated with the spanning tree matroid and discuss applications to recent work on discrete notions of curvature based on the effective resistance.
Lena
Weis
TU Berlin
Computing lines in tropical cubic surfaces
Abstract.
In the 1840s Arthur Cayley and George Salmon showed that a smooth cubic surface in \(\mathbb{P}^3\) contains exactly 27 lines. With the rise of tropical geometry the question of whether this theorem holds for tropical lines in smooth tropical cubic surfaces was posed. Vigeland (2010) was the first to observe that it can contain in fact infinitly many lines. Nonetheless, he conjectured that the aggregate count of isolated and families of lines remained invariant at 27. This conjecture was refuted by Hampe and Joswig (2017), as they discovered a smooth tropical cubic surface containing 26 isolated lines and 3 families of lines. In this talk we will show that the aggregated count can be also less than 27.
BĂĄlint
Zsigri
FU Berlin
Grassmannians, oriented matroids, and MacPherson's conjecture
May 2024
Lilla
Tothmeresz
ELTE
Relationships between the geometry of graph polytopes and graph structure
Abstract.
The symmetric edge polytope is a lattice polytope associated to a graph, that is actively investigated both because of its beautiful geometry, and because of its connections to the Kuramoto synchronization model of physics. One can also investigate ânon-symmetricâ edge polytopes, that are assigned to directed graphs instead of undirected ones. Moreover, one can even generalize them to regular (oriented) matroids. For these more general polytopes, many interesting geometric phenomena uncover themselves that are hidden for symmetric edge polytopes. We would like to demonstrate that the geometric properties of (graph and matroid) edge polytopes are connected to deep graph/matroid-theoretic properties. In particular, we show that the co-degree of an edge polytope is equal to the minimal cardinality of a dijoin. Other notions of combinatorial optimization also turn up naturally with respect to edge polytopes. In particular, for an Eulerian directed graph, complements of arborescences rooted at a given vertex give a (unimodular) triangulation of the edge polytope of the cographic matroid. This gives an alternative, geometric proof for the fact that an Eulerian digraph has the same number of arborescences for any choice of root vertex. I will also mention open problems. Based on joint work with TamĂĄs KĂĄlmĂĄn.
Ilia
Zharkov
KSU
Approximation of the diagonal and A-infinity structures on polytopes
Abstract.
Given a convex polytope P and a choice of a linear function on it one can define the multiplication on its cellular cochains by a cellular approximation of the diagonal in P^2. This is not associative (except for simplices and cubes) and gives rise to so called higher A-infinity products. I will describe a one-parameter family of permuto-associahedra based on a q-version of the Reiner-Ziegler realization. As q tends to zero, the family tends to the dual permutahedron. Restricted to a single permutation chamber, this inscribes the associahedron in the simplex similar to the Loday realization and allows one to give a geometric explanation of the A-infinity relations among the products. This is a part of a joint project with Gabe Kerr in the context of mirror symmetry. But in the talk we will restrict our attention to the combinatorics of the (fiber) polytopes.
Mateusz
Skomra
LAAS
Smoothed analysis of deterministic discounted and mean-payoff games
Abstract.
Deterministic turn-based discounted and mean-payoff games are fundamental classes of games with an unsettled complexity. They belong to the complexity classes NP and coNP, but are not known to be polynomial-time solvable. Furthermore, they are at the bottom of a hierarchy of complexity classes that stratifies the NP search problems. Despite these properties, the problem of solving turn-based games efficiently has been open for 35 years. Nevertheless, even though we do not know how to solve these games in polynomial time in the worst case, practical experiments suggest that solving random games is easy. More precisely, the policy iteration methods, which can take exponentially many steps in the worst case, converge quickly to the solution when the weights of the game are taken at random. The aim of my talk is to give an explanation of this phenomenon using the framework of "smoothed analysis" introduced by Spielman and Teng to explain the real-world efficiency of the simplex method. We prove that if the weights of a turn-based deterministic game are perturbed by a Gaussian noise, then the resulting randomized problem can be solved efficiently by a variant of a policy iteration method. This talk is based on a joint work with Bruno Loff.
Manuel
Bodirsky
TU Dresden
The Complexity of Constraint Satisfaction with Semilinear Constraints
Abstract.
The linear program feasibility problem is a well-studied example of a constraint satisfaction problem that can be solved in polynomial time. For some other CSPs over numeric domains, the computational complexity is wide open, such as satisfiability of max-plus systems. In this talk I will give a survey on what is known about the border of polynomial-time tractability and NP-hardness for the large class of CSPs where all the allowed constraints come from some fixed set of semilinear relations, i.e., relations that are definable over the rationals with addition and the order.
April 2024
Hankyung
Ko
Uppsala University
Coxeter combinatorics of double cosets
Abstract.
A Coxeter group is a group W together with a generating set S of reflections satisfying the (Coxeter-)braid relations. This talk concerns parabolic double cosets in a Coxeter group, i.e., double cosets with respect to subgroups generated by subsets of S. I will discuss how to express them and show the double coset braid relations from a joint work with Ben Elias. If there is time, I will also give an "atomic" description obtained more recently, partially jointly with Ben Elias, Nico Libedinsky, Leonardo Patimo.
Janike
Oldekop
TU Berlin
Likelihood Geometry of Reflexive Polytopes
Abstract.
We study the problem of maximum likelihood (ML) estimation for statistical models defined by reflexive polytopes. Our focus is on the ML degree of these models as a way of measuring the algebraic complexity of the corresponding optimization problem. We compute the ML degrees of all 4319 classes of three-dimensional reflexive polytopes and prove formulas for several general families, which include the hypercube and the cross-polytope in any dimension. We find some surprising behavior in terms of the gaps between ML degrees and degrees of the associated toric varieties, and we encounter some models of ML degree one. This is joint work with Carlos Améndola.
February 2024
Kyle
Huang
FU Berlin
Generating Smooth 3-Polytopes
Abstract.
Smooth polytopes are an important class of lattice polytope in combinatorial algebraic geometry, corresponding to smooth toric varieties. Open questions such as Oda's conjecture, BĂžgvad's Conjecture, and Ewald's question guide research, but the lack of meaningful examples hinders our ability to disprove even dramatic strengthenings of such conjectures. We describe and implement a novel algorithm for classifying 3-polytopes which extends past classification results by Haase, Lorenzo, and Paffenholz as well as Lundman. We also present theoretical findings on smooth 3-polytopes--in fact our theoretical and computational findings are intertwined and inform one another.
Eva
Philippe
Sorbonne Université
Geometric realizations via triangulations of flow polytopes
Abstract.
Building upon the example of the s-permutahedron, a combinatorial complex introduced by Ceballos and Pons in 2019 and conjectured to be polytopal, I will present a pathway to obtain geometric realizations of combinatorial complexes thanks to nice triangulations of flow polytopes, Cayley trick and tropical dualization. This is based on joint work with Rafael S. GonzĂĄlez DâLeĂłn, Alejandro H. Morales, Daniel Tamayo JimĂ©nez, Yannic Vargas, Martha Yip.
Sophie
Huiberts
LIMOS
Open problems about the simplex method
Abstract.
The simplex method is a very efficient algorithm. In this talk we see a few of the state-of-the-art theories for explaining this observation. We will discuss what it takes for a mathematical model to explain an algorithmâs qualities, and whether existing theories meet this bar. Following this, we will question what the simplex method is and if the theoretician's simplex method is the same algorithm as the practioner's simplex method.
January 2024
Nils
Mosis
TU Darmstadt
A Unified Worst Case for Classical Simplex and Policy Iteration Pivot Rules
Abstract.
We construct a family of Markov decision processes for which the policy iteration algorithm needs an exponential number of improving switches with Dantzigâs rule, with Blandâs rule, and with the Largest Increase pivot rule. This immediately translates to a family of linear programs for which the simplex algorithm needs an exponential number of pivot steps with the same three pivot rules. Our results yield a unified construction that simultaneously reproduces well-known lower bounds for these classical pivot rules, and we are able to infer that any (deterministic or randomized) combination of them cannot avoid an exponential worst-case behavior. Regarding the policy iteration algorithm, pivot rules typically switch multiple edges simultaneously and our lower bound for Dantzigâs rule and the Largest Increase rule, which perform only single switches, seem novel. Regarding the simplex algorithm, the individual lower bounds were previously obtained separately via deformed hypercube constructions. In contrast to previous bounds for the simplex algorithm via Markov decision processes, our rigorous analysis is reasonably concise.
Matthias
Schymura
BTU Cottbus-Senftenberg
On the size of integer programs with bounded subdeterminants
Abstract.
We study 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 n rows such that the absolute value of every n-by-n 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 n rows equals n^2 + n + 1. We investigate the problem in two settings: First, in the general case we obtain an upper bound of order O(Delta * n^4), that is, a linear bound in the parameter Delta. Secondly, under the additional assumption that no n-by-n minor of A vanishes, we prove an optimal linear bound for n=2 rows, and a sublinear bound for any n >= 3 rows. In the talk I will focus on the second setting and describe how we use tools from the theory of finite fields and from the geometry of numbers to get our results. This is based on joint work with Gennadiy Averkov, Björn Kriepke and Gohar Kyureghyan.
Ansgar
Freyer
TU Wien
Unimodular valuations beyond Ehrhart
Abstract.
The Betke-Kneser theorem characterizes the Ehrhart coefficients as the unique scalar-valued valuations on the set of lattice polytopes that are invariant under affine unimodular transformations. For tensor-valued valuations, a classification result in a similar spirit was pursued by Ludwig and Silverstein. If the tensor degree is at most 8, they showed that any unimodular equivariant and translation covariant tensor valuation is a linear combination of the so-called Ehrhart tensor coefficients. Moreover, they gave an example of a valuation from lattice polygons into tensors of degree 9 that does not arise as a linear combination of Ehrhart tensor coefficients. In the talk we complete the classification of tensor valued valuations in the planar case. To this end, we draw a connection between tensor valuations on lattice polygons and invariants with respect to a specific finite group. This connection will explain the particular significance of the number 8 in the work of Ludwig and Silverstein. Our approach also yields a classification of power series-valued valuations on lattice polygons, as well as a partial classification of tensor-valuations on 3-dimensional lattice polytopes. This is joint work with Monika Ludwig and Martin Rubey.
December 2023
Hannah
Tillmann-Morris
University College London
Detecting blow-ups of Fano varieties via their Laurent polynomial mirrors
Abstract.
Mirror symmetry gives a correspondence between certain Fano varieties and Laurent polynomials, translating the classification of Fano varieties up to deformation into a combinatorial problem. I will present a set of combinatorial conditions $\Phi$ on pairs of Laurent polynomials $(f,g)$ which imply the existence of mirror Fano varieties $X_f$ and $X_g$ related by a blow-up map $X_g \to X_f$. These criteria generalise the relationship between fans of toric varieties related by toric blowup; I will explain how in some key examples. Time permitting, I will discuss a new approach to constructing mirrors to Laurent polynomials, which is the main idea in the proof that Laurent polynomials in two variables satisfying the conditions $\Phi$ have mirrors related by blowing up in one point. This is based on upcoming joint work with Mark Gross.
Neil
Olver
LSE
A strongly polynomial algorithm for linear programs with at most two non-zero entries per row or column
Abstract.
We give a strongly polynomial algorithm for minimum cost generalized flow, and hence for optimizing any linear program with at most two non-zero entries per row, or at most two non-zero entries per column. Our result can be viewed as progress towards understanding whether all linear programs can be solved in strongly polynomial time, also referred to as Smale's 9th problem. Our approach is based on the recent primal-dual interior point method (IPM) due to Allamigeon, Dadush, Loho, Natura and VĂ©gh (FOCS '22). They show that the number of iterations needed by the IPM can be bounded in terms of the straight line complexity of the central path; roughly speaking, this is the minimum number of pieces of any piecewise linear curve that multiplicatively approximates the central path. As our main contribution, we show that the straight line complexity of any minimum cost generalized flow instance is polynomial in the number of arcs and vertices. By a reduction of Hochbaum, the same bound applies to any linear program with at most two non-zeros per column or per row. Further, we demonstrate how to handle initialization, and how to ensure that the bit complexity of each iterate remains bounded during the execution of the algorithm. Joint work with Daniel Dadush, Zhuan Khye Koh, Bento Natura and LĂĄszlĂł VĂ©gh.
November 2023
Myfanwy
Evans
Uni Potsdam
Geometry-based simulation of self assembly
Abstract.
The morphometric approach to solvation free energy is a geometry-based theory that incorporates a weighted combination of geometric measures over the solvent accessible surface for solute configurations in a solvent. In this talk, I will demonstrate that employing this geometric technique in simulating the self assembly of sphere clusters and small loops results in an assortment of interesting geometric configurations. This gives insight into the role of shape in the physical process of self assembly, potentially relevant to proteins, viruses and other complex systems.
Marie
Brandenburg
MPI MiS Leipzig
How to slice a polytope
Abstract.
Given a 3-dimensional cube, the intersection with an affine hyperplane is always a polygon with 3,4,5, or 6 vertices. But how can one understand the slices of a general polytope? And which slice is âthe bestâ, e.g. is the slice of maximal volume? In this talk, we consider the structure of all possible affine hyperplane sections of a convex polytope, and we craft algorithms that compute optimal sections for various combinatorial and metric criteria. Along the way, we will encounter several famous hyperplane arrangements which will guide our algorithms. This is based on joint work with Jesus De Loera and Chiara Meroni.
Christoph
Hertrich
Goethe-UniversitÀt Frankfurt
Understanding Neural Network Expressivity via Polyhedral Geometry
Abstract.
Neural networks with rectified linear unit (ReLU) activations are one of the standard models in modern machine learning. Despite their practical importance, fundamental theoretical questions concerning ReLU networks remain open until today. For instance, what is the precise set of (piecewise linear) functions representable by ReLU networks with a given depth? Even the special case asking for the number of layers to compute a function as simple as max{0, x_1, x_2, x_3, x_4} has not been solved yet. In this talk I will convince you that polyhedral geometry is a useful perspective to study such questions and I will report about recent progress using mixed-integer programming and subdivisions of lattice polytopes. This is based on joint works with Amitabh Basu, Marco Di Summa, and Martin Skutella (NeurIPS 2021), as well as Christian Haase and Georg Loho (ICLR 2023).
Olaf
Parczyk
FU Berlin
New Ramsey Multiplicity Bounds and Search Heuristics
Abstract.
We study two related problems concerning the number of monochromatic cliques in two-colorings of the complete graph that go back to questions of ErdĆs. Most notably, we provide the first substantial improvement on the 25-year-old upper bounds of Thomason on the Ramsey multiplicity of K_4 and K_5 and we settle the minimum number of independent sets of size 4 in graphs with clique number at most 4. Motivated by the elusiveness of the symmetric Ramsey multiplicity problem, we also introduce an off-diagonal variant and obtain tight results when counting monochromatic K_4 or K_5 in only one of the colors and triangles in the other. The extremal constructions for each problem turn out to be blow-ups of a finite graph and were found through search heuristics. They are complemented by lower bounds and stability results established using Flag Algebras, resulting in a fully computer-assisted approach. More broadly, these problems lead us to the study of the region of possible pairs of clique and independent set densities that can be realized as the limit of some sequence of graphs. Joint work with Sebastian Pokutta, Christoph Spiegel and Tibor SzabĂł.
Justin
Lanier
University of Sydney
Section problems for configuration spaces
Abstract.
Is there a continuous rule for adding a new distinct point to configurations of n distinct points in a given space X? For instance, when X is a closed ball and n is 1, the answer is no by Brouwerâs fixed-point theorem. This âadd a pointâ problem can be phrased as a question about the existence of a continuous section of the forgetful map from the configuration space on X of n+1 points to the configuration space on X of n points. I will discuss the cases where the X is the plane, a closed ball, or a graph, treated respectively in work by Lei Chen, in my joint work with Lei Chen and Nir Gadish, and in work by Alexander Bauman.
October 2023
Moritz
Grillo
TU Berlin
Topological expressive power of ReLU neural networks
Abstract.
We study the expressivity of ReLU neural networks in the setting of a binary classification problem from a topological perspective. Recently, empirical studies showed that neural networks operate by changing topology, transforming a topologically complicated data set into a topologically simpler one as it passes through the layers. This topological simplification has been measured by Betti numbers. We use the same measure to establish lower and upper bounds on the topological simplification a ReLU neural network can achieve with a given architecture. We therefore contribute to a better understanding of the expressivity of ReLU neural networks in the context of binary classification problems by shedding light on their ability to capture the underlying topological structure of the data. In particular the results show that deep ReLU neural networks are exponentially more powerful than shallow ones in terms of topological simplification.
July 2023
Tatiana
Levinson
FU Berlin
Transversal Nandakumar & Ramana Rao problem with the glimpse of algebraic topology side
Abstract.
In 2006 Nandakumar asked whether, for a given polygon on a plane and an integer m, it is always possible to find a partition of this polygon into m convex pieces of equal area and perimeter. The problem turned out to be surprisingly hard - almost two decades later the full answer is not known. On the other hand, this question allows many interesting generalisations, for example by asking the same question for a d-polytope, and partitions that equalise volume and some d-1 continuous functions on the space of full-dimensional compact convex bodies in R^d. In this talk, we will discuss the original Nandakumar & Ramano Rao problem and will see how an application of algebraic topology methods allowed Karasev, Hubard & Aronov and Blagojevic & Ziegler to find a partial solution. Then we will consider its transversal generalisation, in which we aim to equipart more than d-1 functions by choosing a suitable polytope from some family of d-polytopes. We will examine the new challenges it brings to the algebraic topology side of the problem and some ways to overcome them. We will also discuss the inherent limitations of the algebraic approach to this problem and the questions about the polytopes it gives rise to. This talk is based on my PhD thesis.
Anton
Dochtermann
Texas State University
Parking function ideals on generalized permutohedra
Abstract.
Suppose G is a finite graph with specified sink vertex q. The `G-parking functions' (relative to q) are combinatorial objects with connections to algebra (eg power ideals) and combinatorics (eg chip-firing on G). As studied by Postinov and Shapiro, one way to define a G-PF is as a standard monomial of a certain monomial ideal M_G associated with G. It turns out that the generators of M_G are described by the facets of the corresponding zonotope Z_G that are visible when one views Z_G `from the direction q'. Furthermore the facial structure of Z_G describes a minimal cellular resolution of M_G. We extend these constructions to generalized permutohedra P given by sums of simplices. Viewing P from a sink direction, we again obtain a monomial ideal generated by the visible facets. The algebraic results seem to generalize nicely, and can even be extended to mixed subdivisions of P. On the combinatorial side, the standard monomials of this ideal lead to notions of chip-firing on hypergraphs, where many questions remain. This is joint work with Ayah Almousa and Ben Smith, as well as an REU program co-advised with Suho Oh.
Helena
Bergold
FU Berlin
An Extension Theorem for Signotopes
Abstract.
In 1926, Levi showed that, for every pseudoline arrangement A and two points in the plane, A can be extended by a pseudoline which contains the two prescribed points. Later extendability was studied for arrangements of pseudohyperplanes in higher dimensions. While the extendability of an arrangement of proper hyperplanes in R^d with a hyperplane containing d prescribed points is trivial, Richter-Gebert found an arrangement of pseudoplanes in R^3 which cannot be extended with a pseudoplane containing two particular prescribed points. In this talk, we investigate the extendability of signotopes, which are a combinatorial structure encoding a rich subclass of pseudohyperplane arrangements. We show that signotopes of odd rank are extendable in the sense that for two prescribed crossing points we can add an element containing them.
June 2023
Sebastian
Manecke
Goethe UniversitÀt Frankfurt
The twisted-incidence algebra of angles
Abstract.
The study of valuations emerged from Hilberts 3rd problem and has since been a useful tool to understand various dissection problems. In this talk we consider valuations on polyhedral cones, examples of which arise in convex and polyhedral geometry as well as algebraic combinatorics. Such valuations can be used to measure angles between faces of polyhedra and thus angles are naturally an element in the incidence algebra of face lattices. Adding a twist to the convolution product turns the set of angles into an subalgebra of the (twisted-)incidence algebra. This algebra provides a very general and unified framework for dissection statements on cones and can be used to recover old and obtain new dissections with simple proofs.
Matthias
Beck
San Francisco State University
Integer-point transforms, symmetric functions, and q-Ehrhart polynomials
Abstract.
The integer-point transform of a rational polyhedron P encodes all integer lattice points of P as a multivariate rational generating function. It has applications in combinatorics, commutative algebra, number theory, and many other fields. We will discuss some connections with work of Chapoton (2016) on the q-Ehrhart polynomial of P, a 2-variable generalization of the integer-point counting function of dilates of P. Motivated by Stanley's chromatic symmetric function (1995) generalization of the chromatic polynomial of a graph, we propose a study of symmetric functions attached to certain rational polytopes.
Esme
Bajo
UC Berkeley
q-analog chromatic polynomials
Abstract.
Stanley (1995) introduced a symmetric function generalization of the chromatic polynomial, and conjectured that it distinguishes non-isomorphic trees. We discuss a geometric approach to this problem using Chapotonâs q-analog weighted Ehrhart theory, wherein we express the principal specialization of the chromatic symmetric function as a polynomial in the q-integers and study its coefficients in different bases. This is joint work with Matthias Beck and AndrĂ©s R. Vindas-MelĂ©ndez.
May 2023
Kris
Shaw
University of Oslo
The birational geometry of matroids
Abstract.
In this talk, I will consider isomorphisms of Bergman fans of matroids. Motivated by algebraic geometry, these isomorphisms can be considered as matroid analogs of birational maps. I will introduce Cremona automorphisms of the coarsest fan structure. These produce a class of automorphisms which do not come from automorphisms of the underlying matroid. I will then explain that the automorphism group of the coarse fan structure is generated by matroid automorphisms and Cremona maps when the fan is 2-dimensional and also for modularly complemented matroids. I will assume no background on matroid theory for this talk. This is based on joint work with Annette Werner.
Bernd
Sturmfels
MPI Leipzig
Positive del Pezzo geometry
Abstract.
Positive geometry is an emerging field at the interface of combinatorics, algebraic geometry and physics. This lecture explores the positive geometries associated with del Pezzo surfaces and their moduli spaces. Scattering amplitudes offer new vistas on configurations of six and seven points in the plane, their Weyl group symmetries of types E6 and E7, and on 27 lines on real and tropical cubic surfaces. This is work in progress with Nick Early, Alheydis Geiger, Marta Panizzut and Claudia Yun.
Raul
Penaguiao
MPI Leipzig
Linear Tropical Geometry with Matroids
Abstract.
There are several ways of computing the degree of varieties, but the most basic one is to intersect your variety with a line. We will be doing the same in the tropical world. In this talk, we will introduce the Bergman fan of a matroid, our tropical variety of interest. We study its combinatorics and identify its degree. Interesting things arise when we apply the Cremona map to the Bergman fan, which flips x \to -x. This new fan recovers some interesting beta invariants with the number of so called nbc bases. With the techniques developed we will compute the likelihood degeneracy degree of a matroid and recover a result from Agostini et al. All these results are algorithmic, which is a new way of computing this degree.
April 2023
Manfred
Scheucher
TU Berlin
Using SAT Solvers in Combinatorics and Geometry
Abstract.
In this talk, we discuss how modern SAT solvers can be used to tackle mathematical problems. We discuss various problems to give the audience a better understanding, which might be tackled in this fashion, and which might not. Besides the naive SAT formulation further ideas are sometimes required to tackle problems. Additional constraints such as statements which hold 'without loss of generality' might need to be added so that solvers terminate in reasonable time.
Christian
Stump
Ruhr-UniversitÀt Bochum
The Poincaré-extended ab-index
Abstract.
Motivated by a conjecture of Maglione-Voll concerning Igusa zeta functions, we introduce and study the PoincarĂ©-extended ab-index. This polynomial generalizes both the ab-index and the PoincarĂ© polynomial. For posets admitting R-labelings, we prove that the coefficients are nonnegative and give a combinatorial description of the coefficients. This proves Maglione-Vollâs conjecture as well as a conjecture of the KĂŒhne-Maglione. We also recover, generalize, and unify results from Billera-Ehrenborg-Readdy, Ehrenborg, and Saliola-Thomas. This is joint work with Galen Dorpalen-Barry and Josh Maglione.
February 2023
Thomas
Kahle
OvGU Magdeburg
No short polynomials in determinantal ideals
Abstract.
We discuss the problem of determining (algorithmically or otherwise) the shortest polynomial in an ideal of the polynomial ring. Here shortness is measured in the number of terms of polynomials. While the general problem of determining if an ideal contains a polynomial with at most t terms is unsolved, we show that the shortest polynomials in a determinantal ideal are determinants. This implies that the shortest polynomials vanishing on all rank-r matrices must have (r+1)! terms and are thus not particularly short.
Omid
Amini
Ăcole Polytechnique
Convexity in tropical geometry
Abstract.
What is a tropical polytope? Is it possible to associate a (usual) convex body to a tropical polytope? Which informations are preserved in passing? I will present results around the notion of convexity in tropical geometry, focusing on the local setting, that of tropical fans and their supports named tropicalfanfolds, with the aim of answering the above questions. Based on joint works with Matthieu Piquerez.
SofĂa
GarzĂłn
FU Berlin
Weighted Ehrhart Theory
Abstract.
Since Ehrhart's original work in the late 1960's, Ehrhart theory has developed into a key topic at the intersection of polyhedral geometry, number theory, commutative algebra, algebraic geometry, enumerative combinatorics, and integer programming. Here we examine an approach where instead of counting lattice points in polytopes, we define a weight function and count the evaluations of this function at the lattice points instead. We will study which of the properties of the original h*-vector hold more generally in the weighted case for some nicely behaved functions and we will see some counterexamples as to why we need some hypothesis on the weights. This leads us to a generalization of Stanleyâs celebrated theorem about the h*-polynomial of the Ehrhart Series having nonnegative coefficients for some specific families of weight functions.
January 2023
Karin
Schaller
FU Berlin
Combinatorial identity relating LDP-polygons to the number 12
Abstract.
In [Batyrev-S. 2017], we give a combinatorial interpretation of the stringy Libgober-Wood identity in terms of generalized stringy Hodge numbers and intersection products of stringy Chern classes for arbitrary projective Q-Gorenstein toric varieties. Simultaneously we introduce stringy E-functions and stringy Chern classes in general for projective varieties with at worst log-terminal singularities. As an application we derive a novel combinatorial identity extending the well-known formula for reflexive polygons including the number 12 to LDP-polygons and toric log del Pezzo surfaces, respectively. In the mentioned work, our proof depends largely on the powerful connection between algebraic geometry and combinatorics of polytopes. Nevertheless, we will leave the connection behind and present a purely combinatorial proof for this identity that is equivalent to the stringy Libgober-Wood identity and relates LDP-polygons to the number 12. This talk is based on joint work in progress with Ulrike BĂŒcking, Christian Hasse, and Jan-Hendrik de Wiljes.
Martina
Juhnke
OsnabrĂŒck
On cosmological polytopes
Abstract.
In this talk, I will consider cosmological polytopes, a class of lattice polytopes that can be constructed from a graph. Those polytopes were originally defined and studied by Arkani-Hamed, Benincasa, and Postnikov in their study of the wavefunction of the universe. The goal of this talk is to understand how geometric invariants, e.g., their volume and triangulations, of these polytopes are related to the combinatorics of the underlying graph. In particular, we will show that these polytopes have a regular unimodular triangulation by computing an explicit squarefree Gröbner basis for the corresponding toric ideals. We will describe the maximal cells in these triangulations by Feynman diagram like graphs. As a consequence, we are able to compute the normalized volume of the cosmological polytope for paths and cycles. This is joint work (in progress) with Liam Solus and Lorenzo Venturello.
Martin
Winter
Warwick
On 4-flat graphs and the embeddability of 2-complexes in dimension four
Abstract.
I will discuss the following graph class introduced by van der Holst: for a graph G let C(G) denote the 2-dimensional (CW-)complex obtained by gluing 2-cells to all cycles of G. G is called 4-flat if C(G) embeds (piecewise linearly) into R^4. This graph class is a natural candidate for generalizing planar and linkless graphs and I briefly address the (partially conjectural) evidence for and against this claim. In our work we studied operations on 2-complexes that preserve embeddability into R^4. Based on this we were able to confirm two conjectures of van der Holst: 4-flat graphs are closed under doubling edges and under Delta-Y transforms. Whether 4-flat graphs are closed under Y-Delta transforms remains open. We furthermore showed that the following two graph classes are actually equivalent to 4-flat graphs, even though the requirement is seemingly much stronger (i) resp. weaker (ii): instead of attaching 2-cells to all cycles of G, we attach 2-cells to (i) all closed walk in G. (ii) all induced cycles in G. If time remains, I demonstrate how topological graph theory can be used to construct a 2-complex that embeds into R^4 piecewise linearly, but not smoothly. This talk is a result of joined work with Agelos Georgakopoulos (University of Warwick) and Tam Nguyen-Phan (Karlsruhe Institute of Technology).
December 2022
Alex
Black
UC Davis
Realizable Standard Young Tableaux
Abstract.
Given two vectors u and v, their tropical outer product (or outer sum) is given by the matrix A with entries A_{jk} = u_{j} + v_{k}. If the entries of u and v are increasing and sufficiently generic, the total ordering of the entries of the matrix is a standard Young tableau of rectangular shape. Similarly, given a generic configuration of n points in two-dimensions, the total ordering of all the slopes between pairs of points gives rise to a standard Young tableau of staircase shape. We call standard Young tableaux that arise in either way realizable. Realizable tableaux appear independently in many contexts including sorting algorithms, quantum computing, random sorting networks, reflection arrangements, fiber polytopes, and Goodman and Pollack's theory of allowable sequences. However, little is known about their combinatorial structure. In particular, a basic question is: How many are there? Equivalently, what is the probability that a random standard Young tableaux is realizable? In this talk, I will discuss my recent joint work with Igor Araujo, Amanda Burcroff, Yibo Gao, Robert Krueger, and Alex McDonough in which we use algebraic and polyhedral geometry to address these questions asymptotically.
November 2022
Alexandru
Suciu
Polyhedral products, duality properties, and cohomology jump loci
Abstract.
The polyhedral product is a functorial construction that assigns to each simplicial complex $K$ on $n$ vertices, and to each pair of topological spaces, $(X,A)$, a certain subspace, $\mathcal{Z}_K(X,A)$, of the Cartesian product of $n$ copies of $X$. I will discuss some of the relationships between the duality properties of these spaces and the Cohen-Macaulay property of the original simplicial complex, and the interplay between the cohomology jump loci of right-angled Artin groups and Bestvina--Brady groups.
Georg
Loho
University of Twente
Generalized permutahedra and positive flag Dressians
Abstract.
Generalized permutahedra appear in various areas from submodular function optimization to the study of Grassmannians and Flag varieties. I will give an introduction to some of their geometric and combinatorial properties leading to the study of their subdivisions. Those arise naturally in Tropical Geometry and Discrete Convex Analysis. I present a new characterization of the corresponding height functions and show how to refine this for the study of positivity. The talk is based on joint work with Michael Joswig, Dante Luber and Jorge Alberto Olarte (https://arxiv.org/abs/2111.13676).
Andreas
Kretschmer
OvGU Magdeburg
Thin polytopes: lattice polytopes with vanishing local h*-polynomial
Abstract.
I will introduce the local h*-polynomial of a lattice polytope and give its main properties, like palindromicity and non-negativity, and how it interacts with the usual h*-polynomial and combinatorial invariants of the polytope. We call a lattice polytope thin if its local h*-polynomial vanishes, and I am going to explain the classification of thin polytopes in dimension 3 and a characterization in the Gorenstein case of arbitrary dimension. I will also mention an open question relating thinness to the width of a lattice polytope.
Martin
Henk
TU Berlin
Linear and affine subspace concentration conditions (for centered polytopes)
Abstract.
The linear subspace concentration conditions play a crucial role in the log-Minkowski problem which, in the discrete setting, asks for a characterization of the cone-volumes of polytopes, i.e., the volumes of the cones given by the convex hull of a facet and the origin, which is supposed to be an interior point of the polytope. This problem is only solved in the symmetric case, but it is known that also centered polytopes, i.e, the centroid is at the origin, satisfy certain linear subspace concentration conditions. Based on these linear conditions, K.-Y. Wu introduced recently affine subspace concentration conditions and proved them for centered, reflexive, smooth lattice polytopes. We extend this result to arbitrary centered polytopes. This is joint work with Ansgar Freyer (TU Vienna) and Christian Kipp (TU Berlin).
October 2022
Giulia
Codenotti
An overview of classifications of lattice polytopes
Abstract.
In this survey talk we will touch on classifications of different classes of lattice polytopes, such as those of low volume, hollow polytopes, or empty simplices. We will explore the special role played by lattice width in these classifications and discuss some tools coming from Geometry of Numbers used in these contexts. A particular focus will be on empty simplices and open questions regarding their h^* vectors and related invariants.
July 2022
Anton
Dochtermann
Texas State University
Anna
Hartkopf
FU Berlin
and
Erin
Henning
FU Berlin
Mathematical Science Communication
Abstract.
Quality science journalism is a crucial tool in science communication to build a relationship between scientific mathematics and society that is based on mutual trust. The MIP.labor is a research project for science journalism in mathematics, computer science and physics at the Freie UniversitÀt Berlin. In our talk, we will first outline the theoretical foundations of science communication and briefly introduce a classification of its practice. In the second part of the talk, we will present the operating principle of the research being done at the MIP.labor, which includes research on the development of new formats of science journalism as well as scientifically evaluating them. In collaboration with the National Institute for Science Communication (NaWik), instruments are being tested to analyze the reception of these formats. With this cooperation, MIP.labor aims to critically reflect on the developed formats in order to advance the connection between the theory and practice of science communication.
June 2022
Matthias
Beck
San Francisco State University
f^*- and h^*-vectors
Abstract.
If P is a lattice polytope (i.e., P is the convex hull of finitely many integer points in R^d), Ehrhart's theorem asserts that the integer-point counting function L_P(m) = #(mP \\cap Z^d) is a polynomial in the integer variable m. Our goal is to study structural properties of Ehrhart polynomials - essentially 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), âŠ, \\binom(m+d,d), has nonnegative coefficients; these coefficients 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), âŠ; the coefficients 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 JĂ©ronimo Valencia) about f^*- and h^*-vectors, including analogues and dissimilarities with f- and h-vectors of polytopes and polyhedral complexes.
Alexey
Garber
University of Texas Rio Grande Valley
Concrete polytopes may not tile the space
Abstract.
Pickâs formula gives a simple way to connect area of lattice polygon $P$ with lattice points inside $P$. Particularly, Pickâs theorem claims that the discrete volume of $P$ coincides with the Euclidean volume of $P$. Unfortunately, there is not generalization of this property for lattice polytopes in higher dimensions. In an attempt to extend Pickâs theorem to higher dimensions, Brandolini et al. conjectured that equality of discrete and Euclidean volumes implies a tileability property for lattice polytopes. In the talk I will present a construction of family of counterexamples to this conjecture. The construction is based on McMullenâs theory of valuations of lattice polytopes and Dehnâs invariant. The talk is based on joint result with Igor Pak (UCLA).
Frédéric
Meunier
Ăcole Nationale des Ponts et ChaussĂ©es
Coloring complements of line graphs
Abstract.
Our purpose is to show that complements of line graphs enjoy nice coloring properties. For instance, all graphs in this class have their local chromatic number equal to their (usual) chromatic number. We also provide a sufficient condition for the chromatic number to be equal to a natural upper bound. A consequence of this latter condition is a complete characterization of all induced subgraphs of the Kneser graph KG(n, 2) that have a chromatic number equal to its chromatic number, namely n â 2. In addition to the upper bound, a lower bound is provided by Dolânikovâs theorem, a classical result of the topological method in graph theory. We prove the NP-hardness of deciding the equality between the chromatic number and any of these bounds. The topological method is especially suitable for the study of coloring properties of complements of line graphs of hypergraphs. Nevertheless, all proofs are elementary and we provide a short discussion on the ability for the topological methods to cover some of our results. Joint work with Hamid Reza Danehspajouh and Guilhem Mizrahi.
Steven
Simon
Bard College
Ron
Aharoni
Technion
May 2022
Shira
Zerbib
Iowa State University
Line transversals in families of connected sets in the plane
Abstract.
We prove that if a family of compact connected sets in the plane has the property that every three members of it are intersected by a line, then there are three lines intersecting all the sets in the family. This answers a question of Eckhoff from 1993, who proved that under the same condition there are four lines intersecting all the sets. We also prove a colorful version of this result under weakened conditions on the sets, improving results of Holmsen from 2013. Our proofs use the topological KKM theorem. Joint with Daniel McGinnis.
Amzi
Jeffs
Carnegie Mellon University
Enumerating interval graphs and d-representable complexes
Abstract.
Given a collection of n convex sets in R^d, one can record how they intersect using a simplicial complex on the vertex set [n] = {1, 2, ..., n} called the nerve. Simplicial complexes that arise this way are called d-representable, and enjoy a variety of interesting combinatorial properties, such as d-collapsibility. However, the number of these complexes has not been previously studied, except in the case d=1, which amounts to counting interval graphs with n vertices. We show that the number of d-representable complexes on vertex set [n] is exp(Theta(n^d log n)), and provide bounds on the constants involved. As a consequence, we show that d-representable complexes comprise a vanishingly small fraction of d-collapsible complexes. In the case d=1 our results are more precise, and improve the previous best asymptotics for the number of interval graphs. These results are joint work with Boris Bukh.
Samantha
Fairchild
University of OsnabrĂŒck and MPI Leipzig
Counting pairs of saddle connections
Abstract.
A translation surface is a collection of polygons in the plane with parallel sides identified by translation to form a Riemann surface with a singular Euclidean structure. A saddle connection is a special type of closed geodesic, and the set of saddle connections can be associated to a discrete subset of the complex plane. I will discuss recent work showing that for almost every translation surface the number of pairs of saddle connections with bounded virtual area has quadratic asymptotic growth. No previous knowledge of translation surfaces or counting problems will be assumed. This is based on joint work with Jayadev Athreya and Howard Masur.
April 2022
Florian
Frick
FU Berlin and Carnegie Mellon University
Embeddings, chirality, triangulations
Abstract.
An object is chiral if it has a left-handed and a right-handed version, where one cannot be deformed into the other. A space that is chiral in (d+1)-space cannot embed into d-space. I will explain how to extend classical non-embeddability results to chirality results using triangulations of spaces. In fact, one can derive bounds for the topology of the space of embeddings this way. This is joint work with M. Harrison (IAS).
Eleonore
Bach
FU Berlin
Cographic hyperplane arrangements, flow zonotopes and their Ehrhart polynomials
Abstract.
Geometrically carrying a trove of information about the underlying simple graph, the graphic hyperplane arrangement $H_G$ yields an interesting mathematical object to study a simple graph $G$. For example, one proves that the regions of $H_G$ are in one-to-one correspondence to the acyclic orientations of $G$ and that the normal vectors of $H_G$ are linearly independent if and only if they induce forests on $G$. The latter is related to the independent sets of the graphic matroid which is the matroid associated to the graphic hyperplane arrangement. Furthermore, we associate with graphic hyperplane arrangements graphic zonotopes whose Ehrhart polynomials are related to the independent sets of the graphic matroid. In this talk we explain how the cographic hyperplane arrangement arises as a dual of its graphic counterpart. This is accomplished through matroid duality, graph duality and dualizing the chain complex associated to the faces of a special polytope. Completing this dual picture, a final result shown in this talk describes the coefficients of the Ehrhart polynomial of the flow zonotope, which is the zonotope associated to the cographic hyperplane arrangement.
February 2022
Paul
Breiding
MPI Leipzig
The Zonoid Algebra
Abstract.
In this talk I will introduce the zonoid algebra. Starting from the monoid structure of zonoids in R^d I will explain how to turn this structure into an algebra, where we can âmultiplyâ zonoids. I will show that every multilinear map between finite dimensional vector spaces has a unique, continuous, Minkowski multilinear extension to the corresponding space of zonoids. Taking the wedge product of vector spaces as the multilinear map, we get a definition of the wedge of zonoids. This is the definition of the product in our algebra. The motivation for this construction comes from probabilistic intersection theory in a compact homogeneous space, where the zonoid algebra plays the role of a probabilistic cohomology ring. This is joint work with Antonio Lerario, Leo Mathis and Peter BĂŒrgisser.
Raman
Sanyal
Goethe-UniversitÀt Frankfurt
Pivot rules and polytopes
Abstract.
The simplex algorithm is the method of choice for solving linear programs but itâs running time crucially depends on the chosen pivot rule. In joint work with Black, De Loera, and LĂŒtjeharms, we introduced a new family of pivot rules, the normalized-weight pivot rules, that has a number of interesting features. In particular, normalized-weight pivot rules can be parametrized in a natural continuous manner and the behavior on a fixed linear program is governed by a polytope, the pivot rule polytope. In this talk I want to give an introduction to normalized-weight pivot rules and their associated polytopes with an emphasis on combinatorics: Among pivot-rule polytopes one finds monotone path polytopes, sweep polytopes, permutahedra, associahedra and many more old and new friends from algebraic and geometric combinatorics.
January 2022
Antonio
Macchia
FU Berlin
General non-realizability certificates for spheres with linear programming
Abstract.
A classical problem in polytope theory is whether a given combinatorial polytope is realizable as the boundary of a convex polytope. Attempts to answer this question often rely on the theory of oriented matroids, the classification of spheres with a certain dimension and number of vertices and the search for non-realizability certificates based on Grassmann-PlĂŒcker relations, called final polynomials. Due to the large number of such relations, it is often necessary to require special assumptions on the structure of the final polynomials. I will present a new method to search for algebraic certificates of non-realizability with no prescribed structure. Our algorithm combines linear programming together with the compact description of the realization space of a polytope given by the so-called reduced slack model, which we developed starting from the notion of slack matrix. This allows us to produce non-realizability certificates for several large simplicial and quasi-simplicial spheres whose realizability was not previously known. This is a joint work with JoĂŁo Gouveia and Amy Wiebe.
Zuzana
PatĂĄkovĂĄ
Charles University Prague
On Radon and fractional Helly theorems
Abstract.
Radon theorem plays a basic role in many results of combinatorial convexity. It says that any set of d+2 points in R^d can be split into two parts so that their convex hulls intersect. It implies Helly theorem and as shown recently also its more robust version, so-called fractional Helly theorem. By standard techniques this consequently yields an existence of weak epsilon nets and a (p,q)-theorem. We will show that we can obtain these results even without assuming convexity, replacing it with very weak topological conditions. More precisely, given an intersection-closed family F of subsets of R^d, we will measure the complexity of F by the supremum of the first d/2 Betti numbers over all elements of F. We show that bounded complexity of F guarantees versions of all the results mentioned above. Partially based on joint work with Xavier Goaoc and Andreas Holmsen.
December 2021
Lukas
KĂŒhne
MPI Leipzig
Matroids and Algebra
Abstract.
A matroid is a combinatorial object based on an abstraction of linear independence in vector spaces and forests in graphs. I will discuss how matroid theory interacts with algebra via the so-called von Staudt constructions. These are combinatorial gadgets to encode polynomials in matroids. A main application is concerned with generalized matroid representations over division rings, matrix rings and probability space representations together with their relation to group theory. Based on joint work with Rudi Pendavingh and Geva Yashfe.
Mariel
Supina
KTH
The Universal Valuation for Coxeter Matroids
Abstract.
Matroids are combinatorial objects that generalize the notion of independence, and their subdivisions have rich connections to geometry. Thus we are often interested in functions on matroids that behave nicely with respect to subdivisions, which are called valuations. Matroids are naturally linked to the symmetric group; generalizing to other finite reflection groups gives rise to Coxeter matroids. I will give an overview of these ideas and then present some work with Chris Eur and Mario Sanchez on constructing the universal valuative invariant of Coxeter matroids. Since matroids and their Coxeter analogues can be understood as families of polytopes with special combinatorial properties, I will present these results from a polytopal perspective.
November 2021
Henry
Adams
Colorado State University
Gromov-Hausdorff distances, Borsuk-Ulam theorems, and Vietoris-Rips complexes
Abstract.
The Gromov-Hausdorff distance between two metric spaces is an important tool in geometry, but it is difficult to compute. For example, the Gromov-Hausdorff distance between unit spheres of different dimensions is unknown in nearly all cases. I will introduce recent work by Lim, Memoli, and Okutan that lower bounds the Gromov-Hausdorff distance between spheres using Borsuk-Ulam theorems. We improve these lower bounds by connecting this story to Vietoris-Rips complexes.
Galen
Dorpalen-Barry
Ruhr-UniversitÀt Bochum
Cones of Hyperplane Arrangements through the Varchenko-Gelâfand Ring
Abstract.
The coefficients of the characteristic polynomial of an arrangement in a real vector space have many interpretations. An interesting one is provided by the Varchenko-Gelâfand ring, which is the ring of functions from the chambers of the arrangement to the integers with pointwise multiplication. Varchenko and Gelâfand gave a simple presentation for this ring, along with a filtration whose associated graded ring has its Hilbert function given by the coefficients of the characteristic polynomial. We generalize these results to cones defined by intersections of halfspaces of some of the hyperplanes.
Eleni
Tzanaki
U Crete
Upper bounds on the number of faces of the Minkowski sum of polytopes
Abstract.
Given two convex polytopes P, Q, their Minkowski sum, which is again a polytope, is defined as P + Q = {p + q : p â P, q â Q}. In this talk I will present tight expressions for the maximum number of k-dimensional faces, 0 †k †d â 1, of the Minkowski sum P_1 + P_2 of two convex d-dimensional polytopes in R_d. These upper bounds are proved making use of basic notions such as f - and h-vector calculus, stellar-subdivisions and shellings, and generalize the steps used by McMullen to prove the Upper Bound Theorem for polytopes. The key idea behind the approach is to express the Minkowski sum P_1 + P_2 as a section of the Cayley polytope C of the summands; bounding the k-faces of P_1 + P_2 reduces to bounding the subset of the (k + 1)-faces of C that contain vertices from each of the two summands. I will briefly explain how these steps should be adjusted when one considers the Minkowski sum of three or more polytopes. This is joint work with M. Karavelas.
Jesus
De Loera
UC Davis
Stochastic Tverberg-type theorems and their relevance in Machine Learning and Statistical Inference
Abstract.
Discrete geometry can play a role in foundations of data science. Here I present concrete examples. In statistical inference we wish to find the properties or parameters of a distribution or model through sufficiently many samples. A famous example is logistic regression, a popular non-linear model in multivariate statistics and supervised learning. Users often rely on optimizing of maximum likelihood estimation, but how much training data do we need, as a function of the dimension of the covariates of the data, before we expect an MLE to exist with high probability? Similarly, for unsupervised learning and non-parametric statistics, one wishes to uncover the shape and patterns from samples of a measure or measures. We use only the intrinsic geometry and topology of the sample. A famous example of this type of method is the $k$-means clustering algorithm. A fascinating challenge is to explain the variability of behavior of $k$-means algorithms with distinct random initializations and the shapes of the clusters. In this talk we present new stochastic combinatorial theorems, direct new variations of Tverbergâs theorem, that give bounds on the probability of existence of maximum likelihood estimators in multinomial logistic regression and also quantify to the variability of clustering initializations. Along the way we will see fascinating connections to the coupon collector problem, topological data analysis, and to the computation of Tukey centerpoints of data clouds (a high-dimensional generalization of median). This is joint work with (in various papers) with T. Hogan, R. D. Oliveros, E. Jaramillo-Rodriguez, A. Torres-Hernandez, and Dominic Yang.
October 2021
Martin
Skrodzki
TU Delft
Single-sized spheres on surfaces (S4)
Abstract.
Surface representations play a major role in a variety of applications throughout a diverse collection of fields, such as biology, chemistry, physics, or architecture. From a simulation point of view, it is important to simulate the surface as good as possible, including the usage of a wide range of different approximating elements. However, when it comes to manufacturing, it is desirable to have as few different building blocks as possible, as these can then be produced cost-efficiently. The talk discusses a procedure to be used in the simulation of natural phenomena as well as within the designers' creative toolbox. It represents a surface via a collection of equally sized spheres. In the first part of the talk, we investigate mathematical challenges of the problem. These include estimating the maximal intersection area of a sphere with a surface of bounded curvature as well as counting the minimal and maximal number of spheres to be placed on a surface. Following these theoretical results, in the second part of the talk, we compare a depth-first, a breadth-first, and a heuristic algorithm for the generation of surface coverings by single-sized spheres. We prove the applicability of our algorithm by a multitude of experiments and compare our procedure to ellipsoidal and multi-sized sphere methods.
July 2021
Alexey
Garber
University of Texas Rio Grande Valley
The Voronoi conjecture: convex polytopes that tile space with translations
Abstract.
In this talk I am going to discuss a well-known connection between lattices in $\mathbb{R}^d$ and convex polytopes that tile $\mathbb{R}^d$ with translations only. My main topic will be the Voronoi conjecture, a century old conjecture which is, while stated in very simple terms, is still open in general. The conjecture states that every convex polytope that tiles $\mathbb{R}^d$ with translations can be obtained as an affine image of the Voronoi domain for some lattice. I plan to survey several known results on the Voronoi conjecture and give an insight on a recent proof of the Voronoi conjecture in the five-dimensional case. The talk is based on a joint work with Alexander Magazinov (Skoltech, Russia).
Laith
Rastanawi
FU Berlin
Towards a geometric understanding of 4-dimensional point groups
Abstract.
The 4-dimensional point groups can be roughly classified as follows. There is a finite list of polyhedral groups, which are related to the regular polytopes. There are torodial groups, which are characterized by having a torus that remains invariant. They come in several infinite families. There are axial groups, which leave a line through the origin invariant. Finally, there are eleven classes of tubular groups. We propose a new, geometric classification for the torodial groups, and we make effort to understand the action of the tubular groups in terms of orbit polytopes. Joint work with GĂŒnter Rote.
Thomas
Kahle
OvGU Magdeburg
Symmetric chains in algebra and discrete geometry
Abstract.
We describe a framework to study chains of symmetric objects from algebra (e.g. ideals) and discrete geometry (e.g. cones or monoids). Each such chain has a natural limit object in countable-dimensional space and we are interested in finite generation in the limit (which is often equivalent to stablization of the chain). While in the algebraic situation one has Noetherianity up to symmetry, that is any suitably symmetric chain stabilizes this fails for cones and monoids. Our framework yields characterizations of stabilization in terms of properties of the chain. Joint work with Dinh Van Le and Tim Römer.
June 2021
Julian
Pfeifle
UPC Barcelona
Positive PlĂŒcker Tree Certificates for Non-Realizability
Abstract.
In 2020, Hailun Zheng constructed a balanced, 2-neighborly combinatorial 3-sphere Z on 16 vertices whose graph is the complete 4-partite graph K_{4,4,4,4}. However, it was unknown whether Z is realizable as the boundary of a convex polytope. If so, Z would provide the first example of a polytope with such a graph aside from the cross-polytope. However, known techniques for proving or disproving the realizability of Z could not cope with this example. In the present talk, we level up the old idea of PlĂŒcker relations, and assemble them using integer programming into a new and more powerful structure, called 'positive PlĂŒcker trees'. They certify the non-realizability of Z and many other previously inaccessible families of simplicial spheres, such as several combinatorial prismatoids by Criado & Santos, and all centrally symmetric neighborly d-spheres recently constructed by Novik and Zheng.
Aram
Dermenjian
York University
Sign Variations and Descents
Abstract.
In this talk we consider a poset structure on projective sign vectors. We show that the order complex of this poset is partitionable and give an interpretation of the h-vector using type B descents of the type D Coxeter group.
Isabel
Hubard
UNAM
Twisted honeycombs revisited: chirality in polytope-like structures
Abstract.
In the 70ÂŽs Coxeter considered the 4-dimensional regular polytopes and used the so-called Petrie Polygons to obtain quotients of the polytopes that, while having all possible rotational symmetry, lack reflectional symmetry. He called these objects Twisted Honeycombs. Nowadays, objects with such symmetry properties are often called chiral. In this talk I will review CoxeterÂŽs twisted honeycombs and explore a natural way to extend CoxeterÂŽs work to polytope-like structures, in particular, we shall see some properties of so-called chiral skeletal polyhedra.
Martina
Juhnke-Kubitzke
U OsnabrĂŒck
On Îł-vectors for symmetric edge polytopes
Abstract.
Symmetric edge polytopes (SEP) are a class of lattice polytopes that can be constructed from a graph. Recently, their h*-vectors have been studied by several authors and it was shown that the corresponding Îł-vectors are non-negative for several classes of graphs. The goal of this talk is twofold: First, we will show that Îł2 is non-negative for any SEP and characterize those graphs for which Îł2=0. Second, we will take an asymptotic point of view and show that, for graphs with n vertices and cn edges (for some c>1), not containing any even cycle, Îłk grows as 2^k(c-1)^k/k!n^k if n is large enough. If time permits, I will also show that a similar statement (without excluding the existence of even cycles) holds with high probability if we consider graphs constructed by the probabilistic Erdös-Renyi model. This is joint work with Alessio D'AlĂ, Daniel Köhne and Lorenzo Venturello.
May 2021
Isabella
Novik
University of Washington
Many neighborly spheres
Abstract.
A simplicial complex on $n$ vertices is $s$-neighborly if it has the same $(sâ1)$-skeleton as the $(n â 1)$-simplex on the same vertex set. While a $(d-1)$-dimensional sphere with $n>d+1$ vertices cannot be more than $loor{d/2}$-neighborly, $loor{d/2}$-neighborly $(d-1)$-dimensional spheres with $n$ vertices do exist. How many such neighborly spheres are there? We will present a recent construction showing that for $d ext{â„}5$, there are at least $2^{ exts{ extOmega}(n^{loor{(d-1)/2}})}$ distinct combinatorial types of neighborly spheres. Joint work with Hailun Zheng.
Henri
MĂŒhle
TU Dresden
Refined Face Enumeration in v-Associahedra
Abstract.
Chapoton defined for each finite root system three remarkable polynomials, the F-, H- and M-triangle. The F-triangle is a refined face generating polynomial of the cluster complex, the H-triangle is a refined generating function of nonnesting partitions, and the M-triangle is a bivariate generating function of the Möbius function in the noncrossing partition lattice. He observed that these three polynomials are related by an invertible substitution of variables. These observations were proven uniformly by Athanasiadis and Thiel, respectively. In this talk, we explain how the F- and the H-triangle arise as refined versions of the f- and the h-polynomial of a polytope, and give a simple, combinatorial proof of Chapoton's relation in the context of v-associahedra. The relation with the M-triangle is much less clear. We conjecture a characterization of the northeast paths for which Chapoton's relation generalizes to this setting. Computational evidence suggests a close connection to the pureness of v-associahedra. This is based on joint work with Cesar Ceballos from TU Graz.
Sara
Faridi
Dalhousie University
Breaking up cycles in simplicial complexes and applications to subadditivity of degrees of syzygies of monomial ideals
Abstract.
The motivation for this work is finding methods to prove the subadditivity conjecture for the maximal shifts in the betti diagram of a monomial ideal. Hochster's work in the 1970's showed that the betti diagram encodes dimensions of homology modules of subcomplexes of a simplicial complex known as the Stanley-Reisner complex. In this talk we will show, using lattice complementation, how the subadditivity question can be extended to a stronger question about cycles of a simplicial complex breaking into smaller ones. We will also discuss what is known for the stronger question. This talk is based on joint work with Mayada Shahada.
April 2021
Federico
Castillo
MPI Leizig
Lineup polytopes
Abstract.
Motivated by an instance of the quantum marginal problem in physics, we define the r-lineup polytope of P as a polytope parametrizing all possible linear orders on the vertices of P. We focus on the concrete case when P is a hypersimplex. This example sits in between the sweep polytopes of A.Padrol and E.Philippe and the theory of symmetric polytopes. This is based on joint work with JP. Labbe, J.Liebert, A.Padrol, E.Philippe and C.Schilling.
Mara
Belotti
TU Berlin
Algebraic degrees of 3-dimensional polytopes
Abstract.
Results of Koebe (1936), Schramm (1992), and Springborn (2005) yield realizations of 3-polytopes with edges tangent to the unit sphere. We introduce two notions of algebraic degree for such constrained realizations and we compute them for some classes of polytopes. This is joint work with Michael Joswig and Marta Panizzut.
Alessio
D'AlĂŹ
U OsnabrĂŒck
A tale of quadratic algebras and flag simplicial complexes
Abstract.
Koszul algebras are quadratic algebras satisfying desirable homological properties and arising naturally in many geometric and combinatorial contexts: for instance, the coordinate rings of Veronese, Segre and Grassmannian varieties (in their natural embeddings) are all Koszul, and so is the Stanley-Reisner ring of any flag simplicial complex. However, the Koszul property is hard to control and to check in general, and many conjectures about the general behaviour of Koszul algebras are currently open. Starting from a flag simplicial complex Delta, we propose a construction of a (non-monomial) quadratic Gorenstein ring R_Delta which is Koszul if and only if Delta is Cohen-Macaulay, thus providing a rather unexpected bridge between these two worlds. On a more combinatorial level, the very same correspondence also yields that R_Delta has a Gröbner basis of quadrics if and only if Delta is shellable. As an application, we provide counterexamples to an algebraic generalization of a conjecture by Charney and Davis about flag homology spheres. This is joint work with Lorenzo Venturello (KTH Stockholm).
March 2021
Lena
Walter
FU Berlin
Toric Newton-Okounkov functions and polytopes
Abstract.
We initiate a combinatorial study of Newton-Okounkov functions on toric varieties with an eye on the rationality of asymptotic invariants of line bundles. In the course of our efforts we identify a combinatorial condition which ensures a controlled behavior of the appropriate Newton-Okounkov function on a toric surface. Our approach yields the rationality of many Seshadri constants that have not been settled before. This is joint work with Christian Haase and Alex KĂŒronya. In the upcoming talk I will explain the setup from a discrete geometer's point of view and how polyhedral methods can be used to study the above problem.
February 2021
Carolina
Benedetti
U de los Andes
Quotients of lattice path matroids
Abstract.
In this talk we will focus on a particular class of matroids called Lattice Path Matroids (LPMs). We will determine when a collection M_1,...,M_k of LPMs are a flag matroid, using their combinatorics. Part of our work will show that the polytope associated to such a flag can be thought as an interval in the Bruhat order, and thus provides a partial understanding of flags of LPMs from a polytopal point of view. We will not assume previous knowledge on quotients. This is joint work with Kolja Knauer.
Afshin
Goodarzi
KTH Stockholm
Mixed connectivity for cell complexes
Abstract.
The classical Steinitz's theorem (1922) asserts that a graph is the 1-skeleton of a convex 3-polytope if and only if it is 3-connected and planar. In 1961, Balinski extended the 'only if' direction of Steinitz's theorem by showing that the 1-skeleton of a convex d-polytope is d-connected. In this talk, which is based on a joint work with Anders Björner, some results that combine k-connectivity of graphs and topological k-connectivity of spaces will be presented. In particular, it will be shown that if we remove some d-k vertices (and all faces containing them) from the k-skeleton of the boundary of a convex d-dimensional polytope, then the remaining complex is topologically (k-1)-connected. This extends the result of Balinski (the k = 1 case).
Eva
Philippe
Sorbonne Université Paris
Sweep polytopes and sweep oriented matroids
Abstract.
Consider a configuration of n labeled points in a Euclidean space. Any linear functional gives an ordered partition of these points. We call it a sweep, because we can imagine its parts as the sets of points successively hit by a sweeping hyperplane. The set of all such sweeps forms a poset which is isomorphic to the face lattice of a polytope, called the sweep polytope. I will present several constructions of the sweep polytope, related to zonotopes, projections of permutahedra and monotone path polytopes of zonotopes. In a second part, I will present sweep oriented matroids, an abstract generalization of this structure in terms of oriented matroids. Besides their intrinsic interest, they also appear in connection to the Generalized Baues Problem for cellular strings of some oriented matroids beyond the realizable case.
January 2021
Margaret
Bayer
U Kansas
Lattice Polytopes from Schur Polynomials
Abstract.
Associated with a polynomial (in any number of variables) is the Newton polytope, the convex hull of the exponent vectors occurring in the polynomial. Information about Newton polytopes can shed light on families of polynomials. In this talk I report on a study of some combinatorial properties of the Newton polytopes of Schur polynomials, which enumerate certain tableaux. This work was the result of a project at the Graduate Research Workshop in Combinatorics, and is joint with Goeckner, Hong, McAllister, Olsen, Pinckney, Vega and Yip.
Anastasia
Chavez
UC Davis
Characterizing quotients of positroids
Abstract.
We characterize quotients of specific families of positroids. Positroids are a special class of representable matroids introduced by Postnikov in the study of the nonnegative part of the Grassmannian. Postnikov defined several combinatorial objects that index positroids. In this talk, we make use of one of these objects called a decorated permutation to combinatorially characterize when certain positroids form quotients. Furthermore, we conjecture a general rule for quotients among arbitrary positroids on the same ground set. This is joint work with Carolina Benedetti and Daniel Tamayo
Juan Camilo
Torres
Universidad de los Andes
An algebraic approach to projective uniqueness with an application to order polytopes
Abstract.
A polytope is said to be projectively unique if it has a single realization up to projective transformations. Projective uniqueness is a geometrically compelling property but is difficult to verify. In this talk, I will present two approaches to projective uniqueness in the literature. One is primarily geometric and is due to McMullen, who showed that certain natural operations on polytopes preserve projective uniqueness. The other is more algebraic and is due to Gouveia, Macchia, Thomas, and Wiebe. They use certain ideals associated to a polytope to verify a property called graphicality that implies projective uniqueness. I will show that McMullen's operations preserve not only projective uniqueness but also graphicality. As an application, I will show that order polytopes from finite ranked posets with no 3-antichain are graphic, and therefore projectively unique. These results were obtained in collaboration with professors Tristram Bogart and Joao Gouveia.
Sophie
Rehberg
FU Berlin
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 concepts 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.
December 2020
Jorge
Olarte
RWTH Aachen University
The tropical symplectic Grassmannian
Abstract.
Given a vector space V with a bilinear, alternating, non-degenerate form w, we call a linear subspace L isotropic if every two vectors v and u in L are orthogonal with respect to w, i.e. w(u,v) = 0. The symplectic Grassmannian SpGr(V,k) is the space of all isotropic subspaces of V of dimension k. It is a subvariety of the usual Grassmannian Gr(V,k), and its ideal is generated by the usual PlĂŒcker relations plus some additional linear relations called the symplectic relations. Our main object of study is the tropicalization of this space, the tropical symplectic Grassmannian TSpGr_p(2n,k) where 2n is the dimension of V and p is the characteristic of the field. In this talk we show when does the usual basis of SpGr(V,k) form a tropical basis. Then we will look at several examples that exhibit different pathologies, such as why the characteristic of the field makes a difference. We end the talk by proposing several research directions. This is work in progress with George Balla.
Giulia
Codenotti
Goethe-UniversitÀt Frankfurt
Beyond flatness: maximizing width of convex bodies with forbidden subpolytopes
Abstract.
Recently, Averkov, Hofscheier and Nill introduced the so-called generalized flatness constants. These generalize usual flatness by substituting hollow convex bodies with convex bodies avoiding a certain fixed subset up to a chosen class of transformations (for example unimodular transformations followed by real translations). Such convex bodies are called X-free, if X is the subset we avoid. In joint work with Hall and Hofscheier, we prove that inclusion-maximal X-free convex bodies are actually polytopes. Even in dimension 2 and with X the unimodular triangle, the family of such maximal X-free bodies is very rich and complex. However, in this case we are able to determine the flatness constants by other means. The goal of this talk is to present these results starting from basic definitions of width and flatness, and to give plenty of motivation and highlight applications of the generalized flatness constant
Deniz
Kus
Ruhr-University Bochum
Polytope parametrization of bases of representations
Abstract.
The representation theory of finite-dimensional complex Lie algebras is well-understood. There are dimension formulas, character Formulas and many parametrizations of their bases, e.g. using Young tableaux or GT pattern. The goal of this talk is to overview some known results and to present new parametrizations by convex polytopes. At the end of the talk we will discuss how these results can be extended to the representation theory of Lie superalgebras or quantum groups which is less understood
November 2020
Ilse
Fischer
U Wien
Where are the bijections? Plane Partitions and Alternating Sign Matrices
Abstract.
For about 35 years, combinatorialists have not been able to find bijections between three classes of objects that are all counted by the product formula $\prod\limits_{i=0}^{n-1} \frac{(3i+1)!}{(n+i)!}$. These objects are $n \times n$ alternating sign matrices, totally symmetric self-complementary plane partitions in a $2n \times 2n \times 2n$ box, and cyclically symmetric rhombus tilings of a hexagon of side lengths $n+2,n,n+2,n,n+2,n$ with a central hole of size $2$. Recently, we have added a fourth class of objects to this list, namely alternating sign triangles, and, even more recently, we have extended this class to alternating sign trapezoids, and have shown that they are equinumerous with cyclically symmetric rhombus tilings of a hexagon with a central hole of size $k$. At about the same time, we have constructed the first (complicated) bijection relating alternating sign matrices to cyclically symmetric rhombus tilings with a central hole of size two. In my talk, I shall tell the fascinating story of this search for explicit bijections. I will also report on joint work with Arvind Ayyer, Roger Behrend and Matjaz Konvalinka.
Hailun
Zheng
U Copenhagen
The stresses on centrally symmetric complexes
Abstract.
A simplicial complex is called centrally symmetric, or cs, if it possesses a free simplicial involution. In 1987, Stanley conjectured that if a cs Cohen-Macaulay (d-1)-dimensional simplicial complex satisfies h_i = {d choose i} for some i > 0, then h_j = {d choose j} for all j > i. More recently, a similar conjecture on the g-numbers of cs simplicial d-polytopes was proposed by Klee, Nevo, Novik and Zheng. In this talk, I will give a brief introduction to the theory of stress spaces developed by Lee. Then I will prove the above two conjectures using this machinery. This is joint work with Isabella Novik.
Daniel
Tamayo Jiménez
Université Paris-Saclay
Permutree sorting, weak order quotients, and automata
Abstract.
We define permutree sorting which generalizes the stack sorting and coxeter sorting algorithms due to Knuth and Reading respectively. Given two disjoint subsets U and D of {2,...,n}, (U, D)-permutree sorting consists of an algorithm that fails for a permutation if and only if there are integers i<j<k in [n] such that the permutation contains the subword jki (resp. kij) if j is in U (resp. in D). We present this algorithm through automata that read reduced expressions and accept only those that form a special structure within the weak order. This is joint work with Vincent Pilaud and Viviane Pons.
Viviane
Pons
Paris-Sud University
Permutrees
Abstract.
We present the construction of permutrees: a combinatorial family which includes permutations, binary trees and binary words. We show how the permutree lattices describe certain quotient of the weak order while permutreehedra are generalized permutahedron.
October 2020
Karin
Schaller
FU Berlin
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.
Matthias
Schymura
BTU Cottbus-Senftberg
Computing the covering radius of a polytope with an application to Lonely Runners
Abstract.
The covering radius of a polytope is the minimal dilation factor that is needed for the dilated polytope to cover the whole space by lattice translations. This classical parameter has versatile theoretical merits in the Geometry of Numbers, Integer Programming, the Classification of Lattice Polytopes, and Cryptography. However, given your favorite polytope it's a hard task to compute its covering radius. The only prior algorithm is due to Kannan (1992), but it is hardly implementable and has a time complexity that involves a double exponentiation of the input. We develop an easily implementable and more efficient procedure based on the concept and structure of so-called last-covered points. In the talk I will explain the main ideas behind the algorithm and its analysis. I also discuss our initial motivation drawn from a variant of the Lonely Runner Conjecture, which can be formulated as the problem of bounding the covering radius of certain lattice zonotopes. This is based on joint work with Jana Csolvjecsek, Romanos Malikiosis, and MĂĄrton NaszĂłdi.
Hannah
Markwig
U TĂŒbingen
Curve counting and tropical geometry
Abstract.
The talk introduces tropical geometry as a tool for enumerative geometry. In enumerative geometry, we study counts of curves satisfying certain conditions. Particularly, we consider generating series for important enumerative invariants. Some of them appear in the context of mirror symmetry and can be related to Feynman integrals. This can be used to study their properties such as quasimodularity.
July 2020
Sophia
Elia
FU Berlin
and
Marie
Brandenburg
FU Berlin
Multivariate volume, Ehrhart and h*-polynomials of polytropes
Abstract.
In this talk we discuss polytropes, tropical polytopes that are also classically convex, and their related polynomials, taking time to review all necessary background material. We describe methods stemming from algebraic geometry and Ehrhart theory for computing multivariate versions of volume, Ehrhart, and h*-polynomials of lattice polytropes. Finally, we touch on the combinatorics of the coefficients of the volume polynomials.
Florian
Kohl
Aalto University
Unconditional Reflexive Polytopes
Abstract.
A convex body is unconditional if it is symmetric with respect to reflections in all coordinate hyperplanes. In this talk, we investigate unconditional lattice polytopes with respect to geometric, combinatorial, and algebraic properties. In particular, we characterize unconditional reflexive polytopes in terms of perfect graphs. As a prime example, we study a type-B analogue of the Birkhoff polytope. This talk is based on joint work with McCabe Olsen and Raman Sanyal.
JĂŒrgen
Herzog
UniversitÀt Duisburg-Essen
Sortable sets and sortable simplicial complexes
Abstract.
Sortable sets of monomials is a concept which was introduced by Bernd Sturmfels. Toric algebras whose monomial generators are sortable have the nice property that their defining toric ideal has a quadratic Gröbner basis and squarefree initial ideal, and this has remarkable consequences for the toric algebra and also for the ideal generated by this sortable set of monomials. We will also introduce sortable simplicial complexes and show that the proper interval graphs are precisely the graphs whose independence complex is sortable. My lecture is based on joint papers with my coauthors Viviana Ene, Takayuki Hibi, Fahimeh Khosh-Ahang, Somayeh Moradi, Masoomeh Rahmbeigi, Marius Vladoiu, Ayesha Asloob Qureshi and Guangjun Zhu.
Laura
Escobar
Washington University in St. Louis
Wall-crossing phenomena for Newton-Okounkov bodies
Abstract.
A Newton-Okounkov body is a convex set associated to a projective variety, equipped with a valuation. These bodies generalize the theory of Newton polytopes. Work of Kaveh-Manon gives an explicit link between tropical geometry and Newton-Okounkov bodies. We use this link to describe a wall-crossing phenomenon for Newton-Okounkov bodies. This is joint work with Megumi Harada.
June 2020
Sebastian
Manecke
Goethe-UniversitÀt Frankfurt
Inscribable fans, zonotopes, and reflection arrangements
Abstract.
Steiner posed the question if any 3-dimensional polytope had a realization with vertices on a sphere. Steinitz constructed the first counter example and Rivin gave a complete resolution. In dimensions 4 and up, Mnev's universality theorem renders the question for inscribable combinatorial types hopeless. However, for a given complete fan F, we can decide in polynomial time if there is an inscribed polytope with normal fan F. Linear hyperplane arrangements can be realized as normal fans via zonotopes. It turns out that inscribed zonotopes are rare and in this talk I will focus on the question of classifying the corresponding arrangements. This relates to localizatons and restrictions of reflection arrangements and GrĂŒnbaum's quest for simplicial arrangements. The talk is based on joint work with Raman Sanyal.
Kaie
Kubjas
Aalto University
Log-concave density estimation and polytopes
Abstract.
In this talk, we study probability density functions that are log-concave. The log-concave maximum likelihood estimation involves tent functions, regular subdivisions and Samworth bodies, which are continuous analogues of duals of secondary polytopes. This goal of this talk is to introduce the connections between log-concave density estimation and discrete geometry. All necessary background from statistics will be given in the talk.
BĂŒĆra
Sert
TU Berlin
A study on the chamber complex
Abstract.
The notion of chamber (Minkowski cone, type cone) of a polytope has had an important role in several theories, such as Minkowski decomposition, the vector partition function, etc (McMullen, Emiris et al., Henk et al., Brion et al., Strumfels, Beck and others). While the chamber of a polytope P gives us the cone of vectors that change the half-space arrangement of P without changing its normal fan, we are interested in finding all different normal fans we can obtain by moving a given set of half-spaces. In this talk, we present the chamber complex of a matrix, which gives us the collection of all chambers we can obtain from it. Moreover, we describe an algorithm to compute it. This is joint work with Zafeirakis Zafeirakopoulos.
José
Samper
MPI MiS Leipzig
How to complete matroids.
Abstract.
The goal of this talk is to present the big picture of one of my favorite problems: matroids enjoy several properties that are ideal to be studied with techniques from polyhedral geometry and combinatorial topology, but applying those techniques typically take us out of the realm of matroid theory. I am interested in the minimal class of additional objects needed to apply the toolkits freely. Prominent examples of this phenomenon include the universal valuation theorem of Derksen and Fink, or the matroid flip technique of Adiprasito, Huh and Katz. I will discuss many flavors of this phenomenon, including some new ones I have stumbled upon recently and try to compare them. Along the way I will present many open questions that aim to understand them better. The talk will include some parts of my work with Federico Castillo, Jeremy Martin and Alex Heaton.
May 2020
Lei
Xue
University of Washington
A Proof of GrĂŒnbaum's Lower Bound Conjecture for general polytopes
Abstract.
In 1967, GrĂŒnbaum conjectured that any $d$-dimensional polytope with $d+s\leq 2d$ vertices has at least \[\phi_k(d+s,d) = {d+1 \choose k+1 }+{d \choose k+1 }-{d+1-s \choose k+1 } \] $k$-faces. In the talk we will discuss the proof of this conjecture and also also characterize the cases in which equality holds.
Sara
Lamboglia
Goethe-UniversitÀt Frankfurt
Tropical convex hulls of polyhedral sets
Abstract.
In this talk I will present some recent results on the interplay between tropical and classical convexity. In particular, I will focus on the tropical convex hull of convex sets and fans and their explicit computation. This will lead to a lower bound on the degree of tropical fan curves and to a description of tropically convex cones. This is joint ongoing work with Cvetelina Hill and Faye Pasley Simon.
Luis
Ferroni Rivetti
Uni. Bologna
The Ehrhart Polynomial of some Matroid Polytopes
Abstract.
In this seminar we will talk about the Ehrhart Theory of the polytopes of two interesting families of matroids: uniform matroids and minimal matroids. They provide two important examples of infinite families of matroids which support a Conjecture posed by De Loera et al, regarding the positivity of the coefficients of the Ehrhart polynomials of matroid polytopes. We will also discuss how the Ehrhart positivity of minimal matroids is related with the operation of circuit-hyperplane relaxation of a matroid, and we will make brief analysis of the Ehrhart polynomial as a matroid invariant.
April 2020
Max
Hlavacek
UC Berkeley
Subdivisions of Shellable Complexes
Abstract.
Combinatorialists often ask whether certain polynomials are real rooted; today we focus on h-polynomials, which encode the number of faces of cell complexes. When proving that a polynomial is real-rooted, we often rely on the theory of interlacing polynomials and their recursive nature. In this paper, we relate the recursive nature of interlacing polynomials to the recursive structure, typically termed 'shellability', of cell complexes. In this talk, we describe how these ideas can be used to positively answer a question posed first by Brenti and Welker, and then again by Mohammadi and Welker, on whether the h-polynomial of the barycentric subdivision of a cubical polytope is real rooted. We then briefly describe other subdivisions of shellable complexes in which these techniques apply.
Jonathan
Spreer
Univ. Sydney
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.
Hannah
Sjöberg
FU Berlin
Do alcoved polytopes have unimodal h*-vectors?
Abstract.
Unimodal sequences are widely studied in combinatorics. They can for example show up as a result of some algebraic properties of the underlying object. The h-vectors of simplicial complexes and the Ehrhart h*-vectors of lattice polytopes are examples for sequences that are often studied for unimodality. We will look at a certain class of lattice polytopes, alcoved polytopes and describe some conditions under which their h*-vectors are unimodal.
Matt
Beck
FU Berlin / San Francisco State Uni.
The Arithmetic of Coxeter Permutahedra
Abstract.
Ehrhart theory measures a polytope P discretely by counting the number of lattice points inside its dilates P, 2P, 3P, ... We compute the Ehrhart quasipolynomials of the standard Coxeter permutahedra for the classical Coxeter groups. A central tool is a description of the Ehrhart theory of a rational translate of an integer zonotope.
February 2020
Thomas
Yahl
Texas A&M Univ.
Solving decomposable sparse systems
Abstract.
Solutions to polynomial systems lying in a family can be identified with fibres of a branched cover. A branched cover decomposables if it factors on an open set through nontrivial branched covers. This structure can be exploited to numerically compute solutions via homotopy continuation methods. This leads to an algorithm for numerically solving systems lying in a family by completely factoring the associated branched cover. We study this in the case of sparse polynomial systems, where these decompositions can be explicitly described and their fibres can be computed as solutions to simpler polynomial systems.
Pamela
Harris
Williams College
Recent results on Kostantâs partition function
Abstract.
In this talk we introduce Kostantâs partition function which counts the number of ways to represent a particular weight (vector) as a nonnegative integral sum of positive roots of a Lie algebra. We provide two fundamental uses for this function. The first is associated with the computation of weight multiplicities in finite-dimensional irreducible representations of classical Lie algebras, and the second is in the computation of volumes of flow polytopes. We provide some recent results in the representation theory setting, and state a direction of ongoing research related to the computation of the volume of a flow polytope associated to a Caracol diagram.
Andres
Vindas Melendez
Univ. of Kentucky
Equivariant Volumes of the Permutahedron
Abstract.
Motivated by the generalization of Ehrhart theory with group actions, this project is the prequel to the equivariant Ehrhart theory of the permutahedron (which Mariel spoke about in December). The fixed polytopes of the permutahedron are the polytopes that are fixed by acting on the permutahedron by a permutation. We prove some general results about the fixed polytopes/slices. In particular, we compute their dimension, show that they are combinatorially equivalent to permutahedra, provide hyperplane and vertex descriptions, and prove that they are zonotopes. Lastly, we obtain a formula for the volume of these fixed slices, which is a generalization of Richard Stanley's result of the volume for the standard permutahedron. This is joint work with Federico Ardila (San Francisco State Unviersity) and Anna Schindler (North Seattle College).
Katharina
Jochemko
KTH Stockholm
Generalized permutahedra: Minkowski linear functionals and Ehrhart positivity
Abstract.
Generalized permutahedra form a combinatorially rich class of polytopes that naturally appear in many areas of mathematics such as combinatorics, geometry, optimization and statistics. They comprise many important classes of polytopes, for example, matroid polytopes. We study functions on generalized permutahedra that behave linearly with respect to dilation and taking Minkowski sums. We give a complete classification of all positive, translation-invariant Minkowski linear functionals on permutahedra that are invariant under permutations of the coordinates: they form a simplicial cone and we explicitly describe the generators. We apply our results to prove that the linear coefficients of Ehrhart polynomials of generalized permutahedra are nonnegative, verifying conjectures of De Loera-Haws-Koeppe (2009) and Castillo-Liu (2018) in this case. This is joint work with Mohan Ravichandran.
January 2020
Elise
Walker
Texas A&M Univ.
Toric degenerations and homotopy methods from finite Khovanskii bases
Abstract.
Homotopies are useful numerical methods for solving systems of polynomial equations. Embedded toric degenerations are one source for homotopy algorithms. In particular, if a projective variety has a toric degeneration, then linear sections of that variety can be optimally computed using the polyhedral homotopy. Any variety whose coordinate ring has a finite Khovanskii basis is known to have a toric degeneration. We provide embeddings for this Khovanskii toric degeneration to compute general linear sections of the variety. This is joint work with Michael Burr and Frank Sottile.
Jean-Philippe
Labbé
AG Diskrete Geometrie
Combinatorial Foundations for Geometric Realizations of Subword Complexes of Coxeter Groups
Abstract.
Let d>=1 and C be a simplicial complex homeomorphic to a (d-1)-dimensional sphere. "Is there a d-dimensional simplicial convex polytope P whose face lattice is isomorphic to that of C?" This is a classical problem in discrete geometry going back to Steinitz who proved that every 2-dimensional simplicial sphere is the boundary of a polytope. The determination of the polytopality of subword complexes is a resisting instance of Steinitz's problem. Indeed, since their introduction more than 15 years ago, subword complexes built up a wide portfolio of relations and applications to many other areas of research (Schubert varieties, cluster algebras, associahedra, tropical Grassmannians, to name a few) and a lot of efforts has been put into realizing them as polytopes, with relatively little success. In this talk, I will present some reasons why this problem resisted so far, and present a glimpse of a novel approach to study the problem grouping together Schur functions, combinatorics of words, and oriented matroids.
Johannes
Hofscheier
Nottingham
Generalised flatness constants, spanning lattice polytopes, and the Gromov width
Abstract.
In this talk, I will present joint work with Averkov and Nill where we motivate some new directions of research regarding the lattice width of convex bodies. Based on the conclusion that convex bodies of large width contain a unimodular copy of a standard simplex, we will discuss relations to recent results on spanning lattice polytopes and how this can be viewed as the beginning of the study of generalised flatness constants. We will conclude the talk by outlining connections between the lattice width of a Delzant polytope and the Gromov width of its associated toric symplectic manifold. No prior knowledge to symplectic geometry is assumed.
Joseph
Doolittle
FU Berlin
Non-Inscribable 4-polytopes
Abstract.
Following work of Chen and Padrol, and many others, we studied the question of which polytopes can be inscribed, realized with all vertices on a sphere. We focused on dual-to-cyclic polytopes, and found a nearly complete characterization of when these polytopes are indescribable. The obstruction to inscribability used comes from classical plane geometry, Miquel's 5 circle theorem. We further found the first example of an f-vector for which every polytope with that f-vector cannot be inscribed. In this talk, we will explain the methods and insights leading to these results, which include algebraic geometry, linear algebra, combinatorics, and plane geometry. This is joint work with Jean-Philippe LabbĂ©, Carsten Lange, Rainer Sinn, Jonathan Spreer, and GĂŒnter M. Ziegler.
December 2019
Mariel
Supina
FU Berlin
/
UC Berkeley
Equivariant Ehrhart Theory of the Permutahedron
Abstract.
Ehrhart theory is a topic in geometric combinatorics which involves counting the lattice points inside of lattice polytopes. Stapledon (2010) introduced equivariant Ehrhart theory, which combines discrete geometry, combinatorics, and representation theory to give a generalization of Ehrhart theory that accounts for the symmetries of polytopes. In this talk, I will discuss joint work with Ardila and Vindas-Meléndez (2019) on answering one of Stapledon's open questions: determining the equivariant Ehrhart theory for the permutahedron, and verifying his Effectiveness Conjecture in this special case.
Irem
Portakal
Univ. Magdeburg
Kazhdan-Lusztig varieties with a view towards T-varieties
Abstract.
Lee and Masuda investigate the closure of the usual torus orbit in Schubert variety X_w in full flag variety. The maximal cones of the associated normal fan of this toric variety are encoded by permutations smaller than w (in Bruhat sense). It turns out that these cones are edge cones of certain directed graphs. On the other hand, Kazhdan and Lusztig prove a relation between Kazhdan-Lusztig varieties and affine neighborhoods of torus fixed points in the Schubert variety X_w. In this talk, we aim to bring these two results together in order to investigate the usual torus action on Kazhdan-Lusztig varieties using directed graphs. This is an ongoing-project with Donten-Bury and Escobar-Vega.
November 2019
Zuzka
PatĂĄkovĂĄ
IUUK
Around Radon's theorem
Abstract.
Radonâs theorem is one of the cornerstones of convex geometry. It implies many of the key results in the area such as Hellyâs theorem and, as recently shown by Andreas Holmsen and Dong-Gyu Lee, also its more robust version, fractional Hellyâs theorem together with a colorful strengthening of Hellyâs theorem. Consequently, this yields an existence of weak epsilon nets and a (p,q)-theorem. We show that we can obtain these results even without assuming convexity, replacing it with very weak topological conditions. Moreover, using a recent result we have obtained together with Gil Kalai, we show that, under the weak topological conditions, the fractional Helly number for open sets in the plane or on a surface is reasonably small. Special case of this result settles a conjecture of Andreas Holmsen, Minki Kim, and Seunghun Lee about an existence of a (p,q)-theorem for open subsets of a surface.
Camille
Combe
Univ. Strasbourg
Cubic realizations of Tamari interval lattices
Abstract.
We introduce cubic coordinates, which are integer words encoding intervals in the Tamari lattices. Cubic coordinates are in bijection with interval-posets, themselves known to be in bijection with Tamari intervals. We will see that in each degree the set of cubic coordinates forms a lattice, isomorphic to the lattice of Tamari intervals. Geometric realizations are naturally obtained by placing cubic coordinates in space, highlighting some of their properties. We will present the cellular structure of these realizations. Finally, we will see a proof generalizing the result of Björner and Wachs about the EL-shellability of Tamari posets for Tamari interval posets.
Takayuki
Hibi
Osaka Univ.
Gorenstein polytopes
Abstract.
A Gorenstein polytope is a lattice polytope one of whose dilated polytopes is a reflexive polytope. In my talk, after reviewing Gorenstein polytopes from a viewpoint of enumeration of lattice points, the conjecture that every (0, 1)-polytope is a face of a Gorenstein (0, 1)-polytope will be discussed. No special knowledge will be required to understand my talk.
Miruna-Stefana
Sorea
Leipzig
The shapes of level curves of real polynomials near strict local minima
Abstract.
We consider a real bivariate polynomial function vanishing at the origin and exhibiting a strict local minimum at this point. We work in a neighbourhood of the origin in which the non-zero level curves of this function are smooth Jordan curves. Whenever the origin is a Morse critical point, the sufficiently small levels become boundaries of convex disks. Otherwise, these level curves may fail to be convex. The aim of this talk is two-fold. Firstly, to study a combinatorial object measuring this non-convexity; it is a planar rooted tree. And secondly, we want to characterise all possible topological types of these objects. To this end, we construct a family of polynomial functions with non-Morse strict local minima realising a large class of such trees.
October 2019
Amy
Wiebe
FU Berlin
Realization Spaces 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). I will also show how the relationship of the slack model to the classical models can be used to improve computational efficiency of the slack model.
Liam
Solus
MPI-Leipzig
s-derangement polynomials and some conjectures on lattice polytopes
Abstract.
A thriving industry in combinatorics centers around the investigation of distributional properties of combinatorial generating polynomials such as unimodality and log-concavity. In the context of lattice polytopes, one of the now longest standing conjectures pertaining to this general problem asserts that the (Ehrhart) h^*-polynomial of a reflexive and IDP lattice polytope is unimodal. In 2013, Schepers and Van Langenhoven put forth a series of questions that propose new methods for attacking this conjecture as based on a classic theorem of Betke and McMullen. In this talk, we will introduce a family of combinatorial generating polynomials, called s-derangement polynomials, that allow us to positively answer these questions and conjectures for some well-studied lattice polytopes. Key to these results is the fact that the s-derangement polynomials generalize the classical derangement polynomial in such a way that it inherits many of its desirable properties, including real-rootedness, symmetry, log-concavity, gamma-positivity, and unimodality. This talk is based on joint work with Nils Gustafsson.
August 2019
Basudeb
Datta
Indian Institute of Science
Stacked and tight triangulations of manifolds
Abstract.
Walkup constructed a class of triangulated d-manifolds from a stacked d-sphere by adding successive handles. Now, we know that Walkup's class of manifolds are same as the class of stacked manifolds. (A stacked triangulated manifold is the boundary of triangulated manifold whose co-dimension 2 spaces are on the boundary.) Tight triangulated manifolds are generalisations of neighbourly triangulations of closed surfaces and are interesting objects in Combinatorial Topology. Tight triangulated manifolds are conjectured to be minimal. A triangulation of a closed 2-manifold is tight (with respect to a field F) if and only if it is F-orientable and neighbourly. Recently, it is shown that a triangulation of a closed 3-manifold is tight (with respect to a field F) if and only if it is F-orientable, neighbourly and stacked. Thus every tight triangulation of closed 3-manifold is strongly minimal. Except few, all the known tight triangulated manifolds are stacked. From some recent works, we know more on tight triangulations. In this talk, we present a survey on the works done on stacked and tight triangulation.
July 2019
Madeline
Brandt
Berkeley/Leipzig
Matroids and their Dressians
Abstract.
In this talk we will explore Dressians of matroids. Dressians have many lives: they parametrize tropical linear spaces, their points induce regular matroid subdivisions of the matroid polytope, they parametrize valuations of a given matroid, and they are a tropical prevariety formed from certain PlĂŒcker equations. We show that initial matroids correspond to cells in regular matroid subdivisions of matroid polytopes, and we characterize matroids that do not admit any proper matroid subdivisions. An efficient algorithm for computing Dressians is presented, and its implementation is applied to a range of interesting matroids. If time permits, we will also discuss an ongoing project extending these ideas to flag matroids.
Federico
Castillo
University of Kansas
Deformations of Coxeter permutahedra and Coxeter submodular functions
Abstract.
One way to decompose a polytope is to represent it as a Minkowski of two other polytopes. These smaller pieces are naturally called summands. Starting from a polytope we want to explore the set of all summands. This set can be parametrized by a polyhedral cone, called deformation cone, in a suitable real vector space. We focus on the case where the starting polytope is a Coxeter permutahedron, which is a polytope naturally associated with a root system. This generalizes the type A case which correspond to generalized permutohedra. This is joint work with Federico Ardila, Chris Eur, and Alexander Postnikov.
Rekha
Thomas
Univ. Washington
Geometry and Algebra in Optimization
Abstract.
While optimization is a well established field with myriad tools, the use of algebraic methods to tackle optimization problems, beyond those from linear algebra, is relatively new. Algebraic models inherently bring in geometry via the language of algebraic geometry, which studies solutions to polynomial equations and inequalities. Convexity enters naturally as well since optimizing a linear function over a set is the same as optimizing the function over its convex hull. In this talk I will illustrate a sequence of ideas and results that use polynomials to tackle a variety of optimization problems. On the theoretical side, this will touch on theta bodies, lifts of convex sets, tightness of relaxations, and the use of symmetries. If there is extra time, I will talk about some applications to computer vision and combinatorics.
June 2019
Jose
Samper
MPI Leipzig
Slicing matroid polytopes
Abstract.
We introduce the notion of a matroid threshold hypergraph: a set system obtained by slicing a matroid basis polytope and keeping the bases on one side. These hypergraphs can be then used to define a class of objects that slightly extends matroids and has a few new technical advantages. For example, it is amenable to several inductive procedures that are out of reach to matroid theory. In this talk we will motivate the study of these families of hypergraphs, relate it to some old open questions and pose some new conjectures. To conclude we will show that the study of these objects helps us find a link between the geometry of the normal fan of the matroid polytope and shellability invariants/activities of independence complexes.
Giulia
Codenotti
FU Berlin
The covering minima of lattice polytopes
Abstract.
The covering minima of a convex body were introduced by Kannan and Lovasz to give a better bound in the flatness theorem, which states that lattice point free convex bodies cannot have arbitrarily large width. These minima are similar in flavor to Minkowski's successive minima, and on the other hand generalize the covering radius of a convex body. I will speak about recent joint work with Francisco Santos and Matthias Schymura, where we investigate extremal values of these covering minima for lattice polytopes.
Cesar
Ceballos
Univ. Wien
The s-weak order and s-permutahedra
Abstract.
The classical weak order on permutations and the permutahedron are well studied objects in algebraic and geometric combinatorics. In this talk, I will present a generalization of these objects, indexed by a sequence of non-negative integers s. The s-permutahedron has a beautiful geometric structure which is conjectured to be realizable as the polyhedral complex induced by a polytopal subdivision of a polytope. We will present a solution to this conjecture in dimensions 2 and 3, discuss some of its combinatorial properties, and present some connections to the v-Tamari lattices of Préville-Ratelle and Viennot. This is joint work with Viviane Pons.
May 2019
Davide
Bolognini
Univ. Bologna
Betti splitting from a topological point of view
Abstract.
Betti splitting is a Mayer-Vietoris like technique to recover the minimal graded free resolution of homogeneous ideals. In this seminar, I will present a topological version of this technique, in the context of simplicial complexes. As an application, I will show some results establishing that the existence of a particular kind of Betti splitting for a triangulation of a closed manifold can express nice topological properties of the underlying space. Several interesting examples will be given. This is a joint work with Ulderico Fugacci.
Volkmar
Welker
Philipps-Univ. Marburg
Higher dimensional connectivity versus minimal degree of random graphs and minimal free resolutions
Abstract.
We study the clique complex, i.e. simplices are subsets of the vertex sets that form a complete subgraph of a random graph sampled from the ErdĆs-Renyi model. Motivated by applications in the study of minimal free resolutions of the Stanley-Reisner ring of the clique complex, we study for iâ„0 two invariants: the minimal number of vertices that have to be deleted such that the clique complex of the remaining graph has homology in dimension i; and the minimal number of vertices that have to be deleted such that an i-simplex in the clique complex has empty link. Random graph theory says that the two invariants coincide for i=0 and all (ErdĆs-Renyi) probability regimes. We show the same for a middle density regime in case i=1, one inequality for all i and conjecture equality in general.
Michael
Cuntz
Univ. Hannover
Classification of Weyl groupoids
Abstract.
Finite Weyl groupoids (these are certain simplicial arrangements in a lattice) were completely classified in a series of papers by Heckenberger and myself. However, this classification is based on two computer proofs checking millions of cases. In this talk, I want to report on recent progress in finding a shorter proof. In particular, we prove without using a computer that, up to equivalence, there are only finitely many irreducible finite Weyl groupoids in each rank greater than two.
Alexandru
Constantinescu
FU Berlin
DISCRETE STRUCTURES ON THE CONE OF MINKOWSKI SUMMANDS
Abstract.
The possibilities of splitting a lattice polytope into a Minkowski sum of lattice polytopes reflect the deformation theory of the induced toric singularity. This was proved by Altmann in 1996. Our goal is to reveal a similar correspondence for arbitrary polytopes. To this aim we look at special diagrams of semigroups and define a lattice structure inside the cone of Minkowki summands.
April 2019
Giulia
Codenotti
FU Berlin
The covering minima of lattice polytopes
Abstract.
The covering minima of a convex body were introduced by Kannan and Lovasz to give a better bound in the flatness theorem, which states that lattice point free convex bodies cannot have arbitrarily large width. These minima are similar in flavor to Minkowski's successive minima, and on the other hand generalize the covering radius of a convex body. I will speak about recent joint work with Francisco Santos and Matthias Schymura, where we investigate extremal values of these covering minima for lattice polytopes.
Vincent
Delecroix
LaBRI/MPI Bonn
Dirichlet domain computation for real hyperbolic groups
Abstract.
A real hyperbolic group of dimension d is a discrete subgroup of SO(1,d) (the special orthogonal group of a quadratic form of signature (1,d) seen as the isometry group of the real hyperbolic space of dimension d). The main studied cases are d=2,3 which are the so-called Fuchsian and Kleinian groups. In various situations, one has access to generators of a real hyperbolic group and would like to study its properties (e.g. find relations among the generators). A possible approach for this problem is the construction of a fundamental domain with respect to its action on the hyperbolic space. The Dirichlet fundamental domain is a systematic way to construct one. After introducing the problem, I will provide several motivating examples. Then, I will discuss the algorithmic part which involves the incidence geometry of polyhedral cones.
Kenny
Chiu
FU Berlin
The Number of Convex Polyominoes with Given Height and Width
Abstract.
We give a new combinatorial proof for the number of convex polyominoes whose minimum enclosing rectangle has given dimensions. We also count the subclass of these polyominoes that contain the lower left corner of the enclosing rectangle (directed polyominoes). In addition, we indicate how to sample random polyominoes in these classes.
February 2019
Lorenzo
Venturello
OsnabrĂŒck
Algebraic invariants of balanced simplicial complexes
Abstract.
Given a simplicial complex which triangulates a certain manifold it is natural to ask what conditions the topology poses on the number of faces in each dimension. Via the Stanley-Reisner correspondence between simplicial complexes and squarefree monomial ideals we can take advantage of tools from commutative algebra, by studying related algebraic invariants such as the Hilbert function and the graded Betti numbers of a certain graded ring. In particular we focus on balanced simplicial complexes, i.e., (d â 1)-dimensional complexes whose graph is d-colorable. After providing the necessary background we will present upper bounds on graded Betti numbers of various objects in this family and discuss possible applications to face enumeration. This is joint work with Martina Juhnke-Kubitzke.
Karin
Schaller
FU Berlin
Stringy Invariants of Algebraic Varieties and Lattice Polytopes
Abstract.
We present topological invariants in the singular setting for projective Q-Gorenstein varieties with at worst log-terminal singularities, such as stringy Euler numbers, stringy Chern classes, stringy Hodge numbers, and stringy E-functions. In the toric setting, we give formulae to efficiently compute these stringy invariants. Using these combinatorial expressions and the stringy Libgober-Wood identity, we derive several appealing new combinatorial identities for lattice polytopes. We go on to generalise the famous ânumber 12â and ânumber 24â identities which hold far more generally than previously expected.
January 2019
Carsten
Lange
FU Berlin
Some volume identities for $W$-permutahedra
Abstract.
Lovasz (2001) constructed a weighted adjacency matrix $A_G$ for the vertex-edge-graph of a given $3$-polytope $P$ containing the origin such that a basis of its kernel yields vertices for $P$ up to a linear transformation. In 2010, Izmestiev extended the construction to polytopes of arbitrary dimension. We study Izmestievâs construction for generalized $W$-permutahedra $P_W$ were $W$ denotes a finite reflection group. This yields an interesting relation between volumes of faces of the dual polytope $P_W^\Delta$ and the volume of simplices spanned by vertices of $P_W$. Joint works with Ioannis Ivrissimtzis, Shiping Liu and Norbert Peyerimhoff.
Kristin
Shaw
Oslo
Lena
Walter
FU
The Kingman Coalescent as a Density on a Space of Trees
Abstract.
Randomly pick n individuals from a population and trace their genealogy backwards in time until you reach the most recent common ancestor. The Kingman n-coalescent is a probabilistic model for the tree one obtains this way. The common definitions are stated from a stochastic point of view. The Kingman Coalescent can also be described by a probability density function on a space of certain trees. For the space of phylogenetic trees Ardila and Klivans showed, that this space is closely related to the Bergman fan of the graphical matroid of the complete graph. Using its fine fan structure, similar things can be said about the space we are considering. I will describe the density and report on work in progress with Christian Haase about relations of population genetics and polyhedral and algebraic geometry.
Jorge Alberto
Olarte Parra
FU Berlin
The moduli space of Harnack curves
Abstract.
Harnack curves are a special family of plane real algebraic curves which are characterized by having amoebas that behave in the simplest possible way. Given a lattice polygon, we will show how to compute the moduli space of Harnack curves which have that polygon as Newton polygon. This space can be embedded into the moduli space of pointed tropical curves. Through this embedding, the moduli space of Harnack curves has a compactification which essentially is the secondary polytope of the Newton polygon. We show how in this compactification lattice subdivisions of the Newton polygon correspond to collections of Harnack curves that can be glued together using Viroâs patchworking.
Thomas
Kahle
OVGU Magdeburg
The geometry of gaussoids
Abstract.
Gaussoids are combinatorial structures that encode independence in probability and statistics, just like matroids encode independence in linear algebra. We show that the gaussoid axioms of Lnenicka and Matus are equivalent to compatibility with certain quadratic relations among principal and almost-principal minors of a symmetric matrix. This approach facilitates insights into symmetry and realizability of gaussoids as well as several extensions (like oriented, positive, and valuated gaussoids). (based on joint work with T. Boege, A. D'Ali, and B. Sturmfels)
December 2018
Laura
Colmenarejo
MPI Leipzig
Signatures of paths: an algebraic perspective.
Abstract.
Coming from stochastic analysis, the signature of a path is the collection of all the iterated integrals of the path. It can be seen in terms of tensors or as formal power series in words, which make them more relevant in other areas such as algebraic geometry or combinatorics. In this talk, I would like to look at the signatures of paths from an algebra perspective. For that, we will look at the work done by C. Améndola, P. Friz, and B. Sturmfels about the variety defined by the signature of piecewise linear paths, as well as the work done by F. Galuppi about the variety of rough paths. As a continuation, I would like to present our work no the variety defined by the signature of axis paths. This is a joint work with F. Galuppi and M. Michalek.
Michael
Joswig
TU Berlin
Cluster partitions and fitness landscapes of the Drosophila fly microbiome
Abstract.
Beerenwinkel et al.(2007) suggested studying fitness landscapes via regular subdivisions of convex polytopes. Building on their approach we propose cluster partitions and cluster filtrations of fitness landscapes as a new mathematical tool. In this way, we provide a concise combinatorial way of processing metric information from epistatic interactions. Using existing Drosophila microbiome data, we demonstrate similarities with and differences to the previous approach. As one outcome we locate interesting epistatic information where the previous approach is less conclusive. Joint works with Holger Eble, Lisa Lamberti and Will Ludington.
Antonio
Macchia
FU Berlin
Binomial edge ideals of bipartite graphs
Abstract.
Binomial edge ideals are ideals generated by binomials corresponding to the edges of a graph. They generalize the ideals of 2-minors of a generic matrix with two rows and arise naturally 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.
November 2018
Daniel
Ciripol
Jena
Computing Convex Hulls of Trajectories
Abstract.
Motivated by the problem of designing chemical reactors we study convex hulls of trajectories generated by polynomial dynamical systems. Real algebraic curves constitute a special case. We numerically determine whether the convex hull of such a curve is forward closed. That is, if the dynamics started from any point within the hull generate trajectories remaining inside the convex hull. To this end, we compute polyhedral approximations of the convex hull. We give results on the limiting behavior of those approximations. From the polyhedral approximations we derive information about stratified families of faces on the boundary of the convex hull. These stratifications help to partition the boundary into regions of inward and outward pointing dynamics. Experiments have been conducted for dimensions up to 4.
Andrew
Newman
TU Berlin
The integer homology threshold in random simplicial complexes
Abstract.
A classic result of ErdĆs and RĂ©nyi is that the connectivity threshold in their random graph model is at (log n)/n. That is if one samples a graph G from the model G(n, p) with p less than (log n)/n then almost certainly G is disconnected, while p > (log n)/n implies that G almost certainly is connected. As graph connectivity is a homological property, it generalizes nicely to higher-dimensional simplicial complexes as homological connectivity, the vanishing of all homology groups in positive codimension. As such, the threshold for homological connectivity has been studied in the Linial--Meshulam model of random simplicial complexes. A paper of Meshulam and Wallach from 2006 develops the cocycle counting technique to establish the threshold for homological connectivity over a fixed finite field for random simplicial complexes. However, the question of homological connectivity over the integers remained open. In this talk I will give an overview of the Linial--Meshulam model and then discuss joint work with Elliot Paquette to adapt the cocycle counting technique to establish the threshold for homological connectivity over the integers.
Marta
Panizzut
TU Berlin
Local Dressians Of Matroids
Abstract.
The tropical Grassmannian is a rational polyhedral fan parametrizing realizable (d â 1)-dimensional tropical linear spaces in the tropical projective space TP^(nâ1). These are contractible polyhedral complexes arising from the tropicalization of (d â 1)-dimensional linear spaces in the projective space P^(nâ1). Herrmann, Jensen, Joswig and Sturmfels introduced the Dressian Dr(d, n), an outer approximation of the tropical Grassmannian which parametrizes all (d â 1)-dimensional tropical linear spaces in TP^(nâ1). Moreover, they remarked that a stratification based on matroids can be described on the Dressian, motivating a definition of local Dressian Dr(M) of a matroid M. Dressians and local Dressian will be the main characters of the talk. After introducing the main concepts, I will focus on the two fan structures that these objects are endowed with: one coming from the PlĂŒcker relations, and one as a subfan of the secondary fan of the matroid polytope. Generalizing a result of Herrmann et al., I will show that the two fan structures coincide. The proof is based on a careful analysis of the subdivisions induced on the 3-dimensional skeleton of the matroid polytope. This is a joint work with Jorge Alberto Olarte and Benjamin Schröter.
Alex
Fink
Queen Mary University, London
The Tutte polynomial via lattice point enumeration
Abstract.
I will explain how to recover the Tutte polynomial of a matroid from an Ehrhart-style polynomial which counts lattice points in Minkowski sums of simplices and its base polytope. The key ingredient is a polyhedral interpretation of activity; along the way, this will give us a regular subdivision whose cells naturally encode Dawson's activity partition. I will also talk about its generalisation to polymatroids: in this setting, finding a bivariate activity invariant was a question of TamĂĄs KĂĄlmĂĄn, who constructed the univariate activity invariant in his work on enumerating spanning trees of hypergraphs. This work is joint with Amanda Cameron (Eindhoven).
October 2018
Gaku
Liu
MPI Leipzig
Cubical Pachner moves and cobordisms of immersion
Abstract.
We study various analogues of theorems from PL topology for cubical complexes. In particular, we characterize when two PL homeomorphic cubulations are equivalent by Pachner moves by showing the question to be equivalent to the existence of cobordisms between immersions of hypersurfaces. This solves a question and conjecture of Habegger and Funar. The main tool is a theorem to show that any cubical PL decomposition of a disk is regular after some cubical stellar subdivision; this extends a result of Morelli. Joint work with Karim Adiprasito.
Felipe
RincĂłn
University of Oslo
September 2018
Raman
Sanyal
Goethe-UniversitÀt Frankfurt
Cone Angles, Gram's relation, and zonotopes
Abstract.
Eulerâs Polyhedron Formula and its generalization, the Euler-Poincare formula, is a cornerstone of the combinatorial theory of polytopes. It states that the number of faces of various dimensions of a convex polytope satisfy a linear relation and it is the only linear relation (up to scaling). Similarly, Gramâs relation generalizes the fact that the sum of (interior) angles at the vertices of a convex $n$-gon is $(n-2)Ï$. In dimensions $3$ and up it is possible to associate an angle to faces of all dimensions and summing angles over faces of fixed dimension gives rise to the interior angle vectors of polytopes. Gramâs relation is the unique linear relation (up to scaling) satisfied by the angle vectors of polytopes. Interestingly, Gramâs relation is independent of the notion of angle. To make this precise, we will consider generalizations of âanglesâ in the form of cone valuations. It turns out that the associated generalized angle vectors still satisfy Gramâs relation and, surprisingly, it is the only linear relation, independent of the underlying cone valuation! Behind the scenes a beautiful interplay of discrete geometry and algebraic combinatorics is at work that we will try to explain, starting from the beginning. This is joint work with Spencer Backman and Sebastian Manecke.
July 2018
Francisco
Criado
TU Berlin
The Hirsch conjecture for simplicial spheres
Abstract.
We introduce topological prismatoids, a combinatorial abstraction of the (geometric) prismatoids used in the recent counter-examples to the Hirsch Conjecture. We show that the "strong d-step Theorem" that allows to construct non-Hirsch polytopes from prismatoids of large width still works at this combinatorial level. Then, using metaheuristic methods on the flip graph, we construct four combinatorially different "non-d-step" 4-dimensional topological prismatoids with 14 vertices. This implies the existence of 8- dimensional spheres with 18 vertices which do not satisfy the Hirsch bound, which is smaller that the previously known examples by Mani and Walkup (24 vertices, dimension 11). Our non-Hirsch spheres are shellable but we do not know whether they are polytopal.
Akihiro
Higashitani
Kyoto Sangyo University
Finding a new universal condition in Ehrhart theory
Abstract.
Recently, Balletti and I proved that for the h^*-polynomial h_0^*+h_1^*t+... of a lattice polytope, if we assume h_3^*=0, then (h_1^*, h_2^*) satisfies (i) h_2^*=0; or (ii) h_1^* (iii) (h_1^*,h_2^*)=(7,1). These conditions derive from Scott's theorem (1976), who characterized the possible h^*-polynomials of 2-dimensional lattice polytopes, and Scott's theorem is also essentially valid for lattice polytopes with degree at most 2 (Treutlein (2010)). On the other hand, we proved that it also holds under the assumption h_3^*=0. Since the assumption h_3^*=0 is independent of both dimension and degree of polytopes, we call the conditions (i), (ii), (iii) universal. In this talk, towards finding a new universal condition, we investigate the possibility for the polynomial h_0^*+h_1^*t+... to be the h^*-polynomial of some lattice polytope under the assumption that some of h_i^*'s vanish.
June 2018
Giulia
Codenotti
FU Berlin
Separation-type combinatorial invariants for triangulations of manifolds
Abstract.
In this talk, I propose a combinatorial invariant defined for simplicial complexes as an alternative way to obtain lower bounds on the size of triangulations of manifolds. The advantage of this approach lies within its simplicity: the invariants under investigation are defined by counting connected components and/or homological features of subcomplexes. As an application I obtain a linear identity for triangulated 4-manifolds with a fixed f-vector, unifying previously known lower bounds on the number of faces needed to triangulate a) simply connected 4-manifolds, and b) 4-manifolds of type 'boundary of a handlebody'. Moreover, based on the same construction, I present a conjectured upper bound for 4-manifolds with prescribed vector of Betti-numbers. This talk is based on joint work with Francisco Santos and Jonathan Spreer.
May 2018
Francisco
Santos
Universidad de Cantabria
A Polyhedral Method for Sparse Systems with many Positive Solutions
Abstract.
We investigate a version of Viro's method for constructing polynomial systems with many positive solutions, based on regular triangulations of the Newton polytope of the system. The number of positive solutions obtained with our method is governed by the size of the largest positively decorable subcomplex of the triangulation. Here, positive decorability is a property that we introduce and which is dual to being a subcomplex of some regular triangulation. Using this duality, we produce large positively decorable subcomplexes of the boundary complexes of cyclic polytopes. As a byproduct we get new lower bounds for the maximal number of positive solutions of polynomial systems with prescribed numbers of monomials and variables. We also study the asymptotics of these numbers and observe a log-concavity property. This talk is based on joint work with Frédéric Bihan and Pierre-Jean Spaenlehauer.
Christian
Stump
TU Berlin
Counting inversions and descents of random elements in finite Coxeter groups
Abstract.
In this talk I will report on Mahonian and Eulerian probability distributions given by inversions and descents in general finite Coxeter groups. I will provide uniform formulas for the mean values and variances in terms of Coxeter group data in both cases. I will also provide uniform formulas for the double-Eulerian probability distribution of the sum of descents and inverse descents. I will finally establish necessary and sufficient conditions for general sequences of Coxeter groups of increasing rank for which Mahonian and Eulerian probability distributions satisfy central and local limit theorems. This talk is based on joint work with Thomas Kahle.
Nevena
PaliÄ
FU Berlin
Grassmann polytopes and amplituhedra
Abstract.
The amplituhedra arise as images of the totally nonnegative Grassmannians by projections that are induced by linear maps. They were introduced in Physics by Arkani-Hamed & Trnka (Journal of High Energy Physics, 2014) as model spaces that should provide a better understanding of the scattering amplitudes of quantum field theories. The topology of the amplituhedra has been known only in a few special cases, where they turned out to be homeomorphic to balls. The amplituhedra are special cases of Grassmann polytopes introduced by Lam (Current developments in mathematics 2014, Int. Press). In this talk I will present results from the paper *Some more amplituhedra are contractible*, which is a joint work with Pavle V.M. BlagojeviÄ, Pavel Galashin and GĂŒnter M. Ziegler, and in which we show that some further amplituhedra are homeomorphic to balls, and that some more Grassmann polytopes and amplituhedra are contractible.
Jonathan
Kliem
FU Berlin
Discretizing Measure Partition Results
Abstract.
In this talk I will explain how to discretize convex measure partition results. It is a common approach to model colored points in R^d by measures. From measure partition results, e.g. the Ham Sandwich Theorem, one likes to obtain results on convex partitions of colored points. This progress has been inefficient so that even equipartition results could not be transferred except for trivial cases. A recent paper by BlagojeviÄ, Rote, Steinmeyer, and Ziegler uses a Network Flow to simultaneously equipartition d colors in R^d. I will show how this method can be generalized. This talk is based on joint work with Pavle V. M. BlagojeviÄ, Nevena PaliÄ, Johanna K. Steinmeyer, and GĂŒnter M. Ziegler.
April 2018
Louis
Billera
Cornell Univ.
Unbalanced collections and Farkas complexes
Abstract.
We will define and discuss unbalanced collections (PSS systems of Björner) both from the perspective of posets (the order complex of each such collection) and complexes (the simplicial complex of all such collections). In the first case, they are all shellable balls with the same f-vector. In the second, they form a homotopy sphere. The latter leads to a general construction of something we call the Farkas complex of an arrangement of hyperplanes or oriented matroid. The first perspective is due to Anders Björner; the second represents ongoing joint work with Florian Frick. A few examples of other Farkas complexes will be examined, including a family of complexes considered by Klee and Novik. Farkas complexes come complete with a description of their âmissingâ faces, leading to a way of describing their face rings.
March 2018
Amy
Wiebe
University of Washington
Slack Ideals of Polytopes
Abstract.
In this talk we discuss a new tool for studying the realization spaces of polytopes, namely the slack ideal associated to the polytope. These ideals were first introduced to study PSD rank of polytopes, and their structure also encodes other important polytopal properties, gives us a new way to understand important concepts such as projective uniqueness, and suggests connections with the study of other algebraic and combinatorial objects (toric ideals and graphs, for example).
February 2018
Anna Maria
Hartkopf
FU Berlin
Gustavo
Jasso
Univ. Bonn
Triangulations of cyclic polytopes and simplicial combinatorics
Abstract.
Motivated by applications in higher category theory, Dyckerhoff and Kapranov introduced the notion of a d-Segal set in 2012. These are a class of simplicial sets satisfying a property defined in terms of triangulations of d-dimensional cyclic polytopes. In this talk I will give an elementary introduction to d-Segal sets and relate them to the combinatorics of outer horns, which are specific simplicial subsets of the standard simplices. This is part of joint work in progress with Tobias Dyckerhoff (Bonn).
Martin
Skrodzki
FU Berlin
Combinatorial and Asymptotical Results on the Neighborhood Grid
Abstract.
In 2009, Joselli et al introduced the Neighborhood Grid data structure for fast computation of neighborhood estimates in point clouds. Even though the data structure has been used in several applications and shown to be practically relevant, it is theoretically not yet well understood. The purpose of this talk is to present a polynomial-time algorithm to build the data structure. Furthermore, it is investigated whether the presented algorithm is optimal. This investigations leads to several combinatorial questions for which partial results are given. The talk follows our current ArXiv paper: https://arxiv.org/abs/1710.03435
Matthias
Schymura
FU Berlin
Some remarks on the reverse isodiametric problem
Abstract.
Motivated by an old question of Makai Jr. on the thinnest non-separable arrangement of convex bodies, we study a reverse form of the classical isodiametric inequality. More precisely, we are interested in estimating the maximal isodiametric quotient that an affine image of a given convex body can have. After an early solution of Behrend (1937) in the plane, the problem seemed to be forgotten and is open starting from three dimensions. In the talk, we shall first explain the connection to densities of non-separable arrangements, and then illustrate how concepts such as Löwner-position, well-distributed point configurations on the sphere, and measures of orthogonality of orthonormal matrices naturally appear in this context. As a result we obtain the currently best asymptotic solution to the reverse isodiametric problem. Joint (ongoing) work with Bernardo Gonzålez Merino.
January 2018
Mario
Kummer
MPI Leipzig/TU Berlin
Interlacing Ehrhart Polynomials of Reflexive Polytopes
Abstract.
The symmetric edge polytope is a lattice polytope associated to a graph. The Ehrhart polynomial of a symmetric edge polytope often has a remarkable property: All their roots have real part -1/2. One of the first positive results was the case of complete (1,n)-bipartite graphs proved independently by Kirschenhofer et al. and by Bump et al in the context of analytic number theory. We prove several conjectures confirming that certain families of polynomials have real part -1/2. The main ingredient is the theory of interlacing polynomials.
Gaku
Liu
MPI Leipzig
A counterexample to the extension space conjecture for realizable oriented matroids
Abstract.
The extension space conjecture of oriented matroid theory states that the space of all one-element, non-loop, non-coloop extensions of a realizable oriented matroid of rank $d$ has the homotopy type of a sphere of dimension $d-1$. We disprove this conjecture by showing the existence of a realizable uniform oriented matroid of high rank and corank 3 with disconnected extension space. The talk will not assume any prior knowledge of oriented matroids.
Moritz
Firsching
FU Berlin
The classification of polytopal 3-spheres with 9 vertices into polytopes and nonpolytopes
Abstract.
Altshuler and Steinberg classified all 1336 types of 3-dimensional polytopal spheres with 8 vertices into 1294 combinatorial types of 4-dimensional polytopes with 8 vertices and 42 non-polytopal spheres. We examine how an analogues classification of 3-dimensional polytopal spheres can be obtained in order to answer the question: 'How many combinatorial types of 4-dimensional polytopes with 9 vertices exists?'. We also discuss if rational coordinates can be given for those types.
December 2017
Henri
MĂŒhle
TU Dresden
The Alternating Group and Noncrossing Partitions
Abstract.
We consider the alternating group generated by the set of all three-cycles. By orienting the corresponding Cayley graph 'away from the identity', we obtain a natural partial order on the alternating group. It turns out that this partial order is in fact a subword order, in which every interval admits a braid group action on its set of maximal chains, the Hurwitz action. The purpose of this talk is to study this poset from an enumerative and a structural point of view. We outline how noncrossing partitions enter the picture, and how they help us to produce beautiful formulas. Moreover, we enumerate orbits under Hurwitz action. If time permits, we present further generalizations of this construction. This is joint work with Philippe Nadeau.
November 2017
Thomas
Torsney-Weir
UniversitÀt Wien
Slicing multi-dimensional spaces
Abstract.
I will discuss our work with Torsten Möller on investigating methods of visualizing multi-dimensional spaces using interactive one and two dimensional slices. Visualizing multi-dimensional spaces on a two-dimensional screen can be done either by projection or slicing the space. In medical visualization often shows axial, medial, and sagittal slices of a volume around a particular focus point (location in the body). Slices directly visualize an object and it is easy to measure distances in the horizontal and vertical directions. I will show how we addressed the issue of picking a focus point. In addition, I will show a number of examples including comparing regression models, function spaces, and regular polygons.
Rainer
Sinn
FU Berlin
Matrix completion problems from a geometric point of view
Abstract.
We will see several matrix completion problems for matrices with real entries and discuss questions that are specific to the case of real entries from a geometric point of view. I will present answers for special families of examples based on joint work with Daniel Bernstein and Greg Blekherman.
Afshin
Goodarzi
FU Berlin
Face numbers of shellable nonpure complexes
Abstract.
The f-triangle of a simplicial complex is an integer array whose entries determine the number of faces of complexes with a given dimension and co-dimension. The f-triangle is a finer invariant than the ordinary f-vector. If the simplicial complex is pure (all the maximal faces have the same dimension), then the f-triangle encodes the same information as the f-vector. In this talk, we discuss a numerical characterization of the f-triangles of shellable non-pure complexes. This result generalizes the classical Macaulay-Stanley theorem to the nonpure case. (This talk is based on a joint work with K. Adiprasito and A. Björner.)
Jorge Alberto
Olarte
FU Berlin
Pure flag simplicial complexes and the ErdĆs-Ko-Rado-property
Abstract.
We launch the thorough study of the pure ErdĆs-Ko-Rado property of simplicial complexes. Specifically, we identify two fundamental conditions on the maximal faces of a pure simplicial complex to satisfy the ErdĆs-Ko-Rado property, namely flagness and the absence of boundary ridges. We establish a tower of increasingly ambitious conjectures stating, in the most general form, that these properties are sufficient to establish the pure-EKR property in arbitrary dimension. We then prove this conjecture in dimensions two and three. This is joint work with Paco Santos, Jonathan Spreer and Christian Stump
October 2017
Robert
Löwe
TU Berlin
Secondary fans and secondary polyhedra of punctured Riemann surfaces
Abstract.
A famous construction of Gelfand, Kapranov and Zelevinsky associates to each finite point configuration A subset R^d a polyhedral fan, which stratifies the space of weight vectors by the combinatorial types of regular subdivisions of A. That fan arises as the normal fan of a convex polytope. In a completely analogous way we associate to each hyperbolic Riemann surface R with punctures a polyhedral fan. Its cones correspond to the ideal cell decompositions of R that occur as the horocyclic Delaunay decompositions which arise via the convex hull construction of Epstein and Penner. Similar to the classical case, this secondary fan of R turns out to be the normal fan of a convex polyhedron, the secondary polyhedron of R.
September 2017
Stephan
Tillmann
University of Sydney
Computing trisections of 4âmanifolds
Abstract.
Gay and Kirby recently generalised Heegaard splittings of 3-manifolds to trisections of 4-manifolds. A trisection describes a 4-dimensional manifold as a union of three -dimensional handlebodies. The complexity of the 4-manifold is captured in a collection of curves on a surface, which guide the gluing of the handelbodies. After defining trisections and giving key examples and applications, I will describe an algorithm to compute trisections of 4-manifolds using arbitrary triangulations as input. This results in the first explicit complexity bounds for the trisection genus of a 4âmanifold in terms of the number of pentachora (4-simplices) in a triangulation. This is joint work with Mark Bell, Joel Hass and Hyam Rubinstein.
July 2017
Katy
Beeler
FU Berlin
Polytopes with few coordinate values
Abstract.
(0,1)-polytopes are defined by their vertex coordinates taking values 0 or 1. In this talk we will present two generalizations of (0,1)-polytopes called (0,1,a)- and (0,1,a_i)-polytopes. Interesting examples of these polytopes arise already in dimension three, with combinatorial types that cannot be realized as rational polytopes. We will discuss the enumeration in lower dimensions that produced these examples and then examine the tractability of a classification in higher dimensions. We will also discuss various combinatorial properties of these polytopes.
June 2017
Jean-Philippe
Labbé
FU Berlin
Some bounds on the number of faces of flag homology spheres (joint work with Eran Nevo)
Abstract.
In this talk, we discuss enumerative and structural properties of certain simplicial complexes called 'flag homology spheres'. A simplicial complex Î, it is called 'flag' when it is equal to its clique complex, and Î is an 'homology sphere' when the link of every face in Î has the homology of a sphere (over some field). The study of f-vectors of flag homology spheres (or their better suited Îł-vectors) is motivated by the g-conjecture, and the Charney--Davis conjecture, which asserts the non-negativity of a certain linear combination of the entries of the f-vector. We present bounds on some entries of the Îł-vector supporting a conjecture of Nevo--Petersen. The techniques used give two further results 1) relating f-vector of flag balanced simplicial complexes and Îł-vectors of flag homology spheres, and 2) an analog to Perles' Theorem on k-skeleta of flag homology spheres. This is joint work with Eran Nevo (Hebrew University of Jerusalem).
Arnau
Padrol
Paris 6
Extension complexity of polytopes with few vertices (or facets)
Abstract.
The number of combinatorial types of d-polytopes with up to d+4 vertices (or facets) grows superexponentially with d. However, only quadratically many can have realizations with extension complexity smaller than d+4; that is, arise as a linear projection of a higher-dimensional polytope with less than d+4 facets. These are easy to classify into finitely many families and the exact extension complexity of each realization is easy to decide. The classification involves (generalized) Gale transforms and an upper bound on the number of polytopes with few vertices and facets.
Florian
Frick
Cornell University
Geometry and Combinatorics of Fair Division
Abstract.
Sperner's lemma is a combinatorial version of Brouwer's fixed point theorem and states that if the vertices of a triangulation of an n-simplex are colored by n+1 colors following certain simple rules, then there is a face of the triangulation that exhibits all n+1 colors on its vertices. This talk focuses on extensions of Sperner's lemma and related results and applications to problems of fair division. In particular, this approach yields an algorithm for how to fairly divide rent such that n frugal roommates with subjective preferences will not be envious of each other even if the preferences of one roommate are unknown. This is joint work with Megumi Asada, Kelsey Houston-Edwards, Frédéric Meunier, Vivek Pisharody, Maxwell Polevy, David Stoner, Ling Hei Tsang, and Zoe Wellner.
Jonathan
Spreer
FU Berlin
Combinatorial invariants, tightness, and a lower bound for triangulated 3-manifolds
Abstract.
In 1987, Kalai proved that stacked spheres of dimension at least three are characterised by the fact that they attain equality in Barnette's celebrated Lower Bound Theorem. This result does not extend to dimension two. In this talk, I will present a characterisation of stacked 2-spheres using what is called the separation index. This characterisation of stacked 2-spheres is then applied to settle the 3-dimensional case of a conjecture by Lutz, Sulanke and Swartz stating that 'tight-neighborly triangulated manifolds are tight' -- essentially by reproving a lower bound for triangulated 3-manifolds. This is joint work with Benjamin Burton, Basudeb Datta, and Nitin Singh.
May 2017
Marta
Panizzut
TU Berlin
Linear Systems on Graphs
Abstract.
Baker and Norine introduced a combinatorial theory of linear systems on graphs in analogy with the one on algebraic curves. The interplay between the theories is given by specialization of linear systems from curves to dual graphs of degenarations. As shown by Baker, through specialization the rank of a linear system can only increase. In this talk I will present results on linear systems on complete graphs and complete bipartite graphs. This is based on an ongoing project with Filip Cools (KU Leuven) and Michele DâAdderio (ULB).
Jacinta
Torres
MPI Leipzig
April 2017
Nevena
Palic
FU Berlin
Introduction to the oriented matroid Grassmannian
Abstract.
Oriented matroid Grassmannian, also called MacPhersonian, is a combinatorial analogue of the real Grassmannian. It was introduced in early 90's by MacPherson and it was firstly used by Gelfand and MacPherson to give a combinatorial formula for Pontrjagin classes. Since then, there were attempts to understand the MacPhersonian, but still not much is known about its topology. The main open question remains, whether the MacPhersonian and the Grassmannian are homotopy equivalent. In this talk I will define the oriented matroid Grassmannian and look into some of its properties. It will be easy to understand and the questions from the audience are welcome.
Francisco
Santos Leal
Universidad de Cantabria
Classification of empty 4-simplices, part 2
Abstract.
This talk is related to the one I gave in February in this same seminar, but it will be self-contained and largely non-overlapping with part 1. I will report on joint work (partially in progress) with O. Iglesias and M. Blanco, aimed at completing the full classification of empty 4-simplices. An empty simplex is a lattice d-polytope with no other lattice point than its d+1 vertices. They are the âbuilding-blocksâ of lattice polytopes, in the sense that every lattice polytope can be triangulated into empty simplices, and they are also important in algebraic geometry since they correspond to the âterminal singularitiesâ that arise in minimal model programs. The complete classification of empty 3-simplices was done by White (1964), but in dimension 4 only partial results were known so far. Our approach relies on the recent complete classification of lattice hollow 3-polytopes by Averkov, Krumpelmann and Weltge and follows the following scheme: 1) empty 4-simplices of width 1 form a 3-parameter family quite easy to classify, Ă la White. (To relate this to what follows, observe that these empty 4-simplices are the ones that project to a hollow 1-polytope Q, the unit segment). 2) empty 4-simplices of width at least three are finitely many and we have classified them completely by proving an explicit upper bound of 5058 for their (normalized) volume and by enumerating all empty 4-simplices up to that bound. There are 179 of width three and a single one of width four. 3) empty 4-simplices of width two come in three types: 3.1) Those that project to a hollow 2-polytope Q. Since Q itself must have width at least two, it must be the second dilation of a unimodular triangle. We show that empty 4-simplices projecting to it form two 2-parameter families. 3.2) Those that project to a hollow 3-polytope Q, but not to a hollow 2-polytope. We show that, apart of finitely many exceptions for P (with volume bounded by 100) Q is necessarily a triangular bipyramid. Looking at the AKW classification we find out that there are exactly 52 possibilities for Q. Each of them corresponds to an infinite 1-parameter family of hollow 4-simplices, which contains either none or infinitely many empty 4-simplices. We are working on deciding which is the case for each of them (current status is 3 produce none, 38 produce infinitely many, and 11 are still open). 3.3) Those that do not project to a hollow 3-polytope. These are finitely many and we are trying to classify them along the same lines of case (2), except our current volume bounds are not good enough to certify that we have a complete classification. As a by-product, we confirm the classification of âstable quintuplesâ conjectured by Mori, Morrison and Morrison (1989) and proved by Bober (2009). In our language, these quintuples correspond to the infinite families of empty 4-simplices that project to a *primitive* lower dimensional hollow polytope Q (meaning that vertices of Q integer-affinely span the lattice). These include the 3-parameter family of case (1), one of the two 2-parameter families of case (3.1), and 29 of the 52 1-parameter families of case (3.2). The other 1 + 23 families have to be considered new ânon-primitive stable quintuplesâ.
March 2017
Lauri
Loiskekoski
FU Berlin
Separation in the graph of a simple polytope
Abstract.
Separation in graphs is related to graphs being expanders. A conjecture by Kalai generalizes the planar separation theorem to simple polytopes. It states that the graph of a simple d-polytope can be separated to two roughly equal parts by removing O(n^((d-2)/(d-1))) vertices. We provide a counterexample to this conjecture. This is joint work with GĂŒnter Ziegler.
Jean-Philippe
Labbé
FU Berlin
Computing with Polytopes -- Progress Report
Abstract.
This seminar is going to give an overview of the progress made during the 2 weeks long Sage Days workshop in Olot (Spain) on softwares involving polyhedral computations: LattE, normaliz, polymake, Sage, etc.
February 2017
Florian
Kohl
FU Berlin
Francisco
Santos
Classification of empty 4-simplices
Abstract.
An empty simplex is a lattice $d$-polytope with no other lattice point than its $d+1$ vertices. In this talk I will explain what is known about empty 4-simplices. In particular, I will comment on three proofs of the fact that all but finitely many (equivalence classes of) empty 4-simplices have width at most two: - the nice (but incomplete) proof by Barile, Bernardi, Borisov, and Kantor ('On empty lattice simplices in dimension 4.', Proc. Am. Math. Soc. 139, 2011, 4247-4253). - the proof by Blanco, Haase, Hofmann, and Santos (arXiv:1607.00798) - the proof by Santos and Iglesias (in preparation, a poster was presented in http://www.mi.fu-berlin.de/en/math/groups/tubdiscmath/Events/Lattice_Poly_Workshop/index.html#Posters)
GĂŒnter M.
Ziegler
FU Berlin
January 2017
Romanos
Malikiosis
TU Berlin
Theodosios
Douvropoulos
University of Minnesota
Lyashko-Looijenga morphisms and geometric factorizations of a Coxeter element
Abstract.
A common theme in Combinatorics is an unconditional love for the symmetric group. We like to investigate structural and numerological properties of various objects associated with it. It often happens that such objects and phenomena can be generalized to the other (complex) reflection groups as well. This is the world of Coxeter Combinatorics. A problem that goes back to Hurwitz and the 19th century is to enumerate (reduced) factorizations of the long cycle (12..n)â Snâ into factors from prescribed conjugacy classes. In the reflection groups case, it corresponds to enumerating factorizations of a Coxeter element. Bessis gave a beautiful geometric interpretation of such factorizations by using a variant of the Lyashko-Looijenga (LL) map, a finite morphism coming from Singularity theory. We extend some of Bessis' and Ripoll's work and use the LL map to enumerate the so called "primitive factorizations" of a Coxeter element c. That is, factorizations of the form c=wâ t1⯠tkâ, where wâ belongs to a prescribed conjugacy class and the tiâ's are reflections.
Evan
DeCorte
McGill University, Canada
The spectral method for geometric colouring problems
Abstract.
Consider the graph H(d) whose vertex set is the hyperbolic plane, where we join two points with an edge when their distance is equal to d. Asking for the chromatic number of this graph is the hyperbolic analogue to the famous Hadwiger-Nelson problem. One has the lower bound of 4 for all d>0, as in the Euclidean case. Using spectral methods, we prove that with the additional requirement that the colour classes be measurable, one needs at least 6 colours to properly colour H(d) when d is sufficiently large. This is joint work with Konstantin Golubev. Weâll begin the talk by discussing a few problems about the chromatic number and measurable chromatic number of geometric distance graphs, with the aim of surveying the spectral method.
Peter
BĂŒrgisser
TU Berlin
Towards a probabilistic Schubert calculus
Abstract.
Hermann Schubert developed in the 19th century a calculus for answering enumerative questions in algebraic geometry, e.g., 'How many lines intersect four curves of degrees d_1,...,d_4 in three-dimensional space in general position?'. In his 15th problem, Hilberts asked for a rigorous foundation of Schubert's enumerative calculus, which led to important progress in algebraic geometry and topology (intersection theory of the Grassmannians). However, Schubert calculus only yields the typical number of complex solutions. Is there a meaningful way to speak about the typical number of REAL solutions? We shall outline a way to do so, by assuming that the given objects (the four curves in the above example) are randomly rotated and to inquire about the expected number of real solutions. The approach blends ideas from real algebraic geometry with integral geometry and the theory of random polytopes. (Joint work with Antonio Lerario.)
December 2016
Afshin
Goodarzi
FU Berlin
On codimension embedding of simplicial complexes
Abstract.
It is known since before 1930 that a d-dimensional simplicial complex is embeddable into the Euclidean (2d+1)-space. In his 1932 article, van Kampen showed that this result is the best possible, by presenting d-dimensional complexes that do not embed into the Euclidean (2d)-space. The major question concerning embeddings of the complexes is: 'Given a d-dimensional simplicial complex X and an integer k between d and 2d. When does X embed in the Euclidean k-space?'. The cases when k=2d or k=d+1 are probably the most intensively investigated cases: - When k=2d (and d is different from 2), the problem is decidable. Actually, there exists an algorithm based on van Kampen's ideas that solve this problem in a polynomial time. - When k=d+1 and d>3, the problem is not even algorithmically decidable. This was shown by Matousek, Tancer and Wagner in 2009 using a significant result of Novikov on sphere recognition. In this talk, which is based on a work with Anders Björner, we give a homological obstruction to codimension one embedding, i.e. k=d+1 case. Some combinatorial corollaries in low dimensions will be presented.
Michael
Harrison
Penn State University
An h-principle for totally skew embeddings
Abstract.
An embedding f : M \to \R^n is called totally skew if for every pair of distinct points x,y \in M, the tangent spaces at f(x) and f(y) neither intersect nor contain parallel directions. Following Ghomi and Tabachnikov, we ask: Given a manifold M, what is the smallest dimension n(M) such that M admits a totally skew embedding into \R^n? The answer is known in only three cases: n(\R)=3, n(\R^2) = 6, and n(S^1)=4. In their investigation, Ghomi and Tabachnikov established a deep relationship between totally skew embeddings and the generalized vector field problem, as well as to immersions and embeddings of real projective spaces. We give a brief overview of their work and discuss our recent progress on the existence problem for totally skew embeddings, which is based on an h-principle technique due to Gromov and Eliashberg.
November 2016
Timo
de Wolff
Texas A&M
A New Approach to Nonnegativity and Polynomial Optimization
Abstract.
Deciding nonnegativity of real polynomials is a fundamental problem in real algebraic geometry and polynomial optimization. Since this problem is NP-hard, one is interested in finding sufficient conditions (certificates) for nonnegativity, which are easier to check. Since the 19th century, the standard certificates for nonnegativity are sums of squares (SOS). In practice, SOS based semidefinite programming (SDP) is the standard method to solve polynomial optimization problems. In 2014, Iliman and I introduced an entirely new nonnegativity certificate based on sums of nonnegative circuit polynomials (SONC), which are independent of sums of squares. We successfully applied SONCs to global nonnegativity problems. Recently, Dressler, Iliman, and I proved a Positivstellensatz for SONCs, which provides a converging hierarchy of lower bounds for constrained polynomial optimization problems. These bounds can be computed efficiently via relative entropy programming. This result establishes SONCs as a promising alternative to SOS based SDP methods. In this talk I will give an overview about sums of nonnegative circuit polynomials, their relation to combinatorics and optimization, and outline my future research program.
Rainer
Sinn
Geometry of Sums of Squares
Abstract.
I will present recent results on the geometry of sums of squares on projective algebraic sets. A central theme will be the ranks of extreme points of spectrahedra, which are affine linear slices of the cone of positive semidefinite symmetric matrices. These spectrahedra arise naturally in real algebraic geometry in the context of sums of squares. Of special interest will be projective varieties of small degree and subspace arrangements. We will see that the latter case translates into the positive semidefinite matrix completion problem.
October 2016
GĂŒnter
Rote
Selecting K points with the largest convex hull area
Abstract.
We are given a set S of n points in three dimensions and an integer K. We are looking for a subset of at most K points whose convex hull has the largest possible volume. We show that this problem is W[1]-hard, by reduction from the so-called Grid Tiling problem. This implies, under the standard complexity-theoretic assumption that W[1] is not equal to FPT, that the problem cannot be solved in f(K)n^C time, for any function f and any constant C. In other words, the problem is not fixed-parameter tractable. For the related problem of selecting K points that maximize the dominated volume in the nonnegative orthant, we could show NP-hardness by a reduction from independent set in planar graphs of maximum degree 3. The problems are motivated by the task of reducing a large set of options to a small "representative" set. These results are joint work with Kevin Buchin, Karl Bringmann, Sergio Cabello, and Michael Emmerich.
September 2016
Christian
Krattenthaler
Uni Wien
Robinson-Schensted-Knuth correspondence, jeu de taquin, and growth diagrams
Abstract.
I shall review the classical Robinson-Schensted correspondence - a classical bijection between permutations and pairs of standard Young tableaux of the same shape - and then explain that there is a modern, 'better' way the present the same bijection in terms of Sergey Fomin's growth diagrams. These ideas are then put into action by establishing a recent conjecture of Sophie Burrill on a certain bijective relation between standard tableaux and oscillating tableaux.
July 2016
Moritz
Schmitt
On the Number of Facets of a Monohedral Tile
Abstract.
A family of proper convex bodies is a (convex) tiling if the bodies cover space completely and have disjoint interiors. The tiling is monohedral if the bodies are pairwise congruent. Every body in such a tiling has to be polytopal, and determining the least upper bound on the number of facets is a major open problem. We give an overview of known upper bounds for special classes of monohedral tilings, survey a few classical results, and present recent constructions of lower bounds.
Raman
Sanyal
FU Berlin
Tight upper bounds on colorful simplicial depth and Minkowski sums
Abstract.
The colorful simplicial depth of a collection of d+1 finite sets of points in Euclidean d-space is the number of choices of a point from each set such that the origin is contained in their convex hull. This is an extension of the notion of 'simplicial depth' to the colorful situation. If the origin is contained in all color classes, then Barany's beautiful colored version of Carathéodory's theorem asserts that the colorful depth is at least 1. Deza, Huang, Stephen, Terlaky (2006) conjectured lower and upper bounds on the colorful depth and, after many partial results, the lower bound conjecture was confirmed by Sarrabezolles (2015). Recently, we managed to prove the conjectured upper bound. For that we cast the problem into one of combinatorial topology and the goal of the talk is to give a sketch of our proof. We also discovered an interesting connection between colorful configurations and Minkowski sums of polytopes. If time permits, I will give the idea and show how this resolves a conjecture of Burton (2003) in the theory of normal surfaces. This is joint work with Adiprasito, Brinkmann, Padrol, Patak, and Patakova.
Anton
Dochtermann
U Texas
Syzygies of generalized permutohedra, with combinatorial applications
Abstract.
The lattice points of a generalized permutohedra P, when viewed as a Minkowski sum/difference of simplices, naturally define a monomial ideal I_P. This class of ideals includes matroidal ideals and certain artinian ideals generalizing powers of the maximal ideal. We employ techniques from tropical geometry to show that if P is a positive sum of simplices, then any regular fine mixed subdivision of P supports a minimal resolution of I_P. This basic observation leads to applications in a variety of contexts, including ladder determinantal ideals, h-vectors of cographical matroids, and chip-firing on graphs. For the case of arbitrary P we obtain nonminimal resolutions in certain cases (eg for matroid polytopes). We'll survey some of these connections, with an emphasis on the combinatorial/geometric aspects. Joint work, some in progress, with Raman Sanyal and Alex Fink.
June 2016
Spencer
Backman
Hausdorff Center Bonn
Riemann-Roch theory for graph orientations and the Tutte polynomial
Abstract.
Chip-firing is a certain simple game played on the vertices of a graph. In 2007, Baker and Norine proved that by utilizing chip-firing, one may prove a Riemann-Roch formula for graphs analogous to the classical statement for algebraic curves. I will describe a certain equivalence relation on partial graph orientations which captures chip-firing and explain how this setup allows for a more conceptual combinatorial understanding of Baker and Norine's result. I will then outline how such considerations of partial graph orientations led myself, Sam Hopkins, and Lorenzo Traldi to a new 12 variable expansion of the Tutte polynomial of a graph. Time permitting, I will describe some applications of this new Tutte expansion in algebraic and geometric combinatorics.
Arnau
Padrol
Tropical Catalan Subdivisions
Abstract.
We revisit the associahedral subdivision of the Pitman-Stanley polytope to provide geometric realizations of the v-Tamari lattice of Préville-Ratelle and Viennot as the dual of a triangulation of a polytope, as the dual of a mixed subdivision, and as the edge-graph of a polyhedral complex induced by a tropical hyperplane arrangement. The method generalizes to type B. This is joint work with Cesar Ceballos and Camilo Sarmiento.
Bernd
Sturmfels
UC Berkeley/TU Berlin
Convexity in Tree Spaces
Abstract.
We study the geometry of metrics and convexity structures on the space of phylogenetic trees, here realized as the tropical linear space of all ultrametrics. The CAT(0)-metric of Billera-Holmes-Vogtman arises from the theory of orthant spaces. While its geodesics can be computed by the Owen-Provan algorithm, geodesic triangles are complicated and can have arbitrarily high dimension. Tropical convexity and the tropical metric are better behaved, as they exhibit properties that are desirable for geometric statistics.
Tobias
Friedl
FU Berlin
Two Twisted Poset Polytopes
Abstract.
In 1986, Stanley introduced two polytopes associated with a finite poset P: The order polytope O(P) and the chain polytope C(P). Many geometric properties of these polytopes can be described only in terms of the underlying poset P. Moreover, there exists a continuous, piecewise linear bijection between O(P) and C(P), yielding that the volume (and even the Ehrhart polynomial) of the two polytopes is the same. In this talk we will generalize these results to the case of twisted prisms over order and chain polytopes. This is joint work with T. Chappell and R. Sanyal.
May 2016
Albert
Haase
FU
Open questions related to Tverberg's Theorem
Abstract.
Frick's counterexamples to the topological Tverberg conjecture in 2015 settled the main open question regarding Tverbergâs theorem, namely that Tverbergâs theorem cannot be extended to the non-prime-power case. The constraint method developed by Blagojevic, Ziegler, and Frick shows how Tverbergâs theorem and essentially the pigeonhole principle directly imply and, in some cases, strengthen many of the results related to Tverbergâs theorem that were published since the 1980s. So what â if any â are the remaining open questions related to Tverbergâs theorem? In my talk I will touch on one of most prominent open questions and tell you what progress has been made. This is ongoing work with BlagojeviÄ, Engström, and Ziegler.
Hao
Chen
TU Eindhoven
Selectively Balancing Unit Vectors
Abstract.
A set of unit vectors in R^n is selectively balancing if there is a non-zero linear combination with coefficients -1, 0 or 1 whose norm is smaller than 1. We prove that O(n log n) unit vectors suffice to ensure a selectively balancing set, and this estimate is asymptotically best possible. This result finds application in dot product representation of cubes. This is a joint work with Blokhuis.
Maren
Ring
Rostock
A geometric local formula for Ehrhart coefficients
Abstract.
Let P be a lattice polytope in R^d and tP its dilation by a positive integer t. In dimension 2, Pick's Theorem (1899) leads to a connection between the number of lattice points in tP and its volume: #(lattice points in tP) = vol(P) t^2 + (B/2) t + 1, where B is the number of lattice points on the boundary of P. Equivalently, B can be seen as the sum of relative volumes of the edges of P. The higher dimensional generalization of this function is the Ehrhart polynomial. As in the 2-dimensional case, the coefficients of Ehrhart polynomials can be determined via so-called local formulas, by weighting the relative volumes of the faces of P. We develop a construction of these weights based on an elementary geometric idea.
April 2016
Emanuele
Ventura
Aalto University
Real rank geometry of ternary forms
Abstract.
The problem of expressing a homogeneous polynomial as a sum of powers of linear forms is very classical and goes back to the work of Sylvester, Hilbert, and Scorza among others. The real rank of a homogeneous polynomial is the smallest number of linear real forms such that the polynomial admits such a representation. The space parametrizing all real decompositions of a polynomial as a minimal sum of powers is a semialgebraic set sitting inside the classical Varieties of Sums of Powers. For plane cubics, we find a connection with oriented matroids. This is a joint work with M. Michalek, H. Moon and B. Sturmfels.
Christian
Stump
Algebraic combinatorics of reflection arrangements and generalizations
Abstract.
Reflection arrangements have a long history in algebraic combinatorics. Unfortunately, their friends, the Catalan and Shi arrangements, have so far resisted from being generalized beyond Weyl types, and indeed several authors showed that such arrangements cannot be as beautiful for the reflection group of type H4. I start with recalling a few fundamental discrete-geometric properties of (reflection) arrangements. I then discuss surprising numerical observations in the module of derivations of a complex reflection arrangement that indicate that we still miss the "correct" combinatorics to study Catalan and Shi arrangements for general reflection groups. This talk is based on results in an ongoing collaboration with Torsten Hoge and Gerhard Röhrle.
Philip
Brinkmann
FU Berlin
Enumeration of 3-Spheres
Abstract.
In 1906 Steinitz gave a complete characterisation of the set of f-vectors of 3-polytopes. Since then people are trying to find a characterisation for the 4-dimensional case. However, there is still no such description that is complete. There is also no guess for a description of the set of f-vectors of 3-spheres (which have the boundary complexes of 4-polytopes as special cases), nor did we know up to now whether the set of f-vectors of 3-spheres is the same or strictly larger than the one of 4-polytopes - although most spheres are not polytopal (i.e. can be realised as the boundary complex of a convex polytope). In this talk I will present and explain an algorithm to enumerate 3-spheres for a given f-vector (f_0,f_1,f_2,f_3). Furthermore, I will present some of the enumeration results that finally prove that the set of f-vectors of 3-spheres is strictly larger than the set of f-vectors of 4-polytopes. This is joint work with GĂŒnter M. Ziegler.
February 2016
Sören
Berg
TU Berlin
Tensor-valued Ehrhart theory
Abstract.
For a lattice polytope we can define the so-called discrete moment tensor of a certain rank. In the particular cases where this rank is zero or one this yields the number of lattice points or the sum of all lattice points contained in the polytope, respectively. Based on the work by Khovanskii and Pukhlikov the discrete moment tensor of a dilate of a lattice polytope by an integral factor is a polynomial in that dilation factor. For the discrete moment tensor of rank zero this collapses to the well-known Ehrhart theory. In this talk we want to discuss a few classical results from Ehrhart theory which extend naturally for discrete moment tensors of higher rank and some which do not. Starting with simple observations on some coefficients of the underlying polynomials we will carry on with the h-star polynomials arising from the corresponding generating functions. For these h-star polynomials having tensor-valued coefficients we will elaborate basic properties and introduce a notion of positivity and monotonicity. This is ongoing joint work with Katharina Jochemko and Laura Silverstein from TU Vienna.
January 2016
JĂŒrgen
Richter-Gebert
TU MĂŒnchen
The Quest for Nice (Bracket) Formulas
Abstract.
The talk deals with the search for nice symmetric formulas for nice symmetric problems in Invariant theory. After a general introduction that highlights some formulas for geometric primitive operations. Two specific (more advanced) scenarios are addressed; both of them are related to the theory of algebraic curves in the plane. The first one deals with a problem related to the Cayley Bacharach Theorem: Calculate the ninth point of intersection of a pair of cubics if eight intersections are given. Surprisingly this point is uniquely determined and (as a consequence of the First Fundamental Theorem of Invariant Theory) should have a representation as a bracket expression free of polynomial roots. Two such formulas are presented. The second problem concerns the quest for a nice, short and symmetric bracket formula that that expresses the fact that 10 points in the projective plane lie on a common cubic. A nice formula and a short formula will be presented. Unfortunately so far we do not know about a nice and short formula.
Ivan
Izmestiev
U Fribourg
Connecting balanced triangulations by cross-flips
Abstract.
A d-dimensional simplicial complex is called balanced, if its vertices can be properly colored in d+1 colors. In a joint work with Isabella Novik and Steve Klee we introduced a notion of cross-flips: certain moves that transform a balanced simplicial complex into another balanced simplicial complex. These moves form a natural balanced analog of bistellar flips (also known as Pachner moves). We established the following analog of Pachner's theorem: two balanced simplicial complexes that represent closed combinatorial manifolds are PL homeomorphic if and only if they can be connected by a sequence of cross-flips.
December 2015
Matthias
Henze
FU
On lattice points in strictly convex sets and Helly-type numbers in integer programming
Abstract.
Doignon proved a discrete version of Helly's theorem claiming that a finite family of convex sets in R^n intersects in an integral point if every subfamily of size at most 2^n does so. Motivated by applications in integer programming, Aliev et al. recently obtained a quantitative version of this result, which guarantees that a finite family of convex sets intersects in k integral points whenever every subfamily of size at most c_n(k) does so. The best current upper bound on the minimal such constant c_n(k) grows linearly with the parameter k. Based on a connection to the number of boundary integral points in strictly convex sets, we show that the asymptotic behavior of c_n(k) is sublinear in dimension two and we determine the exact value of c_n(k) for k at most four.
November 2015
Sarah
Brodsky
The D4 cluster algebra and tropical positivity
Abstract.
We show that the number of combinatorial types of clusters of type $D_4$ modulo reflection-rotation is exactly equal to the number of combinatorial types of tropical planes in $\mathbb{TP}^5$. This follows from a result of Sturmfels and Speyer which classifies these tropical planes into seven combinatorial classes using a detailed study of the tropical Grassmannian $\Gr(3,6)$. Speyer and Williams show that the positive part $\Gr^+(3,6)$ of this tropical Grassmannian is combinatorially equivalent to a small coarsening of the cluster fan of type~$D_4$. We provide a structural bijection between the rays of $\Gr^+(3,6)$ and the almost positive roots of type $D_4$ which makes this connection more precise. This bijection allows us to use the pseudotriangulations model of the cluster algebra of type $D_4$ to describe the equivalence of "positive" tropical planes in $\mathbb{TP}^5$, giving a combinatorial model which characterizes the combinatorial types of tropical planes using automorphisms of pseudotriangulations of the octogon.
Fatemeh
Mohammadi
Applications of Combinatorial Commutative Algebra in system reliability theory, and Signature analysis for Erdös-Rényi model
Abstract.
I will talk about the application of syzygy tool from commutative algebra in two concrete examples arisen in system reliability theory. Let $G$ be a connected graph whose vertices are reliable but each edge $e$ may fail with the probability $p_e$. There is a canonical ideal associated to $G$ whose Hilbert series encodes the reliability of the system which is the probability that $G$ is connected. I will talk about the connections between matroid theory and system reliability theory applying some tools from convex geometry and commutative algebra.
Raman
Sanyal
FU
Extension complexity of Hypersimplices -- fun and other feelings
Abstract.
A (n,k)-hypersimplex is the convex hull of all 0/1-vectors of length n with exactly k ones. This is a very explicit class of polytopes that appears in many contexts including algebraic geometry and geometric combinatorics. The extension complexity of a polytope P is the minimal number of facets of a polytope Q that projects onto P. This simple-to-state invariant has its origins in combinatorial optimization and is extremely difficult to compute in general. In this talk I will tell you about the extension complexity of hypersimplices and combinatorial hypersimplices. For hypersimplices, this is a lot of fun and involves geometry, combinatorics, and computers. For combinatorial hypersimplices, the other feelings kick in. This is based on joint work with Francesco Grande and Arnau Padrol.
Kathlén
Kohn
Voronoi Cells of Lattices w.r.t. Arbitrary Norms
Abstract.
Micciancio and Voulgaris gave in 2010 'A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations'. Among others, their algorithm solves the prominent Shortest/Closest Vector Problem, but it works solely for the Euclidean norm. One open problem listed by Micciancio and Voulgaris is the extension of this algorithm to other p-Norms. We show that a direct extension with deterministic single exponential time is not possible, for the following reason: Micciancio and Voulgaris represent the Voronoi cell of a lattice (w.r.t. the Euclidean norm) by a finite set of lattice vectors, called the Voronoi-relevant vectors. In particular, they use that the number of the Voronoi-relevant vectors is upper bounded by a bound solely depending on the lattice dimension. We show that such a bound does not even exist for the 3-norm.
October 2015
Moritz
Schmitt
Freie UniversitÀt Berlin
On the number of space groups
Abstract.
A space group is a discrete group of isometries with bounded fundamental domain. Prominent examples are the 17 wallpaper groups and 219 crystallographic groups. Bieberbach proved that in each dimension there are only finitely many non-isomorphic space groups, and much later Buser gave the first upper bound. We will show how to improve Buser's bound considerably and get close to known lower bounds.
MichaĆ
LasoĆ
http://www.mi.fu-berlin.de/math/groups/discgeom/members/Lason.html
On the toric ideal of a matroid and related combinatorial problems
Abstract.
When an ideal is defined only by combinatorial means, one expects to have a combinatorial description of its set of generators. An attempt to achieve this description often leads to surprisingly deep combinatorial questions. White's conjecture is an example. It asserts that the toric ideal associated to a matroid is generated by quadratic binomials corresponding to symmetric exchanges. In the combinatorial language it means that if two multisets of bases of a matroid have equal union (as a multiset), then one can pass between them by a sequence of symmetric exchanges. White's conjecture resisted numerous attempts since its formulation in 1980. We will discuss its relations with other open problems concerning matroids.
Alexander
Engström
Aalto University
Self-polar resolutions
Abstract.
Polytopes with strong duality properties are introduced. They are interesting for constructing explicit projective resolutions of ideals with a strong duality on the syzygies. I will provide some evidence for that this is a fairly general possibility, and discuss results towards that with Linusson on Stanley-Reisner ideals of cyclic polytopes.
September 2015
Hannah
SchÀfer Sjöberg
The combinatorial parameters (f_0, f_03) of 4-dimensional polytopes
Abstract.
For dimensions d â„ 4, the complete set of all f-vectors of d-polytopes has not been characterized. For dimension 4, the projections of f-vectors onto 2 of the 4 coordinates have been determined by GrĂŒnbaum (1967), BarnetteâReay (1973) and Barnette (1974). We expand these results to the flag vectors of 4-polytopes. We will characterize the projection of the set of all flag vectors of 4-polytopes to the two coordinates f_0 and f_03.
June 2015
Jonathan
Spreer
University of Queensland
Parameterised complexity theory for topological problems
Abstract.
Many of the most important algorithmic problems in computational geometry are known to be NP-complete or even have unknown complexity. On the other hand, these difficult problems can often be solved efficiently with the use of heuristics. I will explain how the framework of parameterised complexity can be used to explain this inconsistent behaviour and present a number of examples and recent results.
Emmanuel
Tsukerman
Circumcenter of mass
Abstract.
I shall define and study a variant of the center of mass of a polygon, called the circumcenter of mass. The circumcenter of mass is an affine combination of the circumcenters of the triangles in a non-degenerate triangulation of a polygon, weighted by their areas, and is independent of the triangulation. It satisfies an analog of the Archimedes Lemma, similarly to the center of mass of the polygonal lamina, and hence gives rise to an isometry-covariant valuation. The line connecting the circumcenter and the centroid of a triangle is called the Euler line. Taking affine combinations of the circumcenter of mass and the center of mass, one obtains an Euler line of a polygon. The construction of the circumcenter of mass extends to simplicial polytopes and to the spherical and hyperbolic geometries.
Anton
Dochtermann
Warmth and edge spaces of graphs
Abstract.
In recent years two novel approaches for finding lower bounds on the chromatic number of a graph have been introduced. One involves studying the topological connectivity of the 'edge space' of a graph, dating back to Lovasz's celebrated proof of the Kneser conjecture. The other is motivated by constructions in statistical physics and involves the notion of long range action of random branching walks and the 'warmth' of a graph, as introduced by Brightwell and Winkler. We seek to relate these two constructions, and in particular we provide evidence for the conjecture that the warmth of a graph G is always less than three plus the connectivity of its edge space. We succeed in establishing the first nontrivial case of the conjecture, and calculate the warmth of a family of graphs with relevant edge space topology. We also demonstrate a connection between the warmth of a graph and the collection of complete bipartite subgraphs that it contains, providing an analogue for a similar result in the context of edge spaces. This is joint work with Ragnar Freij.
Samuel
Fiorini
ULB
No Small Linear Program Approximates Vertex Cover within a Factor 2-epsilon
Abstract.
The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev (2003) proved that the problem is NP-hard to approximate within a factor 2-epsilon, assuming the Unique Games Conjecture (UGC). This is tight because the problem has an easy 2-approximation algorithm. Without resorting to the UGC, the best inapproximability result for the problem is due to Dinur and Safra (2002): vertex cover is NP-hard to approximate within a factor 1.3606. We prove the following unconditional result about linear programming (LP) relaxations of the problem: every LP relaxation that approximates vertex cover within a factor of 2-epsilon has super-polynomially many inequalities. As a direct consequence of our methods, we also establish that LP relaxations that approximate the independent set problem within any constant factor have super-polynomially many inequalities. This is joint work with Abbas Bazzi, Sebastian Pokutta and Ola Svensson.
Bram
Petri
Fribourg
The systole of a random surface
Abstract.
In this talk a random surface will be a surface constructed by randomly gluing together an even number of triangles that carry a fixed metric. The model lends itself particularly well to studying the geometry of typical high genus hyperbolic surfaces. For example, it turns out that the expected value of the length of the shortest non-contractible curve, the systole, of such a surface converges to a constant. In this talk I will explain what goes into the proof of this fact and how this relates to the theory of random regular graphs and random elements in the symmetric group.
May 2015
Hao
Chen
Dressing code for the sphere - scribability problems of polytopes
Abstract.
We will study various scribability problems, including the classical one studied by Steinitz and Schulte, the weak one proposed by GrĂŒnbaum-Shephard and Schulte, and the new (i, j)-scribability which requires faces to cut or avoid the sphere instead of being tangent. We obtain new results for each of these problems. In particular, classical scribabilities are fully answered for stacked and cyclic polytopes; the loose end left by Schulte on weak scribability is tied up. As for the new (i, j)-scribability, we find counter examples in most cases, but leave two cases open. This is a joint work with A. Padrol.
Torsten
Hoge
Leibniz UniversitÀt Hannover
The freeness of ideal subarrangements of Weyl arrangements
Abstract.
The talk is based on joint work with Takuro Abe, Mohamed Barakat, Michael Cuntz and Hiroaki Terao on Weyl arrangements. A Weyl arrangement is the arrangement defined by the root system of a finite Weyl group. When a set of positive roots is an ideal in the root poset, we call the corresponding arrangement an ideal subarrangement. Our main theorem asserts that any ideal subarrangement is a free arrangement and that its exponents are given by the dual partition of the height distribution, which was conjectured by Sommers-Tymoczko. In particular, when an ideal subarrangement is equal to the entire Weyl arrangement, our main theorem yields the celebrated formula by Shapiro, Steinberg, Kostant, and Macdonald. Our proof of the main theorem heavily depends on the theory of free arrangements and thus greatly differs from the earlier proofs of the formula.
April 2015
Karim
Adiprasito
Tobias
Friedl
Zero Sets of Polynomials Invariant under Finite Reflection Groups
Abstract.
The degree principle states that the non-emptiness of the zero set of a symmetric polynomial of degree at most d can be tested on a set of dimension d, independent of the dimension of the ambient space (Timofte, 2003, Riener, 2012). In this talk we generalize this to the case of arbitrary reflection groups. We show that the non-emptiness of the zero set of an invariant polynomial can be tested on the union of certain flats in the corresponding reflection arrangement. This is joint work with Cordian Riener and Raman Sanyal.
March 2015
Bruno
Benedetti
Two results on collapsibility
Abstract.
We discuss higher dimensional versions of two basic results: (1) Every tree is planar, (2) Every tree has at least two leaves. If time permits, we show a few applications. This is joint work with Karim Adiprasito and Frank Lutz (arxiv:1403.5217, arxiv:1404.4239).
February 2015
Philip
Brinkmann
Flag Vector Spaces of Polytopes, Spheres and Eulerian Lattices
Abstract.
This talk deals with open questions concerning the flag vector spaces of polytopes, strongly regular spheres and Eulerian lattices. The latter two are natural generalizations of polytopes, since polytope boundaries are strongly regular spheres, and the combinatorial structure behind forms Eulerian lattices. The open questions discussed concern characteristics and description of the sets of flag-vectors that belong to these objects. Emphasis lies here on the distinguishing of the sets of flag-vectors of the three classes of objects. For dimension $d=4$ this relates to the parameters fatness and complexity, which are introduced and studied.
January 2015
Sarah
Brodsky
Moduli of Tropical Plane Curves
Abstract.
Tropical curves have been studied under two perspectives; the first perspective defines a tropical curve in terms of the tropical semifield \(\mathbb{T}=(\mathbb{R}\cup \{-\infty\}, \max, +)\), and the second perspective defines a tropical curve as a metric graph with a particular weight function on its vertices. Joint work with Michael Joswig, Ralph Morrison, and Bernd Sturmfels, we study which metric graphs of genus \(g\) can be realized as smooth, plane tropical curves of genus \(g\) with the motivation of understanding where these two perspectives meet. Using Polymake, TOPCOM, and other computational tools, we conduct our study by constructing a map taking smooth, plane tropical curves of genus \(g\) into the moduli space of metric graphs of genus \(g\) and studying the image of this map. In particular, we focus on the cases when \(g=2,3,4,5\). In this talk, we will introduce tropical geometry, discuss the motivation for this study, our methodology, and our results.
Matthias
Henze
Congruence Arguments in the Geometry of Numbers and a General Discrete Minkowksi-type Theorem
Abstract.
One of the most fruitful results from Minkowski's geometric viewpoint on number theory is his so called 1st Fundamental Theorem. It says that the volume of every o-symmetric n-dimensional convex body whose only interior lattice point is the origin is bounded from above by the volume of the orthogonal n-cube of edge length two. Minkowski also obtained a discrete analog by identifying the n-cube as a maximizer of the number of lattice points in the boundary of such convex bodies. Whereas the volume inequality has been generalized to any number of interior lattice points already by van der Corput in the 1930s, a corresponding result for the discrete case remained to be proven. Using congruence arguments for lattice points and an inequality in additive combinatorics, we determine a best possible relation of this kind. In the talk, we will moreover highlight the usefulness of considering congruences on lattice points in the geometry of numbers. This is joint work with Bernardo GonzĂĄlez Merino.
Leif
Naundorf
FU Berlin
Generalized Schur-Horn orbitopes and zonoids
Abstract.
In this talk I will introduce a special class of convex bodies, the so-called orbitopes. We will take a closer look at a special class of orbitopes, namely the Schur-Horn orbitopes and their generalizations which can be seen as continuous generalizations of permutahedra. We will introduce the notion of a zonoid which is the continuous generalization of a zonotope. Since some permutahedra are zonotopes it is a natural question to ask if there are Schur-Horn orbitopes which are zonoids. We will see that this is in general not the case.
Victor M.
Buchstaber
Steklov Mathematical Institute, Moscow
Combinatorial 2-truncated cubes and applications
Abstract.
The talk is based on the results of Victor Buchstaber, Vadim Volodin, Mikhail Gorsky and Nikolai Erochovets. In the first part of the talk we will discuss the family of combinatorial polytopes that can be obtained from a cube by sequence of truncations of codimension 2 faces (2 - truncated cubes). Every 2-truncated cube is flag simple polytope. These polytopes have remarkable properties and this family contains classes of polytopes playing important roles in different areas of mathematics. The second part will be devoted to the results of the flag simple polytopes, which turns the operation of 2-truncation of the remarkable simple flag polytopes (dodecahedron, fullerenes and their multidimensional analogues) that are not 2-truncated cubes.
December 2014
Jean-Philippe
Labbé
Lower bound for the discrepancy of triangulations of the square with an odd number of triangles
Abstract.
Paul Monsky proved in 1970 that it is impossible to dissect a square using an odd number of triangles all of which having the same area. Guenter Ziegler posed the problem to study the discrepancy of such triangulations, that is: as the number of triangles increases, study how close can dissections be to the ideal situation where all triangles would have equal area. In this talk, we will prove a doubly exponential lower bound using real algebraic geometry results bounding the distance between zeros of a multivariate polynomial. Further, we will describe a family of dissections which could achieve a exponentially decreasing discrepancy supported by experimental results.
Emily
McCullough
On the Unimodality of h^*-vectors for Lattice Parallelepipeds and Zonotopes
Abstract.
It is a famous open question whether the Ehrhart h^*-vector of integrally closed lattice polytopes is unimodal. This question was answered in the affirmative for lattice parallelepipeds by Schepers and Van Langenhoven. In a joint project with Matt Beck and Katharina Jochemko, we give a geometric proof of this argument and a combinatorial interpretation to the entries of the h^*-vectors in terms of permutation descent statistics on the symmetric group. Via a refinement of these descent statistics, the result is extended to include half-open parallelepipeds (closed parallelepipeds with any j adjacent facets removed). From this, together with results from Shephard, and Köppe and Verdoolaege, we show that the h^*-vector for lattice zonotopes is also unimodal. In this talk I introduce the main actors in our story, namely, permutation descent statistics (in a familiar and a refined variety), half-open unit cubes, lattice parallelepipeds and unimodular simplices. I will discuss the interplay of the geometry and the combinatorics and I will review our main results and motivate their proofs with illustrative examples.
MĂłnica
Blanco
Classification of lattice 3-polytopes with 5 or 6 lattice points
Abstract.
We undertake the complete classification of lattice 3-polytopes with n lattice points, modulo unimodular equivalence, for n=5 and n=6. We first argue that for each n there is only a finite number of (equivalence classes) of polytopes of lattice width larger than one and exactly n lattice points. Polytopes of width one are easy to classify, an infinitely many, so we concentrate on an exhaustive classification of those of width larger than one. For n=4, all empty tetrahedra have width one (classical result by White, Howe). For n=5 we show that there are exactly 9 different polytopes of width 2, and none of larger width. For n=6, we show that there are 74 classes of width 2, 2 of width 3, and none of larger width. We give explicit coordinates for representatives of each class, together with other invariants such as their oriented matroid and volume vector. Our motivation comes partly from the concept of distinct pair sum (or dps) polytopes, which are known to have at most 8 lattice points in dimension 3. Among the 9 + 74 + 2 classes mentioned above, exactly 9 + 44 + 1 are dps.
November 2014
Anders
Björner
KTH Stockholm
A q-analogue of the FKG inequality and some applications
Abstract.
The FKG inequality, due to Fortuin, Kasteleyn and Ginibre (1971), is a correlation inequality stemming from work in statistical mechanics. In this talk I will discuss some uses of the FKG inequality in extremal combinatorics, and I will present a polynomial generalization. The polynomial FKG inequality has applications to f-vectors of joins of simplicial complexes, to Betti numbers of intersection of certain Schubert varieties, and to power series weighted by Young tableaux. The talk will be quite elementary. No previous familiarity with these topics will be assumed.
Thomas
Stollin
FU Berlin
The Brunn-Minkowski Inequality for Zonotopes
Abstract.
The Brunn-Minkowski inequality is the most prominent example of a geometric volume inequality of convex geometry with far reaching implications. This inequality together with several other related inequalities like Minkowskiâs First and Second Mixed-Volume inequalities and the Aleksandrov-Fenchel inequality are of particular interest for the field of Discrete Geometry. Several proofs arose out of the theory of polytopes exploiting relations of discrete structures and the continuous measures of volume and mixed volume. A particularly interesting class of polytopes in Discrete Geometry are zonotopes which are finite sums of segments. On the one hand, zonotopes feature strong combinatorial properties such as their relation to hyperplane arrangements that allow for relating the volume of the zonotope to volumes of projections and subzonotopes via the deletion and contraction. On the other hand, the interpretation of a zonotope as an affine image of a possibly higher-dimensional cube offers an association with rectangular matrices. This relation can be used to compute volumes and mixed volumes of zonotopes by applying means of linear algebra. Thus, zonotopes and their subclass of parallelotopes are a link between geometry, combinatorics, and linear algebra providing rich structure and easy computation of volumes. Hence, they are a natural choice for investigating details concerning Minkowskiâs geometric volume inequalities. In this talk I will present results and observations obtained by following this approach in my masterâs thesis.
Matthias
Beck
July 2014
Pablo
SoberĂłn
U Michigan
Tverbergâs theorem and the Birkhoff polytope
Abstract.
Tverbergâs theorem describes the number of points needed in R^d to guarantee the existence of a partition of them into k sets whose convex hulls intersect. This result has led to many variations and extensions, among them what we call the âcolorful versionsâ. In this talk we will discuss how some of these versions can be mixed together, where some conditions involve points in the Birkhoff polytope instead of usual convexity relations. No prior knowledge of the subject is required.
Ivan
Izmestiev
FU Berlin
Fitting the barycenters by a projective transformation
Abstract.
For two subsets A and B of a euclidean space, does there exist a projective transformation f such that the barycenters of f(A) and f(B) coincide? In the following situations f exists and is unique (up to an affine transformation): 1) A is the vertex set of a convex polytope, B a single point inside the polytope (related to polarity wrt a higher order algebraic curve); 2) A is a convex body, B a single point inside (this case was previously known and is related to the Blaschke-Santalo theorem on minimizing the volume of the polar dual); 3) A is the unit sphere, B a finite set of points on it (this is related to the uniqueness of edge-circumscribed realizations of 3-polytopes). If A and B are convex bodies, one sitting inside the other, then a projective transformation exists but is not always unique. It is unique, provided that B is "small enough" wrt A in the projective sense. A suitable transformation corresponds to a critical point of a certain functional, related to the moment of inertia of the classical mechanics.
June 2014
Serkan
Hosten
San Francisco State University
The degree of the central curve in quadratic programming
Abstract.
For convex optimization problems, such as linear, quadratic, or semidefinite programming, a class of interior point algorithms track the so-called central path to an optimal solution. The central curve, the Zariski closure of the central path, is an algebraic curve and it has been recently studied by De Loera, Sturmfels, and Vinzant in the linear case. In particular, the degree of the central curve for linear programming has been computed, and this has implications for the complexity of the interior point algorithms. We tackle the next case, the degree of the central curve for quadratic programming. After a reduction to the 'diagonal' case, we conjecture a formula and present a strong case for the conjecture. Also, in the diagonal case, we construct a Groebner basis for the ideal defining the central curve.
Karola
Meszaros
Cornell
h-polynomials of triangulations of flow polytopes
Abstract.
The h-polynomial of a simplicial complex is a way of encoding the number of faces of each dimension. I will introduce a multivariate generalization of the h-polynomials of unimodular triangulations of flow polytopes. The inspiration for this generalization lies in the subdivision algebra of flow polytopes, whose relations prescribe a way of subdividing flow polytopes. The multivariate generalization of the h-polynomials can be used to prove certain nonnegativity properties in the subdivision and related algebras.
Timo
de Wolff
SarbrĂŒcken
Nonnegative Polynomials and Sums of Squares Supported on Circuits
Abstract.
Nonnegativity of real polynomials is a key question in real algebraic geometry with crucial importance in polynomial optimization. In this talk we completely characterize sections of the cones of nonnegative polynomials and sums of squares with âpolynomials supported on circuitsâ -- a genuine class of sparse polynomials. In particular, nonnegativity is characterized by an invariant, which can be immediately derived from the initial polynomial using a new norm based relaxation strategy. Based on these results, we obtain an entire new class of nonnegativity certificates independent from sums of squares certificates. On the optimization side these results significantly extend known geometric programming approaches for the computation of lower bounds. These results generalize earlier works by Fidalgo, Ghasemi, Kovacec, Marshall and Reznick. The talk is based on joint work with Sadik Iliman.
May 2014
Ragnar
Freij
Polytopes from graph homomorphisms
April 2014
Christophe
Hohlweg
UQAM
Camilo
Sarmiento
Magdeburg
Dyck path triangulations and extendability
Abstract.
In this talk, we introduce the Dyck path triangulation of the cartesian product of two simplices: its maximal simplices are given by Dyck paths along with their orbit under a cyclic action. The construction also naturally produces triangulations of the product of two simplices consisting of rational Dyck paths. Our study of the Dyck path triangulation is motivated by an extendability problem for certain kinds of partial triangulations of the product of two simplices. We present a complete solution to this extendability problem and, with an explicit construction of non-extendable partial triangulations, we prove that our characterization of extendability is optimal. Time permitting, we will briefly mention interesting interpretations of our results in the language of tropical oriented matroids, which are analogous to classical results in oriented matroid theory.
February 2014
Johannes
Rauh
MPI Leipzig
Polytopes from Subgraph Statistics
January 2014
Hao
Chen
FU Berlin
Raman
Sanyal
FU Berlin
Upper Bound Problems and relative Stanley-Reisner theory
Abstract.
The Upper Bound Theorem (UBT) states that among all simplicial d-spheres on n vertices precisely the neighborly spheres maximize the f-vector componentwise. McMullen established the UBT for convex polytopes taking a very geometric approach via shellings. Stanley's generalization to simplicial spheres elegantly combines ideas from combinatorics, commutative algebra, and combinatorial topology. Together with Karim Adiprasito (IHES), we extend these ideas into an algebraic framework for treating relative simplicial complexes. This allows us to resolve upper bound problems of various types including a tight Upper Bound Theorem for Minkowski sums. In this (slightly informal) talk I will try to give a hands-on introduction to this 'relative Stanley-Reisner theory' and its applications.
December 2013
Jean-Philippe
Labbé
FU Berlin
Thilo
Rörig
TU Berlin
Bernd
Sturmfels
Berkeley/Bonn
Quartic Spectrahedra
Abstract.
Spectrahedra are the feasible regions in semidefinite programming. This includes convex polyhedra, the feasible regions in linear programming. We present a tiny first step towards the classification of spectrahedra of a given degree and dimension, by focusing on the 24-dimensional family of all quartic spectrahedra in 3-space. These come in 20 generic types, according to the location of their nodal singularities. This lecture is based on joint work with John Christian Ottem, Kristian Ranestad, and Cynthia Vinzant. It intertwines convex geometry with classical algebraic geometry, and offers many colorful pictures.
Peter
BĂŒrgisser
TU Berlin
Intrinsic volumes and their applications in convex optimization
Abstract.
To a closed convex cone C \\subseteq R^d, one can assign the probability distribution v_0(C),...,v_d(C) of its (spherical) intrinsic volumes. These invariants arise naturally in spherical integral geometry. They are of relevance for understanding algorithms in convex optimization, e.g., for the probabilistic analysis of condition numbers. Numerous fascinating open questions involving spherical intrinsic volumes call for a solution: we conjecture that the sequence v_0(C),...,v_d(C) is always log-concave (a property euclidean inner volumes are known to satisfy). In the talk, I will report about a recent insight due to Amelunxen, Lotz, McCoy, and Tropp. They proved that the distribution of intrinsic volumes concentrates sharply around its mean \delta(C) := \sum_{k=0}^d k v_k(C), for which they coined the name "statistical dimension of C". This has important implications. The kinematic formula, a crowning achievement in integral geometry, implies that a random linear subspace of codimension m hits C nontrivially with the probability hit_C(m) = 2 ( v_{m+1}(C) + v_{m+3}(C) + ...). The concentration result for intrinsic volumes implies that for m >= \delta(C) + \lambda, the hitting probability hit_C(m) decays exponentially with \lambda, while for m <= \delta(C) - \lambda, hit_C(m) is exponentially close to 1. This threshold result enables a uniform treatment of phase transitions in convex optimization, as needed for compressed sensing.
November 2013
Alexey
Garber
Moscow State University
Parallelohedra and the Voronoi Conjecture
Abstract.
A parallelohedron is a d-dimensional polytope which can tile the d-dimensional Euclidean space with translation copies. In 1909 Voronoi conjectured that every parallelohedron is an affine image of a Dirichlet-Voronoi polytope for some lattice. Since Voronoi stated his conjecture there were several results for different families of parallelohedra (G.Voronoi himself, O.Zhitomirskii, R.Erdahl, A.Ordine) but the conjecture remains unproved in the general case. In this talk we will discuss some of the mentioned results and the way they were achieved, also we will sketch the proof of the Voronoi conjecture in a new special case. Furthermore we will discuss some other problems related to parallelohedra theory and the Voronoi conjecture. This is joint work with A.Gavrilyuk and A.Magazinov.
Alexander
Maksimenko
k-Neighborly polytopes in combinatorial optimization
Abstract.
Definition: k-neighborly polytope is a convex polytope in which every set of k or fewer vertices forms a face. E.g., every pair of vertices of a 2-neighborly polytope is connected by an edge. It is known today that as a rule, polytopes of NP-complete problems have a 2-neighborly faces with large (superpolynomial) number of vertices. It is known also that 2-neighborly polytopes are more common than any other among random polytopes. These and some other facts force to look more carefully at the properties of such polytopes. We will try to shed light on this phenomenon and answer the main question: could the k-neighborliness be good complexity measure of a polytope.
Hao
Chen
FU Berlin
Boyd--Maxwell ball packings
Abstract.
In the recent study of infinite root systems, fractal patterns of ball packings were observed while visualizing roots in affine space. We show that the observed fractals are exactly the ball packings generated by inversions described by Boyd and Maxwell, generalizing Apollonian ball packings. We describe the tangency graph of these packings in terms of Coxeter complexes, and list all Coxeter groups that generate Boyd--Maxwell packings. This is joint work with J-P Labbe.
October 2013
Nathan
Williams
Minnesota
Cataland
Abstract.
I will talk about two combinatorial miracles relating purely poset-theoretic objects with purely Coxeter-theoretic objects. The first miracle is that there are the same number of linear extensions of the root poset as reduced words of the longest element (occasionally), while the second is that there are the same number of order ideals in the root poset as certain group elements (usually). I will conjecturally place these miracles on remarkably similar footing and examine the generality at which we should expect such statements to be true.
September 2013
Matthias
Köppe
UC Davis
Intermediate sums on polyhedra and real Ehrhart theory
Abstract.
We study intermediate sums, interpolating between integrals and discrete sums, which were introduced by A. Barvinok [Computing the Ehrhart quasi-polynomial of a rational simplex, Math. Comp. 75 (2006), 1449â1466]. For a given polytope P with facets parallel to rational hyperplanes and a rational subspace L, we integrate a given polynomial function h over all lattice slices of the polytope P parallel to the subspace L and sum up the integrals. We first develop an algorithmic theory of parametric intermediate generating functions. Then we study the Ehrhart theory of these intermediate sums, that is, the dependence of the result as a function of a dilation of the polytope. We provide an algorithm to compute the resulting Ehrhart quasi-polynomials in the form of explicit step polynomials. These formulas are naturally valid for REAL (not just integer) dilations and thus provide a direct approach to real Ehrhart theory. The algorithms are polynomial time in fixed dimension. Following A. Barvinok (2006), the intermediate sums also provide an efficient algorithm to compute, for a fixed number k, the highest k Ehrhart coefficients in polynomial time if P is a simplex of varying dimension. The talk is based on joint papers with Velleda Baldoni, Nicole Berline, Jesus De Loera, and Michele Vergne.
Arnau
Padrol
FU Berlin
A universality theorem for projectively unique polytopes and a conjecture of Shephard
Abstract.
In this talk I will present the following universality theorem for projectively unique polytopes: every polytope described by algebraic coordinates is the face of a projectively unique polytope. This result can be used to construct a combinatorial type of polytope that is not realizable as a subpolytope of any stacked polytope. This disproves a classical conjecture in polytope theory, first formulated by Shephard in the seventies. This is joint work with Karim Adiprasito.
August 2013
Michael
Dobbins
POSTECH
Convexly independent subfamilies of convex bodies
Abstract.
A theorem of ErdĆs and Szekeres says that for any $n$ a sufficiently large family of point in the plane in general position will have $n$ points in convex position. In this talk I will show how this generalizes to families of convex bodies in the plane, provided that the number of common supporting tangents of each pair of bodies is bounded and every subfamily of size 5 is in convex position. This confirms a conjecture of Pach and TĂłth. This is joint work with Andreas Holmsen, Alfredo Hubard.
July 2013
Trung
Ngo Viet
Bhattacharya function of complete monomial ideals in two variables
Abstract.
Let R be a polynomial ring in d variables over a field k. Let I,J be two M-primary homogeneous ideals, where M is the maximal homogeneous ideal. Then one can consider the length function dim_k(R/I^mJ^n) for nonnegative integers m, n. Bhattacharya proved that this function is a polynomial P(m,n) of for m, n large enough. In general, it is very difficult to compute the Bhattacharya polynomial. If I, J are monomials, the computation of the Bhattacharya function can be reduced to a problem of counting integral points of Minkowski sum of polytopes. In this talk I will show how to compute the Bhattacharya function in the case I,J are complete monomial ideals in two variables. Our results show that the coefficients of the Bhattacharya polynomial can be explicitly expressed in terms of the vertices of the Newton polyhedra of I and J. This is a report on a joint work with Hong Ngoc Binh (Hanoi, Vietnam).
Daniel C.
Cohen
On the topology of matrix conguration spaces
Abstract.
We discuss some topological aspects of matrix configuration spaces, certain generalizations of the classical configuration space of n distinct ordered points in the plane. This is part of work in progress with Benson Farb.
NgĂŽ Viá»t
Trung
VAST, Vietnam
Bhattacharya function of complete monomial ideals in two variables