WS 2020/21

Freitag, 6. November 2020 um 13:30 Uhr, Oberseminar Relle Geometrie und Algebra

Tim Seynnaeve (Universität Bern)

(Gast von Mateusz Michalek)

Complete quadrics and algebraic statistics

Let $L$ be a generic linear space of symmetric matrices over the complex numbers. By inverting all invertible matrices in this space, we obtain an algebraic variety. Computing the degree of this variety is a natural geometric question in its own right, but is also interesting from the point of view of algebraic statistics: the number we obtain is the so-called maximum likelihood degree (ML-degree) of the generic linear concentration model. In 2010, Sturmfels and Uhler conjectured that if we fix the dimension of $L$, this ML-degree is a polynomial in the size of the matrices. Using Schubert calculus and intersection theory on the space of complete quadrics, we were able to prove this polynomiality conjecture, and to write an algorithm that can compute these polynomials efficiently.

This talk is based on joint work in progress with Laurent Manivel, Mateusz Michalek, Leonid Monin, and Martin Vodicka.

Freitag, 13. November 2020 um 13:30 Uhr, Oberseminar Relle Geometrie und Algebra

Fulvio Gesmundo (University of Copenhagen)

(Gast von Mateusz Michalek)

Segre reembedding of secant varieties and multiplicativity of rank and border rank

The notion of matrix rank in linear algebra finds a natural generalization for an arbitrary algebraic variety $X$, commonly known as $X$-rank, which is related to the study of the secant varieties of the variety $X$. Motivated by connections with complexity theory and quantum information, it is natural to investigate the behaviour of $X$-rank under Segre reembedding. In recent work, we analyzed Segre reembeddings of secant varieties, determining a number of pathological behaviours. In this seminar I will illustrate the geometric framework and some of these interesting phenomena.

Montag, 16. November 2020 um 15:15 Uhr, Oberseminar Complexity Theory, Model Theory, Set Theory

Wieslaw Kubis (CAS Prague)

(Gast von Salma Kuhlmann)

Universality of automorphism groups of homogeneous structures

A relational structure $M$ is homogeneous if every finite partial isomorphism extends to an automorphism. Countable homogeneous structures are known as Fraisse limits, standard examples are the linearly ordered set of all rational numbers and the Rado graph. Given a homogeneous structure $M$, it is natural to ask whether its automorphism group $\mathrm{Aut}(M)$ is universal in the sense that for every substructure $X$ of $M$ the group $\mathrm{Aut}(M)$ embeds into $\mathrm{Aut}(M)$. Typical Fraisse limits have this property. We shall present examples of homogeneous structures whose automorphism groups are not universal.

Joint work with S. Shelah.

Montag, 30. November 2020 um 15:15 Uhr, Oberseminar Complexity Theory, Model Theory, Set Theory

Christian Ikenmeyer (University of Liverpool)

(Gast von Mateusz Michalek)

The Computational Complexity of Plethysm Coefficients

