VeranstaltungenVeranstaltungen

# Forschungsseminar

NameDatumUhrzeitOrtTitel
Daniel Galicer (University of Buenos Aires)11.09.1916:30MA 406 TBA
Abstract:

TBA

Elisabeth Werner (Case Western Reserve University)08.07.1916:30MA 406 TBA
Abstract:

TBA

Stephan Tillmann (University of Sydney)03.07.1916:30MA 621 TBA
Abstract:

TBA

Sarah Morell26.06.1916:30MA 621 TBA
Abstract:

TBA

Rekha Thomas (University of Washington)19.06.1916:30MA 621 The Slack Realization Space of a Polytope
Abstract:

TBA

Alexander Koldobsky (University of Missouri)12.06.1916:30MA 406 An estimate for the distance from a convex body to subspaces of L_p
Abstract:

TBA

Guillermo Pineda Villavicencio (Federation University Australia)29.05.1916:30MA 621 Minkowski decompositions of polytopes via geometric graphs
Abstract:

Minkowski decomposition of polytopes is presented via geometric graphs. This is due to Kallay (1982), who reduced the decomposability of a realisation of polytope to that of its geometric graph, and in this way, introduced the decomposability of geometric graphs. One advantage of this approach is its versatility. The decomposability of polytopes reduces to the decomposability of geometric graphs, which are not necessarily polytopal. And statements on decomposability of geometric graphs often revolve around the existence of suitable subgraphs or useful properties in the graphs.
As applications, we revisit many of the known results in this area, including the classifications into decomposable and decomposable, of d-polytopes with at most 2d vertices due to Kallay (1979), and of d-polytopes with 2d+1 vertices due to Pineda-Villacicencio et al (2018). Classifying d-polytopes with 2d+2 vertices seems not possible at least for d=3; there exists a 3-polytope with both a decomposable realisation and an indecomposable realisation, showing in the strongest possible way that decomposability is not a combinatorial property.
The talk concludes with the main open problems in the area.

Giulia Codenotti (FU Berlin)22.05.1916:30MA 406 The covering minima of lattice polytopes
Abstract:

Covering minima of a convex body were introduced by Kannan and Lovasz to give a better bound on the constant in the flatness theorem, which states that the width of hollow convex bodies in a fixed dimension is bounded by a constant. 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 non-hollow lattice polytopes.

Boasz Slomka (Weizmann Institute)15.05.1916:30MA 406 On Hadwiger’s covering conjecture
Abstract:

https://www3.math.tu-berlin.de/combi/wp_henk/event/seminartalk-by-boasz-slomka/

Alheydis Geiger (Tuebingen)08.05.1916:30MA 621 Realisability of infinite families of tropical lines on general smooth tropical cubic surfaces
Abstract:

A tropical line on a smooth tropical cubic surface can be realised, if there exists a line on a smooth cubic surface, such that the tropicalisation of the surface and the line coincide with the given tropical cubic surface and tropical line. (This is called relative realisability.)
The tropical lines on a smooth tropical cubic surface can be classified by their combinatorial position. Thus we can distinguish isolated lines and two-point families. The latter are infinite families of tropical lines on the same surface of the same combinatorial position. There are two combinatorial positions of lines of general smooth tropical cubic surfaces that allow infinite families. The question is, whether all the lines in these families can be realised on some lift of the tropical cubic surface. This problem is only solved for one of the two positions and only if char(k)≠2 I will present the solution.

Andreas Paffenholz17.04.1916:30MA 621 tropical cubic surfaces
Abstract:

The Ehrhart polynomial counts lattice points in multiples of a lattice polytope P. It is a polynomial e(t) of degree d, and we know that its constant coefficient and the coefficients of t^d and t^(d-1) are positive, as those coefficients have a geometric interpretation. Much less is known about the other coefficients.
In the talk I first introduce some families of polytopes where it is known that all coefficients of the Ehrhart polynomial is positive, either via a suitable construction or because the coefficients have a combinatorial interpretation. In the second part I will introduce constructions for polytopes where at least one coefficient is negative. In particular I will discuss smooth polytopes. Here, it has been conjectured that such polytopes have an Ehrhart polynomial with positive coefficients. I will disprove this conjecture by providing explicit examples, also in the much smaller class of smooth reflexive polytopes.
This is joint work with F. Castillo, F. Liu, B. Nill.

Erika Roldan10.04.1916:30MA 621 Evolution of the homology and related geometric properties of the Eden Growth Model.
Abstract:

In this talk, we study the persistent homology and related geometric properties of the evolution in time of a discrete-time stochastic process defined on the 2-dimensional regular square lattice. This process corresponds to a cell growth model called the Eden Growth Model (EGM). It can be described as follows: start with the cell square of the 2-dimensional regular square lattice of the plane that contains the origin; then make the cell structure grow by adding one cell at each time uniformly random to the perimeter. We give a characterization of the possible change in the rank of the first homology group of this process (the "number of holes"). Based on this result we have designed and implemented a new algorithm that computes the persistent homology associated to this stochastic process and that also keeps track of geometric features related to the homology. Also, we present obtained results of computational experiments performed with this algorithm, and we establish conjectures about the asymptotic behavior of the homology and other related geometric random variables. The EGM can be seen as a First Passage Percolation model after a proper time-scaling. This is the first time that tools and techniques from stochastic topology and topological data analysis are used to measure the evolution of the topology of the EGM and in general in FPP models.

Andrew Newman, Manuel Radons, and Oğuzhan Yürük (TU Berlin)03.04.1916:30MA 621 Radons: Shellability, Yuruk: Lattice Polytopes and Face Enumeration of Certain Classes of Simplicial Polytopes, Newman: Random polytopes
Abstract:

Radons: Following Tim Roehmer's third lecture at the Bochum spring school, I will introduce the notion of shellability of a pure polytopal complex. A simplification of the concept for pure simplicial complexes and apllications of shellings in inductive proofs will be discussed.
Yuruk: This talk will summarize a certain part of Spring School on Polytopes in Ruhr University Bochum. We will first cover a lattice polytopes part of the lecture on geometry of polytopes. Then, we talk about the face enumeration of certain classes of simplicial polytopes that were discussed in the spring school.
Newman: Following the lectures of Pierre Calka at the Bochum meeting, I will discuss the history of the study of random polytopes going back to Sylvester's Four Point Problem. From there I will also discuss recent results of Werner, Reitzner, and others on the subject.

Holger Eble and Ayush Tewari (TU Berlin)27.03.1916:30MA 621 Eble: Epistatic weights and polyhedral geometry Tewari: Moduli of tropical plane curves of genus 6
Abstract:

Eble: Epistatic weights and cluster filtrations provide a mathematical tool for studying biological data sets. In this informal talk I will present the geometric motivation behind these notions.
Tewari: In the paper 'Moduli of tropical plane curves Brodsky', etc (2015) compute the moduli space of tropical curves of genus g, with g = 3, 4 and 5. In this talk, we would delve into computations trying to extend that computation to the case of g = 6.

Jonathan Kliem (FU Berlin)20.03.1916:30MA 621 A face iterator for polyhedra
Abstract:

We discuss a new algorithm that iterates over all elements of a meet-semilattice, where every interval is coatomic.

Jens Forsgaard (Universiteit Utrecht)13.02.1916:30MA 621 Nonegativity and Discriminants
Abstract:

We study the class of nonnegative polynomials obtained from the inequality of arithmetic and geometric means, called \emph{agiforms} or \emph{nonnegative circuit polynomials}. They generate a full dimensional subcone $S$ of the cone of all nonnegative polynomials, which is distinct from the cone of sums of squares. Let $\mathbb{R}^A$ denote the space of all real polynomials with support $A$. We describe the boundary of the cone $S \cap \mathbb{R}^A$ as a space stratified in real semi-algebraic varieties. In order to describe the strata, we take a journey through discriminants, polytopes, and triangulations, oriented matroids, and tropical geometry. Based on joint work with Timo de Wolff.

Christian Krattenthaler13.02.1915:30MA 621 Discrete analogues of Macdonald-Mehta integrals
Abstract:

The Mehta integral and its generalisations due to Macdonald originate from random matrix theory, but are as well important objects in the theory of (multi-variable) orthogonal polynomials and in combinatorics. These (now) classical integrals are certain multi-dimensional integrals which - suprisingly? - can be evaluated into closed form product formulae. I shall consider certain discretisations of the Macdonald-Mehta integrals. There are ten families of such discretisations which can be evaluated in closed form. I shall sketch the ideas which go into the proofs of these identities, which come from combinatorics of non-intersecting lattice paths, identities for classical group characters, and a transformation formula for elliptic hypergeometric series, respectively. No prior knowledge of any of these is required to follow the talk as everything will be explained during the talk. This is joint work with Richard Brent and Ole Warnaar.

