Research Seminar

The M9 Research Seminar is a weekly seminar in which our guests as well as our group discuss recent research advances and interesting open problems in applied geometry and discrete mathematics.

Usual time: Monday 15:15

Usual room: 02.04.011

Past and Upcoming Talks

Date Speaker Title
Jul 07, 2017, 10:00 Bernhard von Stengel (London School of Economics) Index and Uniqueness of Symmetric Equilibria
May 15, 2017, 14:00 Abhishek Rathod (TUM, M10) Approximation Algorithms for Max Morse Matching
May 05, 2017, 14:00 Prof. Dr. Salvador Gomis (University of Alicante) Some isodiametric inequalities on convex surfaces
May 03, 2017, 15:30 Bernardo González Merino Two Minkowski type theorems in the Geometry of Numbers
Apr 04, 2017, 14:00 Anja Kirschbaum Data Classification, Clustering, Tomography & the Kernel-trick
Apr 04, 2017, 13:00 Maximilian Fiedler Data Transformation in Clustering and Classification
Apr 03, 2017, 14:45 Paul Stursberg Manipulating Single and Double Elimination Knock-out Tournaments

Abstracts

Bernhard von Stengel (London School of Economics): Index and Uniqueness of Symmetric Equilibria

In a symmetric two-player game, a symmetric equilibrium can only be dynamically stable if it has positive index. The sum of the indices of all equilibria is 1, so a unique equilibrium has index 1. The index is a topological notion related to geometric orientation, and defined in terms of the sign of the determinant of the payoffs in the equilibrium support. We prove a simple strategic characterization of the index conjectured by Hofbauer: In a nondegenerate symmetric game, an equilibrium has index 1 if and only if it is the unique equilibrium in a larger symmetric game obtained by adding further strategies (it suffices to add a linear number of strategies).

Our elementary proof introduces "unit-vector games" where one player's payoff matrix consists of unit vectors, and applies in a novel way simplicial polytopes. In addition, we employ a very different known result that any matrix with positive determinant is the product of three P-matrices, a class of matrices important in linear complementarity.

Joint work with Anne Balthasar.

Abhishek Rathod (TUM, M10): Approximation Algorithms for Max Morse Matching

In this talk, we will discuss two approximation algorithms for the Max Morse Matching Problem, specifically the problem of finding the optimal discrete Morse function on a simplicial complex. For D-dimensional simplicial complexes, we obtain a ( D + 1 ) / ( D^2 + D + 1 ) -factor approximation ratio using a simple edge reorientation algorithm that removes cycles. For D >= 5 , we describe a 2 / D -factor approximation algorithm for simplicial manifolds by processing the simplices in increasing order of dimension. This algorithm leads to 1 / 2 -factor approximation for 3-manifolds and 4 / 9 -factor approximation for 4-manifolds. This algorithm may also be applied to non-manifolds resulting in a 1 / ( D + 1 ) - factor approximation ratio. One application of these algorithms is towards efficient homology computation of simplicial complexes. Experiments using a prototype implementation on several datasets indicate that the algorithm computes near optimal results. We will end the talk with some related open problems.

Prof. Dr. Salvador Gomis (University of Alicante): Some isodiametric inequalities on convex surfaces

Some isodiametric inequalities on convex surfaces

Abstract: The intrinsic distance on a convex surface allows us to present some isodiametric inequalities on convex surfaces, and discuss some applications 1) to the geometry of convex surfaces of constant antipodal distance 2) to a classical conjecture by Steinhaus on farthest points and 3) to the Aleksandrov isodiametric conjecture.

Bernardo González Merino: Two Minkowski type theorems in the Geometry of Numbers

Minkowski showed his "First Fundamental Theorem" in 1896, and it states that every 0-symmetric convex body whose only interior point from the lattice $mathbb Z^n$ is the origin 0, has volume bounded from above by $2^n$.

Substituting the volume by the number of lattice points in $K$ (known as the emph{lattice point enumerator}) Minkowski was able to show a "discrete" analogous result to his First Fundamental Theorem, where the former is then bounded from above by $3^n$ instead. Moreover, he could even reduce this upper bound down to $2^{n+1}-1$ if $K$ is assumed to be strictly convex.

In this talk we will show how to extend these two "discrete" theorems of Minkowski, by removing the condition that $K$ contains the origin as the only interior lattice point, following in some sense the ideas that Blichfeldt and Van der Corput developed in order to extend the First Fundamental Theorem of Minkowski.

Bibliography:

G. Averkov, B. Gonz'alez Merino, I. Paschke, M. Schymura, and S. Weltge: Tight bounds on discrete quantitative Helly numbers. Adv. Appl. Math. 89 (2017), 76--101.

B. Gonz'alez Merino and M. Henze: A generalization of the discrete version of Minkowski's fundamental theorem. Mathematika 62 (2016), 637--652.

H. Minkowski: Geometrie der Zahlen. In Bibliotheca Mathematica Teubneriana, Teubner, Leipzig-Berlin, 1896, reprinted by Johnson Reprint Corp., New York, 1968.

Anja Kirschbaum: "Data Classification, Clustering, Tomography & the Kernel-trick"

Independent Studies 2

Maximilian Fiedler: "Data Transformation in Clustering and Classification"

Independent Studies 1

Paul Stursberg: "Manipulating Single and Double Elimination Knock-out Tournaments"

Abstract: Balanced knockout tournaments are one of the most common formats for sports competitions, and are also used in elections and decision-making. The computational complexity of determining whether there is a way to make a particular player win such a tournament had been an open problem for at least 10 years. We prove that checking whether there exists a draw in which a particular player wins is NP-complete. We also generalize this result to double-elimination tournaments.