The aim of the meeting is to bring together graduate students and early postdocs working in fields related to applied algebra and combinatorics. The program is divided into contributed talks by the participants, invited lectures, and plenty of problem sessions to start new collaborations!
The deadline for talk submissions has passed (January 4, 2019), however it is still possible to apply for a poster presentation (no funding available). In your registration email you will receive instructions on how to upload your documents.
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.
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.
Tope arrangements are a collection of bipartite graphs on node sets $[n]\sqcup[d]$, along with a bijection to the lattice points of the scaled simplex $n\Delta_{d-1}$. The motivation for their introduction arises from tropical geometry, but they have multiple connections to classical algebraic geometry via the Grassmannian $\rm{Gr}_d(\mathbb{C}^n)$ and the determinantal variety $\nabla_{d,n}$, the variety of degenerate matrices: \[ \nabla_{d,n} = \left\{X \in \mathbb{C}^{d\times n}\,\right|\left.\,rk(X) < d\right\} \enspace . \] 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.
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.
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.
Construction Methods for GaussoidsTobias BoegeOtto-von-Guericke-Universität MagdeburgGaussoids are combinatorial structures generalizing conditional independence inference rules among Gaussian random variables, similar to how matroids generalize linear independence. Since their introduction in 2007 by Lněnička and Matúš, combinatorial results about gaussoids have been confined to dimension $\le 5$.Using an embedding of $N$-gaussoids into the $N$-dimensional cube, we show constructively that the logarithm of the number of gaussoids is asymptotically between $n 2^n$ and $n^2 2^n$. This is considerably larger than the number of "statistically relevant" gaussoids --- those realizable by a Gaussian distribution. Their number is known to the same degree of accuracy: the logarithm is asymptotically between $n^2$ and $n^3$.Tuples of lattice polytopes of mixed degree oneChristopher BorgerOtto-von-Guericke Universität MagdeburgIt has been shown by Soprunov that the lattice mixed volume of an n-tuple of n-dimensional lattice polytopes (minus one) is a lower bound for the number of interior lattice points in the Minkowski sum of the polytopes. Tuples of mixed degree one are exactly those n-tuples for which this upper bound is attained. A generic class of examples is given by n-tuples admitting a projection sending all polytopes onto the same unimodular (n-1)-simplex. We show that, for each dimension n greater than three, all but finitely many n-tuples of mixed degree one are of this generic type. Furthermore we classify n-tuples of mixed degree one for n=3, showing the existence of infinitely many non-generic examples. This is joint work with Gabriele Balletti.Signature varieties and connections to rough pathsFrancesco GaluppiMPI MiSThe signature of a path is a sequence of tensors, encoding its geometric properties. The signatures of a given class of paths form a subvariety of the space of tensors, whose geometry reflects the features of the paths. We will focus on the class of rough path, very important in stochastics. Their signature variety shows remarkable similarities to the Veronese variety.Multistationarity in the space of total concentrations for systems that admit a monomial parametrizationAlexandru IosifOtto-von-Guericke-Universität MagdeburgWe apply tools from real algebraic geometry to the problem of multistationarity of chemical reaction networks whose positive steady states admit a monomial parametrization. In particular, we show that in the space of total concentrations there is multistationarity for some value of the total concentrations if and only if there is multistationarity on the entire ray containing this value (possibly for different rate constants). Moreover, for these networks it is possible to decide about multistationarity by formulating semialgebraic conditions that involve only total concentrations. Hence quantifier elimination may give new insights into multistationarity regions in the space of total concentrations. To demonstrate this, we show that for the distributive phosphorylation of a protein at two binding sites multistationarity is only possible if the total concentration of the substrate is larger than either the concentration of the kinase or the phosphatase. This result is enabled by the chamber decomposition from polyhedral geometry. This is a joint work with Carsten Conradi and Thomas Kahle.
References: C. Conradi, A. Iosif, T. Kahle, Multistationarity in the space of total concentrations for systems that admit a monomial parametrization arXiv:1810.08152.Supersolvable simplicial arrangementsA simplicial arrangement is a finite set of hyperplanes in $\mathbb{R}^\ell$ which cuts simplicial cones out of the ambient space. For example all Coxeter arrangements, i.e. the reflection arrangements of the finite real reflection groups are simplicial.At least in rank $3$ there is a list of irreducible simplicial arrangements conjectured to be complete.But a classification of these natural geometric objects remains an open problem.A further important class in the theory of hyperplane arrangements are the supersolvable arrangements which possess nice algebraic, geometric and combinatorial properties.We give a classification of all supersolvable simplicial arrangements using tools inspired by M. Cuntz and I. Heckenberger's recent work on crystallographic arrangements.
This is joint work with Michael Cuntz.Lyndon marked permutations and free Hopf algebrasWe will see that functions that count substructures generate algebras if we are given a combinatorial presheaf. These have been studied for permutations and graphs, and here we will observe that the algebra obtained by marked permutations is in fact free.Smallest cyclically covering subspaces of $\mathbb{F}_q^n$Please see the abstract as PDF file.Edge ideals of weighted oriented graphsThe components of the irreducible monomial primary decomposition of an edge ideal of a simple hypergraph are completely determined by the minimal covers of the hypergraph. In this talk, we will introduce the concept of edge ideal of a weighted oriented graph. We will study the irreducible monomial primary decomposition of these ideals. For get it, we introduce the concept of {\bf strong cover} and we prove that these determine the components of the primary decomposition. We will study also when these edge ideals are unmixed and finally we will study the Cohen-Macaulay property for these ideals.How many zeros does a random fewnomial system have?Josue Tonelli-CuetoTechnische Universität BerlinA \emph{fewnomial system} in~$n$ variables with~$t$ terms is a polynomial system $f_1(x)=0,\ldots,f_n(x)=0$ of equations where each polynomial $f_i$ in the system has a prescribed set of monomials described by a set $A\subseteq \mathbb{N}^n$ of cardinality~$t$. In 1980, Khovanskii proved that such a system with real coefficients has at most \[2^{\binom{t-1}{2}}(n+1)^{t-1}\] nondegenerate positive real solutions. It is important to note that this bound does not depend on the degrees of the polynomials. It is conjectured that this bound can be improved to be polynomial in~$t$. However, all existing improvements are still exponential in~$t$. In this talk, we consider a probabilistic version of this conjecture. We show that the expected number of nondegenerate positive real solutions of a random fewnomial system in~$n$ variables with~$t$ terms is bounded by \[ 2\binom{t}{n}, \] which is polynomial in~$t$.
This is joint work with Peter Bürgisser and Alperen A. Ergür.Moment ideals of local Dirac mixturesMarkus WageringelOsnabrück UniversityThis is joint work with Alexandros Grosdos Koutsoumpelias.
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.
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.
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.
The chromatic subdivision $\chi(\Delta)$ of a simplicial complex $\Delta$ is obtained by replacing the simplices of $\Delta$ by suitable Schlegel diagrams of the cross-polytope. We investigate the $f$- and $h$-vector transformation moving from $\Delta$ to $\chi(\Delta)$ 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 $\Delta$ to its chromatic subdivision $\chi(\Delta)$.
Let $P$ be an $n$-dimensional regular crosspolytope, simplex, or cube centred at the origin of $\mathbb{R}^n$. We consider convex cones of the form $$C=\{ \lambda x+\lambda e_{n+1} : \lambda \geq 0, x\in P \} \subset \mathbb{R}^{n+1}, $$ where $e_1,\ldots,e_{n+1}$ is the standard basis of $\mathbb{R}^{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 $\mathcal{P}_{n,d}$, that is the probability that a deterministic point $x \in \mathbb{R}^d$ is contained in the convex hull of $n$ independent standard normally distributed points $X_1,\ldots,X_n$ in $\mathbb{R}^d$ together with their negatives $-X_1,\ldots,-X_n$. Only few stochastic knowledge is necessary to follow this talk, since the methods presented are relatively basic.
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.
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.
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.
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.
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.
