Vorträge 2022
Anand Srivastav (Kiel): Recent Advances in the Maker Breaker Subgraph Game
The triangle game introduced by Chvátal and Erdős (1978) is one of the old and famous combinatorial games. For n , q ∈ N, the ( n , q )-triangle game is played by two players, called Maker and Breaker, on the complete graph K _ n . Alternately Maker claims one edge and thereafter Breaker claims q edges of the graph. Maker wins the game if he can claim all three edges of a triangle. Otherwise Breaker wins. Chvátal and Erdős (1978) proved that for q < sqrt( n /2), Maker has a winning strategy, while for q > 2 sqrt( n ), Breaker wins. So, the threshold bias must be in the interval [sqrt(1/2)sqrt( n ) , 2 sqrt( n )]. Since then, the problem of finding the exact constant (and an associated Breaker strategy) for the threshold bias of the triangle game has been one of the interesting open problems in combinatorial game theory. In fact, the constant is not known for any graph with a cycle and we do not even know if such a constant exists. Balogh and Samotij (2011) slightly improved the Chvátal-Erdős constant for Breaker’s winning strategy from 2 to 1.935 with a randomized approach. Thereafter, no progress was made. In this work, we present a new deterministic strategy for Breaker leading to his win if q > sqrt(8/3) sqrt( n ), for sufficiently large n . This almost matches the Chvátal-Erdős bound of sqrt(1/2)sqrt( n ) for Maker's win (Glazik, Srivastav, Europ. J. Comb. 2022). In contrast to previous (greedy) strategies we introduce a suitable non-linear potential function on the set of nodes. By keeping the potential small, Breaker picks edges that neutralize the most ‘dangerous’ nodes with incident Maker edges blocking Maker triangles. A characteristic property of the dynamics of the game is that the total potential is not monotone decreasing. In fact, the total potential of the game may increase, even for several turns, but finally Breaker’s strategy prevents the total potential of the game from exceeding a critical level, which results in Breaker’s win. We further survey recent results for cycles of length k , and a general potential function theorem (Sowa, Srivastav 2023). This is joint work with Christian Glazik, Christian Schielke and Mathias Sowa, Kiel University.
Ort: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Great Lecture Hall (Ground Floor)
Ralf Kornhuber (FU-Berlin): Neural networks, Fredholm integral equations and all that jazz …
The industrial revolution started with the invention of the steam engine in the 19th century and has made physical work redundant to a large extend. Data Science and Artificial Intelligence (AI) might have the potential to play a similar role for intellectual work. There is a huge overlap of Data Science and AI with mathematics, which on one hand comes with unprecedented social responsibility of mathematics and on the other hand with lots of opportunities for application and extension of existing mathematical concepts and results. In this talk, I will give three examples. First I will present some recent ideas on neural network training by Fredholm integral equations (joint work with P. Gelß and A. Issgali). Then I will rely on recent work of other authors to discuss the curse of dimensionality in neural network approximation, and to finally sketch a backward error attack on deep learning.
Ort: Seminarraum 019 Arnimallee 3 14195 Berlin
Tibor Szabó (FU Berlin): Topology at the North Pole
In the max-min allocation problem a set P of players are to be allocated disjoint subsets of a set R of indivisible resources, such that the minimum utility among all players is maximized. We study the restricted variant, also known as the Santa Claus problem , where each resource has an intrinsic positive value, and each player covets a subset of the resources. Bezakova and Dani showed that this problem is NP-hard to approximate within a factor less than 2, consequently a great deal of work has focused on approximate solutions. The principal approach for obtaining approximation algorithms has been via the Configuration LP (CLP) of Bansal and Sviridenko. Accordingly, there has been much interest in bounding the integrality gap of this CLP. The existing algorithms and integrality gap estimations are all based one way or another on the combinatorial augmenting tree argument of Haxell for finding perfect matchings in certain hypergraphs. Here we introduce the use of topological tools for the restricted max-min allocation problem. This approach yields substantial improvements in the integrality gap of the CLP. In particular we improve the previously best known bound of 3.808 to 3.534. The talk represents joint work with Penny Haxell.
Ort: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Great Lecture Hall (Ground Floor)
Günter Rote (Freie Universität Berlin): Grid Peeling and the Affine Curve-Shortening Flow
Grid Peeling is the process of taking the integer grid points inside a convex region and repeatedly removing the convex hull vertices. By contrast, the Affine Curve-Shortening Flow (ACSF) is defined as a particular deformation of a smooth curve. It has been observed in 2017 by Eppstein, Har-Peled, and Nivasch, that, as the grid is refined, Grid Peeling converges to the Affine Curve-Shortening Flow. As part of the M.Ed. thesis of Moritz Rüber, we have investigated the grid peeling process for special parabolas, and we could observe some striking phenomena. This has lead to the precise value of the constant that relates the two processes. With Morteza Saghafian from IST Austria, we could prove the convergence of grid peeling for the class of parabolas with vertical axis.
Ort: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Great Lecture Hall (Ground Floor)
Max von Kleist (FU-Berlin Antrittsvorlesung): Mathematics for public health
Public health is concerned with measures that improve the general health and prevent infections. In my talk, I will give an overview and outlook of our current work and explain how data science in conjunction with mathematical modeling and simulation can be utilized to guide public health decisions. In particular, I will present approaches that utilize primary and secondary data of SARS-CoV-2 to permanently monitor and assess the pandemic. Moreover, I will give examples where these approaches supported the choice of containment and testing strategies in 2020/21. I will then give some insight into our ongoing work in the field of HIV-1 prevention, the mathematical methods developed along the way, and illustrate how this work is used to quantify risk reduction, to develop guidelines, as well as to a posteriori assess the impact of interventions on the HIV pandemic.
Ort: Seminarraum 019 Arnimallee 3 14195 Berlin
Marita Thomas (FU-Berlin Antrittsvorlesung): Modeling and Analysis of Bulk-Interface Processes
Heterogeneous materials can be seen as bulk-interface systems. They consist of distinct bulk components with different material properties meeting at thin interfacial layers forming lower-dimensional substructures of the system. In many applications the properties of interfaces strongly impact the functionality of the whole system and, in turn, interfaces are strongly affected by processes taking place in the bulk material. Interfaces thus follow their own evolution laws in interaction with bulk processes. In this talk I discuss a general thermodynamical modeling framework for bulk-interface processes and, in particular, apply it to problems related to heat conduction and fracture in elastic composites. Here, a challenge in the modeling and in the analysis lies in the change of the material geometry with the progressing fracture and in the constraint that in many materials crack growth is a unidirectional process, since the crack cannot heal. Models suited to handle these challenges and thus suited to describe dynamic fracture processes in elastic solids with the aid of non-smooth constraints will be introduced. Recent results on their mathematical analysis will be presented.
Ort: Seminarraum 019 Arnimallee 3 14195 Berlin
Claudia Schillings (FU-Berlin Antrittsvorlesung): Quantification of uncertainty for inverse and optimization problems
Approaches to decision making and learning mainly rely on optimization techniques to achieve “best” values for parameters and decision variables. In most practical settings, however, the optimization takes place in the presence of uncertainty about model correctness, data relevance, and numerous other factors that influence the resulting solutions. For complex processes modeled by nonlinear ordinary and partial differential equations, the incorporation of these uncertainties typically results in high or even infinite dimensional problems in terms of the uncertain parameters as well as the optimization variables. We will discuss methods which can be shown to be robust with respect to the number of parameters and are therefore suitable for this setting.
Ort: Seminarraum 019 Arnimallee 3 14195 Berlin
Milena Hering (Edingburgh): Embedding of Algebraic Varieties and Toric Vector bundles
Algebraic varieties are geometric objects that can be described as the zero locus of polynomial equations. While the relationship between geometry and algebra is fundamental to algebraic geometry, it still remains quite mysterious. I will explain some aspects that are known about it, as well as some open questions. And how toric vector bundles enter the equation.
Ort: Seminarraum 019 Arnimallee 3 14195 Berlin
Arend Bayer (Edingburgh): Derived Categories, Wall-crossing and Birational Geometry
Birational geometry studies maps between algebraic varieties defined by rational functions. Recently, derived categories, stability conditions and wall-crossing have led to an entirely new approach to fundamental open questions in birational geometry. I will survey these developments, with an emphasis on Hyperkaehler varieties and cubic fourfolds.
Ort: Seminarraum 019 Arnimallee 3 14195 Berlin
Ana Djurdjevac (FU-Berlin Antrittsvorlesung): Randomness and PDEs: Analysis, Numerics and Applications
We will first consider interacting particle systems that provide powerful models that are useful in many application areas such as sociology (agents), molecular dynamics (proteins) etc. The first model that we will define is a non-linear stochastic PDE that provides a faithful representation of the evolution of the empirical density of a given particle system. This model has a direct applications in the opinion dynamics that will be discussed. Furthermore, we will explain difficulties in numerical approximations of these problems. Instead of considering many particles, next we will consider just one Brownian particle, but which is now evolving on a random domain. Using the rough path analysis, we will investigate different scaling regimes of this system. As a natural question in this setting is how to present a Gaussian random fields on a sphere. One way to do this is using the so-called spherical harmonics. We will discuss the advantages of this approach and challenges in its generalizations to an arbitrary manifold.
Ort: Seminarraum 019 Arnimallee 3 14195 Berlin
Imre Bárány (Rényi Institute, Budapest): Cells in the box and a hyperplane
It is well known that a line can intersect at most 2 n −1 cells of the n × n chessboard. What happens in higher dimensions: how many cells of the d -dimensional [0, n ]^ d box can a hyperplane intersect? We answer this question asymptotically. We also prove the integer analogue of the following fact. If K,L are convex bodies in R ^d and K ⊂ L , then the surface area K is smaller than that of L . This is joint work with Péter Frankl.
Ort: Chemistry building Arnimallee 22 14195 Berlin Hörsaal A
János Pach (Rényi Institute, Budapest): Facets of Simplicity
We discuss some notoriously hard combinatorial problems for large classes of graphs and hypergraphs arising in geometric, algebraic, and practical applications. These structures are of bounded complexity: they can be embedded in a bounded-dimensional space, or have small VC-dimension, or a short algebraic description. What are the advantages of low complexity? I will suggest a few possible answers to this question, and illustrate them with classical examples.
Ort: Chemistry building Arnimallee 22 14195 Berlin Hörsaal A