Graduate Student Meeting on Applied Algebra and Combinatorics

Abstracts for the talks

Lamprini Ananiadi
Otto-von-Guericke Universität Magdeburg
Gröbner Bases for Toric Staged Trees


Staged tree models are a generalisation of discrete graphical models coding conditional independence statements between events represented in a tree graph. Their algebraic properties were studied by Duarte and Görgen in their recent paper "Equations Defining Probability Tree Models". In this talk we aim to explain the combinatorics involved in obtaining the defining equations for such models. In the toric case we show that the generators of the toric ideal are a quadratic Gröbner basis. We connect our study with the theory of toric fiber products as introduced by Sullivant in 2006. This is joint work with Eliana Duarte.

Matthias Beck
San Francisco State University
Discrete Volume Computations for Polyhedra

Our goal is to compute volumes of polyhedra, which are fundamental in many areas of mathematics. Although polyhedra have an easy description, e.g., using a linear system of equalities and inequalities, volume computation (at least in general dimension) is hard even for these basic objects. Our approach is to compute the discrete volume of a polyhedron P, namely, the number of grid points that lie inside P, given a fixed grid in Euclidean space such as the set of all integer points. A theory initiated by Eugene Ehrhart implies that the discrete volume of a polytope has some remarkable properties. We will exemplify Ehrhart theory with the help of several interesting families of polyhedra, and give applications to areas beyond computational geometry.

Arthur Bik
Universität Bern
The monic rank and instances of Shapiro's Conjecture


Shapiro's Conjecture states that every homogeneous polynomial in C[x,y] of degree de is the sum of at most d d-th powers of homogeneous polynomials of degree e. In this talk, we prove a few instances of this conjecture. We do this by introducing the monic rank. For a polynomial, the monic rank is the minimal k for which we can write (an appropriately scaled version of) the polynomial as a sum of k d-th powers of monic polynomials. We prove that the maximal monic rank of polynomials of degree de is at most d when e=1, d=1,2 or (d,e)=(3,2),(3,3),(3,4),(4,2). This is joint work with Jan Draisma, Alessandro Oneto and Emanuele Ventura.

Jan-Marten Brunink
Universität Osnabrück
Chromatic subdivision of simplicial complexes


The chromatic subdivision χ(Δ) of a simplicial complex Δ is obtained by replacing the simplices of Δ by suitable Schlegel diagrams of the cross-polytope. We investigate the f- and h-vector transformation moving from Δ to χ(Δ) and its combinatorial interpretations in the same spirit as it was done for barycentric, edgewise and interval subdivisions. Furthermore we study how algebraic invariants of the Stanley-Reisner ring as e.g, depth or projective dimension behave when passing from Δ to its chromatic subdivision χ(Δ).

Oliver Clarke
University of Bristol
Conditional Independence Ideals with Hidden Variables


We study a class of determinantal ideals that are related to conditional independence (CI) statements with hidden variables. Such CI statements correspond to determinantal conditions on flattenings of marginals of the tensor P of joint probabilities of the observed random variables. We focus on an example that generalizes the CI ideals of the intersection axiom. In this example, the minimal primes are again determinantal ideals, which is not true in general.

Alexandros Grosdos Koutsoumpelias
Universität Osnabrück
, Markus Wageringel
Moment ideals of local Dirac mixtures


Moments are quantities that measure the shape of statistical or stochastic objects and have recently been studied from a more algebraic and combinatorial point of view. We start this talk by introducing local mixtures of Dirac measures and their moment ideals. We explain how taking local mixtures of the measures on the statistical side corresponds to the tangents of the algebraic varieties on the geometric one. We then use techniques from commutative algebra to find generators of the moment ideal for the Dirac measures and use deduce the generators of the moment ideal for the related Pareto distribution from those. Furthermore, we apply elimination theory and Prony's method in order to do parameter estimation, and showcase our results with an application in signal processing.

A main goal is to highlight the natural connections between algebraic statistics, geometry, combinatorics and applications in analysis throughout the talk.

Théo Karaboghossian
Université de Bordeaux, Labri
Polynomial invariant and reciprocity theorem for the Hopf monoid of hypergraphs


Hop monoids were introduced by Aguiar and Mahajan and use algebra to formalise the notions of merging and spliting of combinatorial objects (words concatenation, graph restriction etc). Aguiar and Ardila have shown a useful application of this formalism in defining and computing polynomial invariants. In this talk I present the notion of Hopf monoid and use the works of Aguiar and Ardila to define a new polynomial invariant on hypergraphs. I then show that this invariant is subject to a reciprocity theorem similar to Stanley’s reciprocity theorem on the chromatic polynomial of a graph. Finally I show how similar results on other combinatorial objects can be found as a consequence of this theorem.

Jordan McMahon
Karl-Franzens Universität Graz
Frieze Patterns and the Grassmannian


Frieze patterns are miraculous combinatorial objects whose straightforward nature allows connections to multiple areas of mathematics to be exhibited. In the classical case frieze patterns are an illustration of the combinatorics of the cluster algebras associated with the Grassmannian. We present current and ongoing applications associated with these cluster algebras, such as to persistence homology.

Jorge Alberto Olarte
Freie Universität Berlin
Tropical Linear Algebra