Deane Yang (NYU Courant)06.02.1916:30MA 406 Information theoretic inequalities and their convex geometric analogues
Abstract:

It will be shown how, using the homogeneous contour integral, information theoretic invariants and inequalities involving entropy, moments, Fisher information can be translated into convex geometric invariants and inequalities.

Johannes Rau (Tübingen)23.01.1916:30MA 621 Tropical patchworking for nodal curves in the plane (joint with Ilia Itenberg and Grigory Mikhalkin)
Abstract:

Given a real algebraic curve in the plane, probably the most elementary questions you can ask are: What is its number of connected components? How are they arranged in the plane? This leads to the porblem of topological classification of such curves which received ongoing attention ever since being included as Hilbert's 16th problem in his famous list from 1900. While most results deal with the case of smooth curves, I will present a classification for a certain type of singular curves of degree 5 in the plane. To construct such curves, we will use a "tropical" version of Viro's patchworking construction which is better suited for the singular case.

Timo de Wolff09.01.1916:30MA 621 Nondegenerate Multistationarity in Small Reaction Networks
Abstract:

Much attention has been focused in recent years on the following algebraic problem arising from applications: which chemical reaction networks, when taken with mass-action kinetics, admit multiple positive steady states? The interest behind this question is in steady states that are stable. As a step toward this difficult question, here we address the question of multiple nondegenerate positive steady states. Mathematically, this asks whether certain families of parametrized, real, sparse polynomial systems ever admit multiple positive real roots that are simple. Our main results settle this problem for certain types of small networks, and our techniques point the way forward for larger networks. This is joint work with Anne Shiu.

Tanka Nath Dhamala (Tribhuvan University)05.12.1816:30MA 406 Flow Models and Solution Strategies for Evacuation Planning Problems
Abstract:

Unavoidable human created or natural disasters worldwide highly demand an efficient and reliable evacuation planning strategy to save the people and property in emergency periods. There exist a variant of mathematical modeling approaches and solution techniques covering from wide range of mathematical fields, engineering and management sciences. Although solution techniques with fluid dynamical equations using differential equations or cell based simulation approaches seek to address the problems more accurately and also taking care of the individual behaviors, they could not handle large scale problems because of high computational costs involved. On the other hand, flow models with different optimization techniques that seek to model the real life with time varying or flow dependent attributes also yield nonlinearity and high computational inefficiency. As a compromise, one can model these problems within the framework of evacuation network optimization which can handle relatively larger size instances with compromised solution quality in discrete time settings. We consider the models in latter approach and illustrate some algorithms that are more interesting theoretically and also from practical view points.
In this talk, we are particularly interested in lane reversal (also a contraflow reconfiguration) techniques that significantly increases the flow values with decreased evacuation time. These problems are computationally challenging and there exist many heuristics in literature and practice, however, they are also polynomially solvable in many cases and investigated analytically recently. We present the strength of these techniques and also give some case examples that demonstrate the relevances of these models.

Milena Wrobel (MPI Leipzig)21.11.1816:30MA 621 On the anticanonical complex
Abstract:

Toric Fano varieties are in one to one correspondence to so called Fano polytopes. The lattice points in the Fano polytope determine the singularity type of the corresponding toric Fano variety and thus allows classification with purely combinatorial methods. For varieties with a torus action of complexity one, i.e. the general torus orbit is of dimension one less than the dimension of the variety, the anticanonical complex has been introduced as a natural generalisation of the toric Fano polytope. We give a sufficient condition on Fano varieties with torus action of arbitrary complexity that admit an anticanonical complex, i.e. a polyhedral complex whose lattice points determine their singularity type. We show that the possibility to apply the anticanonical complex to these varieties is connected to certain properties of their quotients and use this fact to construct first example classes.

Anne Frühbis-Krüger (Leibniz Universität Hannover)14.11.1816:30MA 621 Some massively parallel computations in algebraic geometry
Abstract:

While massively parallel computations are ubiquitous in numerics and simulation, they have rarely ever been thought about in computational algebraic geometry. Already the Gröbner Basis Algorithm, which is the workhorse behind numerous computations, does not have a natural parallelization and thus seems a huge obstacle. But there are tasks in algebraic geometry, which are accessible to a very coarse grained, massively parallel approach due to the local nature of the problem itself. In this talk, I will show a few examples, in which such an approach proved fruitful such as e.g. a smoothness test based on the termination criterion of Hironaka’s resolution of singularities.

Iskander Aliev (Cardiff University)31.10.1816:30MA 406 On the distance to lattice points in knapsack polyhedra
Abstract:

In this talk we will present some recent results on the distance from a vertex of an integer feasible knapsack polyhedron $P$ to its nearest lattice point in $P$ (referred to as a vertex distance). We give a sharp upper bound for the vertex distance that only depends on the maximum norm of the vector $a$. In a randomised setting, we show that the vertex distance for a typical knapsack polyhedron is drastically smaller than the vertex distance that occurs in a worst case scenario. This is a joint work with Martin Henk and Timm Oertel.

Akiyoshi Tsuchiya24.10.1816:30MA 621 Reflexive polytopes arising from (0,1)-polytopes
Abstract:

A (0,1)-polytope is a lattice subpolytope of [0,1]^d. Several classes of (0,1)-polytopes arise from some combinatorial objects and many properties of the (0,1)-polytopes are characterized in terms of the combinatorial objects. In this talk, we introduce construction of reflexive polytopes arising (0,1)-polytopes and discuss their properties. A reflexive polytope is one of the keywords belonging to the current trends on the research of lattice polytopes. In fact, many authors have studied reflexive polytopes from viewpoints of combinatorics, commutative algebra and algebraic geometry. We also present a linear algebraic technique to show a lattice polytope is reflexive and we give a family of reflexive polytopes arising from the edge polytopes of finite simple graphs. This talk is based on joint work with Takahiro Nagaoka.

Marta Panizzut17.10.1816:30MA 621 Introduction to p-adic geometry
Abstract:

In this survey talk we will introduce p-adic fields and more generally non-archimedean valued fields. We will point out that the topology induced by the absolute value is totally disconnected. This make it more difficult to define manifolds and geometric theories over these fields. We will see how Berkovich's approach of analytic spaces deal with these problems.

Leon Zhang29.08.1816:30MA 621 Constructing an enveloping membrane for a min-convex hull
Abstract:

Joswig, Sturmfels, and Yu (2007) describe a correspondence between a min-convex hull in the affine building of SL_d(K) and a tropical convex hull in tropical projective space TP^{d-1}, using a membrane containing the min-convex hull. We describe an algorithm for constructing such a membrane, which gives a bound on the number of points needed to span the tropical convex hull.

Charles Wang22.08.1816:30MA 621 Cluster Algebras and Grassmannians
Abstract:

We will study the interactions of combinatorics and geometry via cluster algebras. We will begin with the simple case of the Grassmannians Gr(2,n), where this connection is completely determined by the type A_n associahedron, corresponding to triangulations of an n+3-gon. Next, we will discuss the case for general Gr(k,n) and the Lagrangian Grassmannians LG(n), where will focus on combinatorial objects called plabic graphs. We will discuss how the cluster structure in these cases gives a method to understand the Newton-Okounkov bodies of these varieties, and give a connection to Khovanskii bases and toric degenerations. Time permitting, we will also the study relation to the tropical Grassmannians and positivity.

Stephan Tillmann18.07.1816:30MA 621 What is the Thurston norm?
Abstract:

Thurston’s norm on (co)homology of a 3-manifold reveals interesting topological properties of the 3-manifold. At the centre of its study is its unit ball, which is a finite polytope. Associated to some of its top dimensional faces are special triangulations of the manifold defined by Agol, called veering triangulations. After a general introduction to these topics, I will outline algorithms developed in collaboration with Daryl Cooper and Will Worden to compute the unit ball, and ask the audience for input on interesting properties of the polytopes that one might want to address.

Marek Kaluba11.07.1816:30MA 621 Non-commutative positivity and property (T)
Abstract:

The underlying theme of the talk is the reduction of the (hard analytic) ques- tion of Kazhdan’s property (T) to an (algebraic, computable) problem of non- commutative optimisation. In this formulation, property (T) is equivalent to the positivity of the element ∆ 2 − λ ∆ in (full) C ∗ -group algebra (where ∆ is the group Laplacian). This problem will serve as a motivation to explore the topic of non-commutative positivity. I will present certain results on positivity for free ∗ -algebras and group al- gebras. It turns out that, due to much richer representation theory of non- commutative objects, the Positivestellensätze in the non-commutative world are much stronger than in the commutative world: the positive cone is in many cases equal to the cone of sums of (hermitian) squares. Moreover one of the characterisations of cones in the “algebraic topology” of ∗ -algebra allows turning a numerical approximation of the the sum of squares decomposition (of ∆ 2 − λ ∆ ) into a mathematical proof of the positivity. I will finish by presenting the very concrete case of the application of the theory to S Aut( F n ), the (special) automorphism group of the free group on five generators. Using Gramm method we formulated The successful execution of the described programme was obstructed by the sheer size of the optimisation problem. To overcome these difficulties we exploited the symmetry of ∆ 2 − λ ∆ and used the theory of representations of finite groups to significantly reduce the complexity of the optimisation problem, wich might be of interest of its own.