Plethysm coefficients are the representation theoretic multiplicities in the coordinate rings of spaces of polynomials. There are almost no results about the complexity of computing plethysm coefficients or even deciding their positivity. It follows from recent work of Kahle and Michalek (2016) that plethysm coefficients can be computed in polynomial time if the outer parameter is fixed. In this paper we show that even deciding the positivity of plethysm coefficients is NP-hard (and that computing plethysm coefficients is $\#P$-hard) if the inner parameter of the plethysm coefficient is fixed instead. In this way we obtain an inner versus outer contrast.

Moreover, we derive new lower and upper bounds and in special cases even combinatorial descriptions for plethysm coefficients, which we consider to be of independent interest. Our technique uses discrete tomography in a more refined way than the recent work on Kronecker coefficients by Ikenmeyer, Mulmuley, and Walter (Comput Compl 2017). This makes our work the first to apply techniques from discrete tomography to the study of plethysm coefficients. Quite surprisingly, that interpretation also leads to new natural equalities between certain plethysm coefficients and Kronecker coefficients.

Freitag, 18. Dezember 2020 um 13:30 Uhr, Oberseminar Relle Geometrie und Algebra

Joachim Jelisiejew (University of Warsaw)

(Gast von Mateusz Michalek)

Homology of moduli spaces of finite rank objects

Deformations of finite rank $k$-algebras form a very complicated scheme, called the Hilbert scheme of points. However the homology and even the motive of this scheme is perfectly behaved, in fact isomorphic to those of a Grassmannian. It the talk I will explain the proof and related open questions for secant varieties and deformations of finite rank modules.

This is a joint work with Marc Hoyois, Denis Nardin, Burt Totaro and Maria Yakerson.

Freitag, 8. Januar 2021 um 13:30 Uhr, Oberseminar Relle Geometrie und Algebra

Matteo Varbaro (University of Genoa)

(Gast von Mateusz Michalek)

Singularities, Serre conditions and $h$-vectors

Let $R$ be a standard graded algebra over a field, and denote by $H_R(t)$ its Hilbert series. As it turns out, multiplying $H_R(t)$ by $(1-t)^{\dim R}$ yields a polynomial
$$
h(t)=h_0+h_1t+h_2t^2+\ldots+h_st^s,
$$
known as the $h$--polynomial of $R$. It is well known and easy to prove that if $R$ is Cohen-Macaulay $h_i$ is nonnegative for all $i$.
Since being Cohen-Macaulay is equivalent to satisfying Serre condition ($S_i$) for all $i$, it is licit to ask if $h_i$ is nonnegative for all $i\leq r$ whenever $R$ satisfies ($S_r$).
As it turns out, this is false in general, but true putting some additional assumptions on the singularities of $R$. In characteristic $0$, it is enough that $X= \mathrm{Proj}\, R$ is Du Bois (in particular, if $X$ is smooth we have the desired nonnegativity). In positive characteristic, assuming $R$ is $F$-pure (equivalently, if $X=\mathrm{Proj}\, R$ globally $F$-pure), things work well. In this talk I will speak of the above results and some of their consequences.

This is a joint work with Hailong Dao and Linquan Ma.

Freitag, 22. Januar 2021 um 13:30 Uhr, Oberseminar Relle Geometrie und Algebra

Daniel Brosch (Tilburg University)

(Gast von Markus Schweighofer)

More efficient and flexible Flag-Algebras coming from polynomial optimization

Flag Algebras, i.e. gluing-algebras of limit operators describing the densities of partially labelled sub-graphs, were first introduced by Razborov in 2007 as a powerful tool for problems in extremal combinatorics. Recently Raymond et al. investigated the connections between Flag-SOS and limits of symmetric problems in polynomial optimization, describing an alternative way to derive these algebras. We take a closer look at the symmetry of this problem, deriving a more efficient equivalent hierarchy. We then describe a way to determine alternative, related hierarchies, which make it possible to calculate non-trivial bounds for problems where the usual Flag-SOS method fails. These hierarchies we then apply to the rectilinear crossing numbers of graphs and to distance one maximizing graphs on the Euclidean plane.

Donnerstag, 28. Januar 2021 um 17:00 Uhr, Oberseminar Relle Geometrie und Algebra

Khazhgali Kozhasov (TU Braunschweig)

(Gast von Mateusz Michalek)

Nodes on quintic spectrahedra

A ($3$-dimensional) spectrahedron is the slice of the cone of $n\times n$ positive semidefinite matrices with a ($3$-dimensional) affine linear subspace. In this talk I would like to explain the classification of generic quintic ($n=5$) spectrahedra by the location of $20$ nodes on their algebraic boundary (which is the set of singular matrices in the associated linear space of symmetric matrices).
Based on a joint work with Taylor Brysiewicz and Mario Kummer.

Donnerstag, 4. Februar 2021 um 17:00 Uhr, Oberseminar Relle Geometrie und Algebra

Joseph Gubeladze (San Francisco State University)

(Gast von Mateusz Michalek)

Normal polytopes and ellipsoids

In the talk we will introduce the class of normal polytopes - lattice polytopes of central importance at the crossroads of toric algebraic geometry, combinatorial commutative algebra, and integer programming. A narrower class is the lattice polytopes, covered by unimodular simplices: a property of number theoretical flavor. It was shown in the 1990s that the latter class is a proper subclass of the former. Currently detection of explicit families of normal polytopes, possessing unimodular covers, is an increasingly popular topic. But the progress in this direction is scarce, even in dimension $3$. We will review recent and not so recent results in the field and present our new results.

Freitag, 12. Februar 2021 um 13:30 Uhr, Oberseminar Relle Geometrie und Algebra

Mateusz Skomra (LAAS, Toulouse)

(Gast von Markus Schweighofer)

Derandomization and absolute reconstruction for sums of powers of linear forms

We study the decomposition of multivariate polynomials as sums of powers of linear forms. In this talk, we focus on the following problem: given a homogeneous polynomial of degree $3$ over a field, decide whether it can be written as a sum of cubes of linearly independent linear forms over an extension field. This task can be equivalently expressed as a decomposition problem for symmetric tensors of order $3$. Even if the input polynomial has rational coefficients, the answer may depend on the choice of the extension field. We study the cases where the extension field is either the real or the complex numbers. Our main result is an algorithm that solves this problem in polynomial time when implemented in the bit model of computation. Furthermore, contrary to the previous algorithms for the same problem, our algorithm is algebraic and does not make any appeal to polynomial factorization. We also discuss how our algorithm can be extended to other tensor decomposition problems.

This talk is based on a joint work with Pascal Koiran.