Tropical geometry is a relatively recent field that studies 'polyhedral shadows' of algebraic varieties. In the tropical world there are many objects and theorems which are analogous to those in algebraic geometry. In this talk we will look specifically at tropical linear spaces and compare them with classical linear spaces. The main objective of the talk is to provide the audience with an understanding of what tropical linear spaces are, how do they look like and how do they relate to matroid polytopes. At the end I will briefly mention some results from the research that I have carried out with Alex Fink and with Marta Panizzut and Benjamin Schröter.

Greta Panova
University of Pennsylvania
Algebraic Combinatorics in Geometric Complexity Theory


Some of the oldest classical problems in algebraic combinatorics concern finding a “combinatorial interpretation”, or, more formally, a #P formula, of structure constants and multiplicities arising naturally in representation theory and algebraic geometry. Among them is the 80-year old problem of Murnaghan to find a positive combinatorial formula for the Kronecker coefficients of the symmetric group, the multiplicities of irreducible representations in tensor products. Recently these coefficients found new importance in the Geometric Complexity Theory program aimed at resolving complexity lower bounds problems like P vs NP via Algebraic Geometry and Representation Theory. Despite the little we know about Kronecker and plethysm coefficients we were able to derive positivity statements which showed that the VP vs VNP (algebraic analog of P vs NP) is even harder than originally expected, and in the meantime deepen the understanding of these coefficients and find relationships between them via complexity results.
In this talk we will introduce all the basic notions from the representation theory of the symmetric and general linear group and give some examples of how to derive positivity and briefly show how this applies to Computational Complexity which we will review as well. Based on joint works with C. Ikenmeyer, P. Burgisser.

Irem Portakal
Otto-von-Guericke Universitaet Magdeburg
Faces of the edge cone of a bipartite graph
The affine toric varieties arising from bipartite graphs form an interesting subclass providing a rich connection between graph theory and algebraic geometry. An interesting question in the frame of toric varieties is the computation of their orbits under the corresponding torus action. In this subclass of toric varieties, one can use the connection to graph theory in order to answer this question. In this talk we provide a criterion for determining the torus orbits of these varieties by relating the faces of the corresponding edge cone to certain subgraphs of the bipartite graph.

Hauke Seidel
Universität Münster
Convex Cones Spanned by Regular Polytopes, and Probabilistic Applications


Let P be an n-dimensional regular crosspolytope, simplex, or cube centred at the origin of n. We consider convex cones of the form

C = {λx + λen+1 : λ ≥ 0,x ∈ P } ⊂ ℝn+1,
where e1,,en+1 is the standard basis of n+1.

We shall derive explicit probabilistic expressions for the inner and outer solid angles of these cones. As a corollary, we shall derive a formula for the inner and outer solid angles of a regular crosspolytope.

Furthermore, we shall compute the probability that a random linear subspace intersects a fixed face of a regular crosspolytope, cube or simplex.

As another application, we shall explain how these cones are an important tool in determining the absorption probability of the symmetric Gaussian polytope 𝒫n,d, that is the probability that a deterministic point x d is contained in the convex hull of n independent standard normally distributed points X1,,Xn in d together with their negatives X1,,Xn.

Only few stochastic knowledge is necessary to follow this talk, since the methods presented are relatively basic.

Ben Smith
Queen Mary University of London
Tope Arrangements and Determinantal Varieties


Tope arrangements are a collection of bipartite graphs on node sets [n] [d], along with a bijection to the lattice points of the scaled simplex nΔd1. The motivation for their introduction arises from tropical geometry, but they have multiple connections to classical algebraic geometry via the Grassmannian Grd() and the determinantal variety d,n, the variety of degenerate matrices:

∇d,n = {X ∈ ℂd×n|| rk(X ) < d} .

In this talk, we shall focus on the connections between the latter object and tope arrangements. Furthermore, we will show how this combinatorial machinery solves two conjectures of Sturmfels and Zelevinsky regarding determinantal varieties and their Chow forms.

This is joint work with Georg Loho.

Angelica Torres
University of Copenhagen
Stability of steady states and algebraic parameterizations in chemical reaction networks.


Criteria such as Routh-Hurwitz are used to
establish whether a steady state of a system of ordinary differential equations is asymptotically stable, by computing the Jacobian of the system and studying the sign of the real part of its eigenvalues. I am interested in determining the stability of positive steady states of reaction networks (using mass-action kinetics), when the values of the reaction rate constants are unknown. To this end, I combine the Routh-Hurwtiz criterion with algebraic parameterizations of the steady state variety. In this talk I will give an overview of this approach, and present algebraic and combinatoric tools used to detect bistability in chemical reaction networks.

Lorenzo Venturello
Universität Osnabrück
Balanced triangulations on few vertices


A classical problem in combinatorial and computational topology asks for the minimum number of vertices needed to triangulate a certain manifold. In this talk I will focus on the family of balanced simplicial complexes, that is d-dimensional complexes whose underlying graph is (d+1)-colorable, and I will exhibit balanced triangulations of surfaces and 3-manifolds on few vertices which are the result of an implementation of local flips preserving the coloring condition.


Date and Location

February 18 - 20, 2019
Max Planck Institute for Mathematics in the Sciences
Inselstraße 22
04103 Leipzig

Scientific Organizers

  • Tim Seynnaeve, MPI for Mathematics in the Sciences, Leipzig
  • Rodica Dinu, University of Bucharest
  • Giulia Codenotti, Freie Universität Berlin
  • Frank Röttger, Otto-von-Guericke-Universität, Magdeburg

Administrative Contact

Saskia Gutzschebauch
MPI für Mathematik in den Naturwissenschaften
Contact by Email

23.02.2019, 01:27