Ngoc Tran (UT Austin/Hausdorff Center for Mathematics, Bonn)04.07.1816:30MA 621 A computational approach to tropical semigroups
Abstract:

In many semigroups it is difficult to construct and verify identities. For the semigroups of Tropical uppertriangular matrices, we show that each word has a signature, which is a sequence of polytopes, and two words form an identity if and only if their signatures agree. This leads to fast algorithms for constructing semigroup identities. Our algorithms allow us to disprove conjectures, prove new theorems on the structure of the semigroup, and form new conjectures at the intersection of probability, combinatorics and semigroup theory. In this talk, we will focus on explaining these conjectures from the viewpoint of polyhedral computations. Joint work with Marianne Johnson

Timur Sadykov28.06.1814:15MA 316 Amoebas of multivariate hypergeometric polynomials
Abstract:

Polynomial instances of hypergeometric functions in one and several variables are very diverse. They comprise the classical Chebyshev polynomials of the first and the second kind, the Gegenbauer, Hermite, Jacobi, Laguerre and Legendre polynomials as well as their numerous multivariate analogues.
Despite the diversity of families of hypergeometric polynomials, most of them share the following key properties that justify the usage of the term "hypergeometric":
1. The polynomials are dense (possibly after a suitable monomial change of variables).
2. The coefficients of a hypergeometric polynomial are related through some recursion with polynomial coefficients.
3. For univariate polynomials, there is typically a single representative (up to a suitable normalization) of a given degree within a family of hypergeometric polynomials.
4. All polynomials in the family satisfy a differential equation of a fixed order with polynomial coefficients (or a system of such equations) whose parameters encode the degree of a polynomial.
5. In the case of one dimension, the absolute values of the roots of a classical hypergeometric polynomial are all different (possibly after a suitable monomial change of variables).
6. Many of hypergeometric polynomials enjoy various extremal properties.
In the talk, we will introduce a definition of a multivariate hypergeometric polynomial in several complex variables that is coherent with the properties 1-6 listed above. Namely, with any integer convex polytope P we associate a multivariate hypergeometric polynomial whose set of exponents is P.
The hypergeometric polynomial associated with the polytope P is defined uniquely up to a constant multiple and satisfies a holonomic system of partial differential equations of Horn's type. We prove that under certain nondegeneracy conditions the zero locus of any such polynomial is optimal in the sense of Forsberg-Passare-Tsikh. Generally speaking, this means that the topology of the amoeba of such a polynomial is as complicated as it could possibly be. This property is the multivariate counterpart of the property of having different absolute values of the roots for a polynomial in a single variable.

Christian Stump20.06.1816:30MA 621 Reflection groups and singularity theory
Abstract:

I aim to motivate, as simple as possible and limited by my own understanding, Arnold's problem "Find applications of the complex reflection groups in singularity theory". I start with discussing the connection between the discriminant of a general polynomial in one variable and the realization of the braid group using the braid arrangement. I then intend to give a detailed introduction to reflection groups in rational / real / complex vector spaces, their reflection arrangements, and their discriminants, and in particular discuss the connection to Kleinian singularities associated with symmetry groups of platonic solids and binary polyhedral groups.

Kalina Mincheva (Yale University)13.06.1816:30MA 621 The Picard group of a tropical toric scheme
Abstract:

Through the process of tropicalization one obtains from an algebraic variety $X$ a combinatorial object called the tropicalization of $X$, $trop(X)$, that retains a lot of information about the original variety. Following the work of J. Giansiracusa and N. Giansiracusa, one can endow $trop(X)$ with more structure, to obtain a tropical scheme. Loosely speaking, we consider more equations than the ones needed to determine the tropical variety. We are interested what information about the original variety $X$ is preserved by the tropical scheme $X_\mathbb{T}$ (but possibly not by the tropical variety). In particular, we study the relation between the Picard group of $X$ and $X_\mathbb{T}$. We solve the problem in the case when $X$ is a toric variety.

Jonathan Spreer06.06.201816:30MA 621 Separation-type combinatorial invariants for triangulations of manifolds
Abstract:

In my talk I will propose and discuss a set of combinatorial invariants of simplicial complexes which, in some sense, can be seen as a refinement of the f-vector. The invariants are very elementary and defined by counting connected components and/or homological features of induced subcomplexes.
I will first define these invariants, state some identities they satisfy, and connect them to natural operations on triangulated manifolds and spheres. Then I will present the very natural connjecture that, for a given f-vector, the invariants are maximised for the Billera-Lee-spheres.
This is joint work with Giulia Codenotti and Francisco Santos.

Alperen Erguer30.05.1816:30MA 406 Multihomogenous Nonnegative Polynomials and Sums of Squares
Abstract:

It is due to Blekherman that we now know there are significantly more nonnegative forms than sums of squares for any fixed degree $2d$ and large number of variables $n$. What if we ask the same comparison for polynomials with a prescribed Newton polytope? I will present some general ideas from (modern) convex geometry that handles the case of multihomogeneous polynomials. These results refine the estimates of Blekherman and happens to have some implications in quantum information theory. I will also try to indicate missing ingredient(s) for handling general Newton polytopes, which might be of interest to the lovers of toric geometry and/or Lie algebras.

Travis Scrimshaw29.05.1817:00MA 621 On the Combinatorics of Crystals
Abstract:

In algebra, a crystal base or canonical base is a base of a representation, such that generators of a quantum group or semisimple Lie algebra have a particularly simple action on it. Crystal bases were introduced by Kashiwara (1990) and Lusztig (1990) (under the name of canonical bases).

Grigoris Paouris (Texas A&M University)24.05.1816:15MA 313 The "Small ball" property in high dimensional measures
Abstract:

I will discuss some methods/techniques to prove "small ball probabilities" and I will review some connections with other problems in Asymptotic Geometric Analysis. The emphasis will be on how high-dimensional geometry and convexity is crucial to understand the concentration behavior in the "small ball regime".

Grigoris Paouris (Texas A&M University)23.05.1816:30MA 313 Almost Euclidean section of high-dimensional convex bodies
Abstract:

The celebrated theorem of Dvoretzky states that for any n and $\varepsilon \in (0,1)$ there exists a function $k(n,ε)$ with the property that any n-dimensional symmetric convex body has a k-dimensional section at a distance at most $(1+\varepsilon)$ from the Euclidean ball and moreover $k(n,\varepsilon)$ tends to infinity as $n \to \infty$ for fixed $\varepsilon$. The asymptotic behavior of this function remains an open problem 64 years after Grothendieck proposed it. I will discuss some recent developments on the problem. In particular I will present how the notion of superconcentration is central in the latest improvements. Based on joint work with P. Valettas.

Chris O'Neill (UC Davis)09.05.1816:30MA 621 Computing the delta set of an affine semigroup: a status report
Abstract:

An affine semigroup $S$ is a subset of $\mathbb Z_{\ge 0}^k$ that is closed under vector addition, and a factorization of $a \in S$ is an expression of $a$ as a sum of generators of $S$. The delta set of $a$ is a set of positive integers determined by the 'missing factorization lengths' of $a$, and the delta set of $S$ is the union of the delta sets of its elements. Although the delta set of any affine semigroup is finite, its definition as an infinite union makes explicit computation difficult. In this talk, we explore algebraic and geometric properties of the delta set, and survey the history of its computation for affine semigroups. The results presented here span the last 20 years, ranging from a first algorithm for a small class of semigroups that is impractical for even basic examples, to recent joint work with Garcia-Sanchez and Webb expressing the delta set of any affine semigroup in terms of Groebner bases, and include results from numerous undergraduate research projects.

Vijaylaxmi Trivedi (Tata Institute of Fundamental Research, Mumbai)02.05.1816:30MA 406 Hilbert-Kunz functions and HK density functions
Abstract:

