Sie sind hier

Forschungsseminar

NameDatumUhrzeitOrtTitel
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