We give a brief survey of Hilbert-Kunz function and its leading coefficient $e_{HK}$ called HK multiplicity, for a commutative Noetherian ring.
In order to study $e_{HK}$ we have introduced a compactly supported continuous function $HKd$ (in the graded set up). This idea of replacing a point ($e_{HK}$) by a function ($HKd$) seems to be an effective technique to handle the notoriously difficult invariant like $e_{HK}$. We apply this theory to projective toric varieties and, as a corollary, get an algebraic characterization of the tiling property of a rational convex polytope. Similarly we define a density function for the second coefficient of a HK function (in toric case). Here we use a refined version of a result by Henk-Linke on the boundedness of the coefficients of rational Ehrhart quasi-polynomials of convex rational polytopes.

Victor Magron (CNRS Grenoble)25.04.1816:30MA 621 On exact polynomial optimization
Abstract:

To compute certificates of nonnegativity, an approach based on sums of squares (SOS) decompositions has been popularized by Lasserre and Parillo.
In the first part of this talk, we consider the problem of finding SOS decompositions of nonnegative univariate polynomials. It is well-known that every non-negative univariate real polynomial can be written as the sum of two polynomial squares with real coefficients. When one allows a weighted sum of finitely many squares instead of a sum of two squares, then one can choose all coefficients in the representation to lie in the field generated by the coefficients of the polynomial. We describe, analyze and compare two algorithms computing such a weighted sums of squares decomposition for univariate polynomials with rational coefficients. - The first algorithm, due to Schweighofer, relies on real root isolation, quadratic approximations of positive polynomials and square-free decomposition but its complexity was not analyzed. We provide bit complexity estimates, both on runtime and output size of this algorithm. They are exponential in the degree of the input univariate polynomial and linear in the maximum bitsize of its complexity. This analysis is obtained using quantifier elimination and root isolation bounds. - The second algorithm, due to Chevillard, Harrison, Joldes and Lauter, relies on complex root isolation and square-free decomposition and has been introduced for certifying positiveness of polynomials in the context of computer arithmetics. Again, its complexity was not analyzed. We provide bit complexity estimates, both on runtime and output size of this algorithm, which are polynomial in the degree of the input polynomial and linear in the maximum bitsize of its complexity. This analysis is obtained using Vieta's formula and root isolation bounds. While the second algorithm is, as expected from the complexity result, more efficient on most of examples, we exhibit families of non-negative polynomials for which the first algorithm is better.
In the second part of this talk, we consider the problem of finding exact sums of squares (SOS) decompositions for certain classes of nonnegative multivariate polynomials, while relying on semidefinite programming (SDP) solvers. - We start by providing a hybrid symbolic-numeric algorithm computing exact rational SOS decompositions for polynomials lying in the interior of the SOS cone. This algorithm computes an approximate SOS decomposition for a perturbation of the input polynomial with an arbitrary-precision SDP solver. An exact SOS decomposition is obtained thanks to the perturbation terms. We prove that bit complexity estimates on output size and runtime are both polynomial in the degree of the input polynomial and simply exponential in the number of variables. This analysis is based on quantifier elimination as well as bounds on the cost of the ellipsoid method and Cholesky's decomposition. - Next, we apply this algorithm to compute exact Polya and Putinar's representations respectively for positive definite forms and polynomials positive over basic compact semialgebraic sets. We compare the implementation of our algorithms with existing methods based on CAD or critical points.
This is joint work with Mohab Safey El Din and Markus Schweighofer.

Ben Smith (Queen Mary University of London)18.04.1816:30MA 621 Matching fields and lattice points of simplicies
Abstract:

An (n,d)-matching field is a collection of matchings such that there is a unique matching for each d-subset of [n]. They naturally arise as minimal matchings of a weighted complete bipartite graph, and can be thought of as the tropical analogue to matroids. They have relationships to multiple combiatorial objects, in particular triangulations of the product of two simplices. In this talk, we will use this relationship to introduce a construction that associates to the matching field a collection of bipartite graphs and a bijection to the lattice points of a scaled simplex. We will then use this construction to prove two outstanding conjectures of Sturmfels and Zelevinsky on matching fields.

Michael Joswig (TU Berlin)11.04.1816:30MA 621 Coxeter groups, BN-pairs, and buildings
Abstract:

Buildings form a fundamental geometric concept which generalize the Coxeter complex of a Coxeter group. The theory was mostly developed by Tits (and Borel) in the 1960s and 1970s. While its origins are in Lie theory one particularly striking application was its contribution to the classification of the finite simple groups (completed around 1980). In this talk (of historical survey type) I will define the three notions in the title and look into one family of examples. In the end I will briefly try to sketch the impact on group theory in general.

Sascha Timme04.04.1816:30MA 621 Fast Computation of Amoebas in low Dimensions
Abstract:

The concept of an amoeba was introduced by Gelfand, Kapranov and Zelevinsky in 1994 to study the relationship between the zero locus of a polynomial and its Newton polytope. Amoebas have a lot of fascinating structural properties. In particular, there exists for each amoeba a tropical hypersurface, called the spine, which is a deformation retract of the amoeba.
In this talk we investigate how the structural properties of amoebas can be used to enable the fast approximation of amoebas in low dimensions as well as to compute the spine of 2-dimensional amoebas. We also present the Julia package Amoebas.jl in which these results are implemented.

Adam Kurpisz28.03.1816:30MA 621 On the hierarchies of relaxations for 0/1 optimization problems
Abstract:

Constructing efficient algorithms for combinatorial optimization problems is a task that requires a lot of knowledge, experience and creativity. The goal of this talk is to present the automatizable hierarchies of algorithms (Lasserre/Sum-of-Squares (SoS), Sherali Adams (SA)) and the recent development in this field, the Sum-of-Nonnegative-Circuit (SoNC) algorithm.
We start with a motivation and a gentle introduction to the hierarchies of relaxations for 0/1 optimization problems. Next we discuss the strength and weaknesses of this approach and present a novel method in this field, the SoNC hierarchy.
Finally, in this talk we show that key results for SOS/SA hierarchy remain valid for SoNC hierarchy. More precisely we show that for a polynomial optimization problem over the $n$-variate boolean hypercube with constraints of degree $d$, the SoNC hierarchy at level $n+d$ converges to the convex hull of integral solutions.

Francisco Criado07.02.1816:30MA 621 Packing algorithms applied to linear programming
Abstract:

The Yamnistsky-Levin algorithm (1982) is a variation of the ellipsoid method that uses a simplex instead of an ellipsoid. Unlike the ellipsoid method, it does not require square root computations, and it still runs in weakly polynomial time. However, its running time is still not practical. We introduce a variation of this method that examines a subset of cutting planes, and uses the Multiplicative Weights framework developed by Plotkin, Shmoys and Tardos for packing linear programs. We will show how our algorithm improves the original YL algorithm for a simplification of the problem, and what questions remain open to give a complete proof of convergence.

Romanos Malikiosis24.01.1816:30MA 406 Fuglede's spectral set conjecture on cyclic groups
Abstract:

Fuglede's conjecture (1974) states that a bounded measurable subset in $\mathbb{R}^d$ accepts an orthogonal basis of exponential functions (i.e. it is spectral) if and only if it tiles the space with a discrete set of translations. This conjecture turned out to be false by Tao's counterexample in 2003. Using Tao's ideas, counterexamples in finite Abelian groups such as $\mathbb{Z}_N^d$ can be lifted to counterexamples in $\mathbb{R}^d$, thus shifting the interest on this conjecture to this setting in recent years. This has been successful for $d\geq3$, but the conjecture is still open for $d=1,2$.
Some recent results in the cyclic group setting will be presented in this talk, which are connected to the work of Coven-Meyerowitz and Laba on tiling subsets of $\mathbb{Z}$, as well as the structure of vanishing sums of roots of unity. This is joint work with Mihalis Kolountzakis & work in progress.

Linda Kleist20.12.1716:30MA 621 Rainbow cycles in flip graphs
Abstract:

The vertices of flip graph are combinatorial or geometric objects, and its edges link two of these objects whenever they can be obtained from one another by an elementary operation called a flip. With each edge, we associate the type of a flip (thought of as a color) and seek for r-rainbow cycles, i.e., cycles where every flip type occurs exactly r times.
For instance, the flip graph of triangulations has as vertices all triangulations of a convex n-gon, and an edge between any two triangulations that differ in exactly one edge. An r-rainbow cycle in this graph is a cycle in which every inner edge of the triangulation appears exactly r times.
In this talk we investigate the existence of rainbow cycles in some of the following flip graphs of triangulations of a convex n-gon, plane trees on a set of n points, non-crossing perfect matchings on points in convex position, permutations of [n], and the flip graph of k-element subsets of [n].
The talk is based on joint work with Stefan Felnser, Torsten Mütze and Leon Sering.

Franz Schuster (TU Wien)06.12.1716:30MA 406 Affine vs. Euclidean Sobolev inequalities
Abstract:

In this talk we explain how every even, zonal measure on the Euclidean unit sphere gives rise to a sharp Sobolev inequality for functions of bounded variation which directly implies the classical Euclidean Sobolev inequality. The strongest member of this large family of inequalities is shown to be the only affine invariant one among them – the affine Zhang-Sobolev inequality. We discuss in some detail the geometry behind these analytic inequalities and also relate our new Sobolev inequalities to the sharp Gromov-Gagliardo-Nirenberg Sobolev inequality for general norms and discuss further improvements of special cases.

Gennadiy Averkov (OvGU Magdeburg)29.11.1716:30MA 406 Latest news on Hensley's conjecture
Abstract:

The talk is about the maximum volume of d-dimensional lattice polytopes with a fixed positive number of interior lattice points. Several researchers conjectured that the maximum is attained on a nice family of polytopes arising from the so-called Sylvester sequence. I will report on the recent progress on Hensley's conjecture. This is joint work with Benjamin Nill and Jan Krümpelmann.

Didier Henrion (LAAS-CNRS Univ Toulouse, FR and Czech Tech Univ Prague, CZ) 22.11.1716:30MA 621 Convergence rates of moment-sum-of-squares hierarchies for volume approximation of semialgebraic sets
Abstract:

Moment-sum-of-squares hierarchies of semidefinite programs can be used to approximate the volume of a given compact basic semialgebraic set K. The idea consists of approximating from above the indicator function of K with a sequence of polynomials of increasing degree d, so that the integrals of these polynomials generate a convergence sequence of upper bounds on the volume of K. In this talk we show how we could derive an asymptotic rate of convergence for this approximation scheme. Joint work with Milan Korda, see arXiv:1609.02762.

Henning Seidler15.11.1716:30MA621 Circuit Polynomials for Simplex Newton Polytopes
Abstract:

Finding the minimum of a multivariate real polynomial is a well-known hard problem with various applications. We present an implementation to approximate such lower bounds via sums of non-negative circuit polynomials (SONCs). We provide a test-suite, where we compare our approach, using different solvers, with several solvers for sums os squares (SOS), including sostools and gloptipoly. It turns out that the circuit polynomials yield bounds competitive to SOS in several cases, but using much less time and memory.

Samuli Leppänen (Dalle Molle Institute for Artificial Intelligence Research)08.11.1716:30MA621 Some integrality gap results for the 0/1 SoS Hierarchy
Abstract:

In this talk we present the SoS hierarchy in the context of 0/1 optimization along with some of our recent integrality gap/lower bound results. We introduce the relevant concepts and give a brief derivation of the hierarchy. As for our results, we characterize the possible gap instances on the round n-1 of the hierarchy. Then we show an unbounded integrality gap after nonconstant number of rounds for a problem that admits a polynomial time algorithm. Finally we present a simplification of the positive semidefiniteness constraints when a high degree of symmetry can be assumed, and some applications to integrality gaps and lower Bounds.

Daryl Cooper 13.09.1716:30MA621 Limits of Algebraic varieties: towards a continuous Nullstellansatz
Abstract:

The map that sends a polynomial ideal to an algebraic variety in complex affine space is not continuous with respect to the obvious topology on the domain. However it is continuous on the closure of the set of ideals generated by polynomials of degree at most d. Moreover the closure of this subspace is compact. This is work in progress, and is joint with Ricky Demer.

Dr. Iskander Aliev (Cardiff, Wales)05.09.1716:30MA 406 Sparse solutions to the systems of linear Diophantine equations
Abstract:

We present structural results on sparse nonnegative integer solutions to underdetermined systems of linear equations.
Our proofs are algebraic and number theoretic in nature and make use of Siegel's Lemma and classical tools from the Geometry of Numbers.
These results have some interesting consequences in discrete optimisation.

Marta Panizzut30.08.1716:30MA 621 The hunt for K3 polytopes
Abstract:

The connected components of the complement of a tropical hypersurface are called regions, and they are convex polyhedra. A smooth tropical quartic surface of genus one has exaclty one bounded region. We say that a 3- dimensional polytope is a K3 polytope if it arises as the bounded region of a smooth tropical quartic surface. In a joint project with Gabriele Balletti, we are investigating properties of K3 polytopes. In this talk I will report on the progress of this work.

Timo de Wolff23.08.1716:30MA 621 Intersections of Amoebas
Abstract:

Georg Loho16.08.1716:30MA 621 Monomial Tropical Cones for Multicriteria Optimization
Abstract:

We introduce a special class of tropical cones which we call 'monomial tropical cones'. They arise as a crucial tool in the description of discrete multicriteria optimization problems. We employ them to derive an algorithm for computing all nondominated points. Furthermore, monomial tropical cones are intimately related with monomial ideals. We sketch directions for further work. This is based on joint work with Michael Joswig.

Johannes Hofscheier19.07.1716:30MA 621 A Combinatorial Smoothness Criterion for Spherical Varieties
Abstract:

In this talk we will present algorithms to check smoothness for the class of spherical varieties which contains those of toric varieties, flag varieties and symmetric varieties, and which forms a remarkable class of algebraic varieties with an action by an algebraic group having an open dense orbit. In the toric case there is a well-known simple combinatorial smoothness criterion whereas in the spherical case Brion, Camus and Gagliardi have shown smoothness criteria for spherical varieties which either are rather involved or rely on certain classification results. We suggest a purely combinatorial smoothness criterion by introducing a rational invariant which only depends on the combinatorics of the spherical variety. We have a conjectural inequality this invariant should satisfy where the equality case would imply that the spherical variety has a toric torus action. Our conjecture would also imply the generalized Mukai conjecture for spherical varieties. We complete our talk by summarizing in which cases the above mentioned approach is known to be true. This is joint work with Giuliano Gagliardi.

Sinai Robins (University of São Paulo)06.07.1716:30MA 406 The Ehrhart quasipolynomials of polytopes that come from trivalent graphs, and a discrete version of Hilbert's 3rd problem for the unimodular group
Abstract:

A graph all of whose nodes have degree $1$ or $3$ is called a $\{1,3\}$-graph. Liu and Osserman associated to each $\{1, 3\}$-graph a polytope. They studied these polytopes and their Ehrhart quasi-polynomials. We prove a conjecture of Liu and Osserman stating that the associated polytopes of all connected $\{1,3\}$-graphs with the same number of nodes and edges have the same Ehrhart quasi-polynomial. We also present some structural properties of these polytopes and we show a relation between them and the well-known metric polytopes. This study is related to a question of Hasse and McAllister on a discrete version of Hilbert's 3rd problem for the unimodular group.
This is joint work with Cristina Fernandez, José C. de Pina, and Jorge Luis Ramírez Alfonsín.

Matthias Lenz28.06.1716:30MA 621 On powers of Plücker coordinates and representability of arithmetic matroids
Abstract:

Given $k\in \mathbb{R}_{\ge 0}$ and a vector $v$ of Plücker coordinates of a point in the real Grassmannian, is the vector obtained by taking the $k$th power of each entry of $v$ again a vector of Plücker coordinates? We will show that for $k\neq 1$, this is true if and only if the corresponding matroid is regular. Similar results hold over other fields. We will also describe the subvariety of the Grassmannian that consists of all the points that define a regular matroid.
An arithmetic matroid is a matroid equipped with a function that assigns a multiplicity (a positive integer) to each subset of the ground set. We will discuss a discrete version of the problem described above that deals with the representability of the arithmetic matroid obtained by taking the $k$th power of the multiplicity function. This setting is motivated by some combinatorial questions on CW complexes.

Jean-Philippe Labbé / Michael Joswig21.06.1716:30MA 621 polymake/sage
Abstract:

Jean-Philippe will give an introduction to the new polymake interface in sage. Michael will report basic design principles underlying polymake. This is followed by a common coding session and beer.

Héctor Andrade Loarca14.06.1716:30MA 621 Fast Multidimensional Signal Processing with Shearlab.jl.
Abstract:

We live in the age of data, huge amount of Data its been generated and acquired everyday in different forms and flavors. One would like to have a technique to store and process optimally this data; this is possible since the relevant information in almost all data found in typical applications is sparse due the high correlation of its elements. The challenge will lie in the search of appropriate dictionary that can represent optimally this information. Along the history very talented scientist have proposed different signal transforms based on certain representation dictionaries, starting with the Fourier Transform and Short Time Fourier Transform; in 1980s the wavelet transform was proposed representing a breakthrough in one dimensional signal representation, with the ability to not just optimally represent the data but also capture certain singularities, regularities and other features; the flaw of the wavelets transforms is its lack of directional sensitivity which does not aloud it to represent optimally multidimensional singularities like curves that are predominant in general multidimensional signals (for instance images and videos). The Shearlet transform is a product of almost 10 years of research on sparsifying transform with directional sensitivity that attains the optimal best N-term approximation error, it was proposed by G. Kutyniok, D. Labate and K Guo in 2015 and since then it's been known to be the best of its type.
In this talk I will explain the upsides and downsides of the already mentioned transforms, why the shearlet transform is great solution for anisotropic representation of multidimensional signals, how can we implement wavelet and shearlet transform in Julia, and I will show you some applications and demos of the Shearlet Transform Library that I implemented with Professor Gitta Kutyniok based on the matlab version developed by her group two years ago; I will also explain why Julia is the best option to implement algorithms in Signal and Image Processing and show some benchmarks that show its great performance.

Hiroshi Hirai31.05.1716:30MA 621 Maximum vanishing subspace problem, CAT(0)-space relaxation, and block-triangularization of partitioned matrix
Abstract:

In this paper, we address the following algebraic generalization of the bipartite stable set problem. We are given a block-structured matrix (partitioned matrix) $A=(A_{\alpha\beta})$, where $A_{\alpha\beta}$ is an $m_{\alpha}$ by $n_{\beta}$ matrix over field F for $\alpha=1,2,\ldots,\mu$ and $\beta=1,2,\ldots,\nu$. The maximum vanishing subspace problem (MVSP) is to maximize $\sum_{\alpha}\mbox{dim}X_{\alpha}+\sum_{\beta}\mbox{dim}X_{\beta}$ over vector subspaces $X_{\alpha} \subseteq F^{m_{\alpha}}$ for $\alpha=1,2,\ldots,\mu$ and $Y_{\beta}\subseteq F^{n_{\beta}}$ for $\beta=1,2,\ldots,\nu$ such that each $A_{\alpha\beta}$ vanishes on $X_{\alpha}\times Y_{\beta}$ when $A_{\alpha\beta}$ is viewed as a bilinear form $F^{m_{\alpha}}\times F^{n_{\beta}}\rightarrow F$. This problem arises from a study of a canonical block-triangular form of $A$ by Ito, Iwata, and Murota (1994). We prove that MVSP can be solved in polynomial time. Our proof is a novel combination of submodular optimization on modular lattice and convex optimization on CAT(0)-space. We present implications of this result on block-triangularization of partitioned matrix.

Ted Bisztriczky (University of Calgary)31.05.1716:30MA 406 Erdos-Szekeres type theorems for planar convex sets
Abstract:

A family $\mathcal{F}$ of sets is in convex position if none of its members is contained in the convex hull of the union of the others. The members of $\mathcal{F}$ are ovals (compact convex sets) in the plane that have a certain property. An Erdos-Szekeres type theorem concerns the existence, for any integer $n\geq 3$, of a smallest positive integer $N(n)$ such that if $|\mathcal{F}|≥N(n)$ then there are $n$ ovals of $\mathcal{F}$ in convex position.
In this talk, I survey some known theorems, introduce a new one based upon work with Gabor Fejes Toth and examine the relation between $N(n)$ and Ramsey numbers of the type $R_k(n_1,n_2)$.

Dimitrios Dais (University of Crete)29.05.1717:00MA 406 Toric log del Pezzo surfaces with a unique singularity
Abstract:

The toric log del Pezzo surfaces are constructed by means of the so-called LDP-lattice polygons. In the talk it will be explained how one classifies the subclass of surfaces of this kind which have a unique singularity.

Richard Gardner (Western Washington University)17.05.1716:30MA 406 Open problems in Geometric Tomography
Abstract:

This talk will focus on open problems in Geometric Tomography, which aims to retrieve information about a geometric object (such as a convex body, star body, finite set, etc.) from data concerning its intersections with planes or lines and/or projections (i.e., shadows) on planes or lines. The problems, which span nearly a hundred years of mathematics, are diverse. Many have a common thread, however, since they are linked to various integral transforms: the X-ray transform, divergent beam transform, circular Radon transform, cosine transform, or spherical Radon transform.
The talk will be illustrated by plenty of pictures.

Michael Joswig03.05.1716:30MA 621 Computing Invariants of Simplicial Manifolds
Abstract:

This is a brief survey on algorithms for computing basic algebraic invariants such as homology, cup products, and intersection forms.

Romanos Malikiosis26.04.1716:30MA 406 Formal duality in finite cyclic groups
Abstract:

Numerical computations by Cohn, Kumar, and Schürmann in energy minimizing periodic configurations of density $\rho$ and $1/\rho$ revealed an impressive kind of symmetry, the so–called formal duality. Formal dual subsets of $\mathbb{R}^n$ satisfy a generalized version of Poisson summation formula, and it is conjectured that the only periodic subsets of $\mathbb{R}$ of density $1$ possessing a formal dual subset, are $\mathbb{Z}$ and $2\mathbb{Z}\cup(2\mathbb{Z}+\frac12)$.
In this talk, we will present recent progress on this conjecture by the speaker, utilizing several tools from different areas of mathematics, such as (a) the field descent method by Bernhard Schmidt, used chiefly on the circulant Hadamard matrix conjecture, (b) the 'polynomial method' by Coven & Meyerowitz used in the characterization of sets tiling $\mathbb{Z}$ or $\mathbb{Z}_N$, and (c) basic arithmetic of cyclotomic fields.

Manuel Radons12.04.1716:30MA 621 Piecewise linear methods in nonsmooth optimization
Abstract:

Several techniques in numerical analysis, e.g. Newton's methods and ODE solvers, are based on local linear approximations of a smooth function $f: \mathbb R^n\rightarrow \mathbb R^n$. If $f$ is piecewise smooth such approximations may be arbitrarily bad near nondifferentiabilites. Piecewise linear approximations -- or, briefer, piecewise linearizations -- restore the structural correspondence between approximation and underlying function. We give an overview of the generalized numerical methods based on piecewise linearizations and their properties, e.g. convergence results, as well as the techniques used in their investigation, which include degree theory for piecewise affine functions and nonsmooth analysis.

Philipp Jell05.04.1716:30MA 621 Differential forms on Berkovich spaces and their relation to tropical geometry
Abstract:

Takayuki Hibi (Osaka University)29.03.1716:30MA 621 Order Polytopes and Chain Polytopes
Abstract:

Given a finite partially ordered set P, we associate two poset polytopes, viz, the order polytope O(P) and the chain polytope C(P). In my talk, after reviewing fundamental materials on O(P) and C(P), the question when O(P) and C(P) are unimodularly equivalent will be discussed. Then, in the frame of Gröbner bases, various reflexive polytopes arising from O(P) and C(P) will be presented. Finally, some questions and conjectures will be summarized. No special knowledge will be required to understand my talk.

Lucía López de Medrano (UNAM Cuernavaca)22.03.1717:00MA 621 On the genus of tropical curves
Abstract:

Felipe Rincón (University of Oslo)22.03.1716:15MA 621 Tropical Ideals
Abstract:

Skip Jordan22.03.1715:30MA 621 Parallel Vertex and Facet Enumeration with mplrs
Abstract:

We introduce mplrs, a new parallel vertex/facet enumeration program based on the reverse-search code lrs. The implementation uses MPI and can be used on single machines, clusters and supercomputers. We describe the budgeted parallel tree search implemented in mplrs and compare performance with other sequential and parallel programs for vertex/facet enumeration. In some instances, mplrs achieves almost linear scaling with more than 1000 cores. The approach used in mplrs can be easily applied to various other problems. This is joint work with David Avis.

Alex Fink22.02.1716:30MA 621 The characteristic polynomial two ways
Abstract:

The theory of hyperplane arrangements and matroids derives great utility from the application of algebraic and algebro-geometric methods. The characteristic polynomial often appears in familiar guise in these methods, as an enumerator of the no broken circuit sets. The characteristic polynomial also appears, on the face of it unrelatedly, in the recent magisterial resolution of Rota's conjecture by Huh, Katz, and Adiprasito. In joint work with David Speyer and Alex Woo we explain how these two manifestations are related after all.

Akiyoshi Tsuchiya08.02.1716:30MA 621 Gorenstein simplices and the associated finite abelian groups
Abstract:

A lattice polytope is a convex polytope each of whose vertices has integer coordinates. It is known that a lattice simplex of dimension $d$ corresponds to a finite abelian subgroup of $(\mathcal{R}/\mathcal{Z})^{d+1}$. Conversely, given a finite abelian subgroup of $(\mathcal{R}/\mathcal{Z})^{d+1}$ such that the sum of all entries of each element is an integer, we can obtain a lattice simplex of dimension $d$. In this talk, we discuss a characterization of Gorenstein simplices in terms of the associated finite abelian groups. Gorenstein polytopes are of interest in combinatorial commutative algebra, mirror symmetry and tropical geometry. In particular, we present complete characterizations of Gorenstein simplices whose normalized volume equal $p$, $p^2$ and $pq$, where $p,q$ are prime integers.

Robert Löwe25.01.1716:30MA 621 Secondary fans of a punctured Riemann surface
Abstract:

The secondary fan of a finite point configuration in $R^n$ stratifies the space of height functions by the combinatorial types of regular subdivisions. Now given a punctured Riemann surface, similar techniques yield a polyhedral fan whose cones correspond to horocyclic Delaunay tessellation in the sense of Penner's convex hull construction. The purpose of the talk is to give an introduction to this topic and the corresponding problems that arise naturally.

Eva Maria Feichtner (Universität Bremen)18.01.1716:30MA 406 A Leray model for Orlik-Solomon algebras
Abstract:

Although hyperplane arrangement complements are rationally formal, we note that they have non-minimal rational (CDGA) models which are topologically and combinatorially significant. We construct a family of CDGAs which interpolates between the Orlik-Solomon algebra and the cohomology algebras of arrangement compactifications. Our construction is combinatorial and extends to all matroids, regardless of their (complex) realizability.
This is joint work with Christin Bibby and Graham Denham.

Benjamin Schröter04.01.1716:30MA 621 Fundamental Polytopes of Metric Trees via Hyperplane Arrangements
Abstract:

In this talk I will present a summary of the recent paper 'Fundamental Polytopes of Metric Trees via Hyperplane Arrangements' (arXiv:1612.05534) of Emanuele Delucchi and Linard Hossly. In this paper they develop a formula for the f-vector of the fundamental polytope of a finite metric space and its dual the Lipschitz polytope.

Georg Loho04.01.1717:15MA 621 Slicing and Dicing Polytopes
Abstract:

I present the recent work 'Slicing and dicing polytopes' (arXiv:1608.05372) by Patrik Norén on cellular resolutions. I introduce diced and sharp polytopes which are necessary for the construction and give a brief introduction to cellular resolutions. The main result, introducing a new class of polyhedral subdivisions which support cellular resolutions, is illustrated along some examples.

Marta Panizzut26.10.1613:30MA 621 Linear systems on metric graphs, gonality sequence and lifting problems
Abstract:

A combinatorial theory of linear systems on graphs and metric graphs has been introduced in analogy with the one on algebraic curves. The interplay is given by the Specialization Lemma. Let $X$ be a smooth curve over the field of fractions of a complete discrete valuation ring and let $\mathfrak{X}$ be a strongly semistable regular model of $X$. It is possible to specialize a divisor on the curve to a divisor on the dual graph of the special fiber of $\mathfrak{X}$; through this process the rank of the divisor can only increase. The complete graph $K_d$ pops up if we take a model of a smooth plane curve of degree d degenerating to a union of d lines. Moreover omitting edges from $K_d$ can be interpreted as resolving singularities of a plane curve. In this talk we present some results on linear systems on complete graphs and complete graphs with a small number of omitted edges, and we will compare them with the corresponding results on plane curves. In particular, we compute the gonality sequence of complete graphs and the gonality of graphs obtained by omitting edges. We explain how to lift these graphs to curves with the same gonality using models of plane curves with nodes and harmonic morphisms. This is partially a joint work with Filip Cools.

Fei Xue (BMS)19.10.1616:30MA 406 On Lattice Coverings by Simplices
Abstract:

By studying the volume of a generalized difference body, this talk presents the first nontrivial lower bound for the lattice covering density by $n$-dimensional simplices.

Ngoc Tran05.10.1614:45MA 621 Tropical geometry and mechanism design
Abstract:

How to ensure an outcome based on collective decisions is 'better for all' when a) everyone acts in their personal interest only, and b) we do not know the exact 'motives' of each person? Crudely, this is the central problem in mechanism design, a branch of economics. In this talk, I show how insights from tropical geometry can solve such problems.

Thomas Kahle05.10.1613:30MA 621 The geometry of rank-one tensor completion
Abstract:

tba

André Wagner28.09.1616:30MA 621 Veronesean almost binomial almost complete intersections
Abstract:

The second Veronese ideal I_n contains a natural complete intersection J_n generated by the principal 2-minors of a symmetric (n × n)-matrix. In this talk I show, how to determine the subintersections of the primary decomposition of J_n where one intersectand is omitted. These subintersections can be described via combinatorial method and yield interesting insights into binomial ideals. This talk is based on joint work with Thomas Kahle.

Laura Silverstein (TU Wien)27.07.1616:30MA 406 Tensor Valuations on Lattice Polytopes
Abstract:

A classification of symmetric tensor valuations on lattice polytopes in $\mathbb{R}^n$ that intertwine the special linear group over the integers is established for the cases in which the rank of the tensor is at most $n$. The scalar-valued case was classified by Betke and Kneser where it was shown that the only such valuations are the coefficients of the Ehrhart polynomial. Extending this result, the coefficients of the discrete moment tensor form a basis for the symmetric tensor valuations.

Apostolos Giannopoulos (University of Athens)20.07.1616:30MA 406 Inequalities about sections and projections of convex bodies
Abstract:

We discuss lower dimensional versions of the slicing problem and of the Busemann-Petty problem, both in the classical setting and in the generalized setting of arbitrary measures in place of volume. We introduce an alternative approach which is based on the generalized Blaschke-Petkantschin formula, on asymptotic estimates for the dual affine quermassintegrals and on some new Loomis-Whitney type inequalities in the spirit of the uniform cover inequality of Bollobas and Thomason.

Gerassimos Barbatis (University of Athens)13.07.1616:30MA 406 On the Hardy constant of some non-convex planar domains
Abstract:

The Hardy constant of a simply connected domain $\Omega\subset\mathbb{R}^2$ is the best constant for the inequality $\int_\Omega |\nabla u|^2 dx \geq c\int_\Omega \frac{u^2}{\operatorname{dist}(x,\partial\Omega)^2} dx, \quad u\in C_c^\infty(\Omega).$ After the work of Ancona where the universal lower bound 1/16 was obtained, there has been a substantial interest on computing or estimating the Hardy constant of planar domains. In this talk we determine the Hardy constant of an arbitrary quadrilateral as well as of some other planar domains (joint work with Achilles Tertikas).

Matthew Trager15.06.1616:30MA 621 Geometric models for computer vision
Abstract:

The goal of computer vision is to recover real-world information, either semantic (e.g., object recognition) or geometric (3D reconstruction), from sets of photographs or videos. In a broad sense, my research aims at investigating the fundamental geometric models, both synthetic and analytic, that can be used to describe shapes, cameras, and image contours, in processes of visual inference. In this talk, I will present some properties of 'silhouettes' that are obtained as projections of objects in space. I will also discuss some ongoing work that recasts traditional multi-view vision in terms of the Grassmannian of lines in P^3. This is joint work with Jean-Charles Faugere, Xavier Goaoc, Martial Hebert, Jean Ponce, Mohab Safey El Din and Bernd Sturmfels.

Axel Flinth18.05.1616:30MA 406 High Dimensional Geometry in Compressed Sensing
Abstract:

The main aim of compressed sensing is to recover a low-dimensional object (e.g. a sparse vector, a low-rank matrix, ...) from few linear measurements. Many algorithms for this task (e.g. Basis Pursuit, nuclear norm-minimization) consists of minimizing a structure-promoting function $f$ over the set of possible solutions.

An elegant approach to finding recovery guarantees of such programs relies on high-dimensional geometry of convex cones. The techniques were developed relatively recently, but have quickly gained popularity. In the first half of this talk, this approach will be presented in relative high detail.

In the second half of the talk, we will discuss the connection between geometry and stability of compressed sensing algorithms. In particular, we will present a new geometric criterion on $A$ implying stability both with respect to model inexactness of the signal as well as to additive noise in the measurements.

Amanda Cameron04.05.1616:30MA 621 A lattice point counting generalisation of the Tutte polynomial
Abstract:

The Tutte polynomial for matroids is not directly applicable to polymatroids. For instance, deletion-contraction properties do not hold. We construct a polynomial for polymatroids which behaves similarly to the Tutte polynomial of a matroid, and in fact contains the same information as the Tutte polynomial when we restrict to matroids. This polynomial is constructed using lattice point counts in the Minkowski sum of the base polytope of a polymatroid and scaled copies of the standard simplex. We also show that, in the matroid case, our polynomial has coefficients of alternating sign, with a combinatorial interpretation closely tied to the Dawson partition.

Paul Breiding27.04.1616:30MA 621 The spectral Atheory of tensors
Abstract:

The spectral theory of tensors aims at generalizing the concept of eigenvalues and eigenvectors of matrices to higher dimensional arrays. In this talk I will focus on the definition of E-eigenvalues and Z-eigenvalues given by Qi. After giving the definition itself I will explain various applications, give the higher dimensional equivalent of the characteristic polynomial and talk about the number of eigenvalues of both real and complex tensors. The last part of the talk will be about an algorithm to compute eigenvalues of tensors using homotopy methods and the complexity of this algorithm.

Shiri Artstein-Avidan (Tel Aviv University)27.04.1611:00MA 406 On Godbersen’s conjecture and related inequalities
Abstract:

-

Stefan Weltge (Otto-von-Guericke Universität Magdeburg)20.04.1616:30MA 406 Tight bounds on discrete quantitative Helly numbers
Abstract:

Given a subset S of R^n, let c(S,k) be the smallest number t such that whenever finitely many convex sets have exactly k common points in S, there exist at most t of these sets that already have exactly k common points in S. For S = Z^n, this number was introduced by Aliev et al. [2014] who gave an explicit bound showing that c(Z^n,k) = O(k) holds for every fixed n. Recently, Chestnut et al. [2015] improved this to c(Z^n,k) = O(k (log log k)(log k)^{-1/3} ) and provided the lower bound c(Z^n,k) = Omega(k^{(n-1)/(n+1)}). We provide a combinatorial description of c(S,k) in terms of polytopes with vertices in S and use it to improve the previously known bounds as follows: We strengthen the bound of Aliev et al. [2014] by a constant factor and extend it to general discrete sets S. We close the gap for Z^n by showing that c(Z^n,k) = Theta(k^{(n-1)/(n+1)}) holds for every fixed n. Finally, we determine the exact values of c(Z^n,k) for all k <= 4.

Anna Lena Birkmeyer16.03.1616:30MA 621 Realizability of Tropical Hypersurfaces in Matroid Fans
Abstract:

In tropical geometry, an important aim is to understand which tropical varieties arise as tropicalizations of algebraic varieties. We investigate this question in a relative setting: Given a matroid fan F coming from a linear space W, we ask if a tropical hypersurface in F is the tropicalization of an algebraic subvariety of W. We present an algorithm able to decide for any tropical hypersurface in F if it is realizable in W. Moreover, we use this algorithmic approach to describe the structure of the realization space of a tropical hypersurface H in F, i.e. the space of algebraic subvarieties of W tropicalizing to H, and show that the space of all realizable tropical hypersurfaces in F is an abstract polyhedral set.

Martin Genzel02.03.1616:30MA 406 Convex Recovery of Structured Signals from Non-Linear Observations
Abstract:

In this talk, we study the problem of estimating a structured signal $x_0\in\mathbb{R}$ linear Gaussian observations. Supposing that $x_0$ belongs to a certain convex subset $K\subset\mathbb{R}$ we will see that an accurate recovery is possible as long as the number of observations exceeds the effective dimension of $K$, which is a common measure for the complexity of signal classes. Interestingly, it will turn out that the (possibly unknown) non-linearity of our model affects the error rate only by a multiplicative constant. This achievement is based on recent works by Yaniv Plan and Roman Vershynin, who have suggested to treat the non-linearity rather as noise which perturbs a linear measurement process. Using the concept of restricted strong convexity, we show that their results for the generalized Lasso can be extended to a fairly large class of convex loss functions. This is especially appealing for practical applications, since in many real-world scenarios, adapted loss functions empirically perform better than the classical square loss. To this end, the presented results provide a unified and general framework for signal reconstruction in high dimensions, covering various challenges from the fields of compressed sensing, signal processing, and statistical learning.

Mihalis Kolountzakis (University of Crete)03.02.1616:30MA 406 Periodicity for tilings and spectra
Abstract:

We will talk about periodicity (and structure, more generally) in the study of tilings by translation, where the tile is a set or a function in an Abelian group, and also in the study of spectra of sets (sets of characters which form an orthogonal basis for L^2 of the set). There are connections to harmonic analysis, number theory, combinatorics and computation, and these make this subject so fascinating. Starting from the Fuglede conjecture, now disproved in dimension at least 3, which would connect tilings with spectra, we will go over cases where periodicity always holds, cases where it is optional and cases where it's never true, in one dimension (most positive results) and higher dimension (most interesting questions).

Simon Hampe20.01.1616:30MA 621 Matroids over hyperfields
Abstract:

This talk is a summary of the very recent paper by Matthew Baker of the same title (http://arxiv.org/pdf/1601.01204.pdf). Various flavours of ''matroids with additional structure'', such as valuated and oriented matroids have been around for quite a while, with often very little connection between the different matroid species. Matroids over hyperfields are a generalization of all those concepts - thus allowing a unified treatment. In this talk I will first give a short introduction to hyperfields. I will then define what matroids over hyperfields are, give examples and discuss generalizations of familiar matroid operations such as duality and minors.

Silouanos Brazitikos (University of Athens)13.01.1616:30MA 406 Quantitative versions of Helly's theorem
Abstract:

We provide a new quantitative version of Helly's theorem: there exists an absolute constant$\alpha >1$with the following property: if$\{P_i: i\in I\}$is a finite family of convex bodies in${\mathbb R}^n$with${\rm int}\left (\bigcap_{i\in I}P_i\right)\neq\emptyset$, then there exist$z\in {\mathbb R}^n$,$s\ls \alpha n$and$i_1,\ldots i_s\in I$such that \begin{equation*} z+P_{i_1}\cap\cdots\cap P_{i_s}\subseteq cn^{3/2}\left(z+\bigcap_{i\in I}P_i\right), \end{equation*} where$c>0$is an absolute constant. This directly gives a version of the 'quantitative' volume and diameter theorem of > B\'{a}r\'{a}ny, Katchalski and Pach, with a polynomial dependence on the dimension.

Kristin Shaw06.01.1616:30MA 621 What is Étale cohomology?
Abstract:

Wished for by Weil and defined by Grothendieck, Étale cohomology is to varieties over fields of finite characteristic what usual cohomology is to complex or real algebraic varieties when they are equipped with the analytic, respectively Euclidean topology. This very short introduction will motivate and try to explain the basic ingredients of Étale cohomology. Throughout I will make analogies to the complex and real situations and stick to simple examples in hopes to provide some intuition into this deep theory.

Benjamin Schröter02.12.1516:30MA 621 The degree of a tropical basis
Abstract:

In this talk I will present my work with Michael Joswig. I will give an explicit bound on the degree of a tropical basis. Our result is derived from the algorithm of Bogart, Jensen, Speyer, Sturmfels and Thomas that computes a tropical variety via Groebner bases and saturation. Furthermore I will give examples that illustrate the difference between tropical and Groebner bases.

Bernardo González Merino (TU München)18.11.1516:30MA 406 On the Minkowski measure of symmetry
Abstract:

The Minkowski measure of symmetry s(K) of a convex body K, is the smallest positive dilatation of K containing a translate of -K. In this talk we will explain some of its basic properties in detail.

Afterwards, we will show how s(.) can be used to strengthen, smoothen, and join different geometric inequalities, as well as its connections to other concepts such as diametrical compleness, Jung's inequality, or Banach-Mazur distance.

André Wagner04.11.1516:30MA 621 Introduction to singular value decomposition
Abstract:

In this short talk I will give a brief introduction to singular value decomposition, some of it's applications and efficient ways to compute it.

Jonathan Spreer28.10.1516:30MA 621 Algorithms and complexity for Turaev-Viro invariants
Abstract:

The Turaev-Viro invariants are a powerful family of topological invariants for distinguishing between different 3-manifolds. They are invaluable for mathematical software, but current algorithms to compute them require exponential time. I will discuss this family of invariants, and present an explicit fixed-parameter tractable algorithm for arbitrary r which is practical -- and indeed preferable -- to the prior state of the art for real computation.
This is joint work with Ben Burton and Clément Maria

Alexander Gamkrelidze11.08.1515:00MA 621 Algorithms for Convex Topology: Computation of Hom-Complexes
Abstract:

After a brief introduction to the field of polytopal complexes and affine maps between them, we define the set Hom(P,Q) of all possible affine mappings between two polytopal complexes P and Q that builds a polytopal complex in a higher dimensional space. There are efficient software packages like Polymake that deal (among other things) with the computation of Hom-complexes between two polytopes, but no complexes. In this talk, we introduce algorithms that compute the above mentioned structures and their homotopies. At the end of the talk we introduce a conjectured geometric analog to a well known formula Hom(P,ker(f))=kerHom(P,f): Hom(P,$\Sigma$(f))=$\Sigma$ Hom(P,f) and discuss some ideas to compute the Sigma operator and the possible ways to prove the equation. In case the above conjecture holds, the wide area of the algebraic theory of polytopes can be established.

# Vorträge

Name
Datum
Uhrzeit
Ort
Titel
Michael Joswig
19.10.15
14:15
MA 041
Smooth Fano Polytopes With Many Vertices

# Konferenzen/Workshops

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