Upcoming Talks

Combinatorics Seminar

Title: Kneser graphs are Hamiltonian
Speaker: Torsten Mütze (University of Warwick)
Date: Friday 26th April 12:30
Room: Online meeting (Webex)
Abstract:

For integers $k\geq 1$ and $n\geq 2k+1$, the Kneser graph $K(n,k)$ has as vertices all $k$-element subsets of an $n$-element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph $K(5,2)$. This problem received considerable attention in the literature, including a recent solution for the sparsest case $n=2k+1$. The main contribution of our work is to prove the conjecture in full generality. We also extend this Hamiltonicity result to all connected generalized Johnson graphs (except the Petersen graph). The generalized Johnson graph $J(n,k,s)$ has as vertices all k-element subsets of an n-element ground set, and an edge between any two sets whose intersection has size exactly $s$. Clearly, we have $K(n,k)=J(n,k,0)$, i.e., generalized Johnson graphs include Kneser graphs as a special case. Our results imply that all known families of vertex-transitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lovász’ conjecture on Hamilton cycles in vertex-transitive graphs from 1970. Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway’s Game of Life, and to analyze this system combinatorially and via linear algebra.

This is joint work with Arturo Merino (TU Berlin) and Namrata (Warwick).

Meeting link:
\[
\text{https://tugraz.webex.com/tugraz/j.php?MTID=m8500c46344212abf0fa37925da5ef9bf}
\]

Geometrisches Seminar

Title: Cup Product Persistence and Its Efficient Computation
Speaker: Abhishek Rathod (Ben Gurion University of the Negev)
Date: 24.04.2024, 13:45
Room: Seminarraum 2, Kopernikusgasse 24/IV.
Abstract:

It is well-known that the cohomology ring has a richer structure than homology groups. However, until recently, the use of cohomology in the persistence setting has been limited to speeding up barcode computations. Some of the recently introduced invariants, namely, persistent cup-length, persistent cup modules and persistent Steenrod modules, to some extent, fill this gap. When added to the standard persistence barcode, they lead to invariants that are more discriminative than the standard persistence barcode. In this work, we devise an $O(dn^4)$ algorithm for computing the persistent $k$-cup modules for all $k\in\{2,\dots,d\}$, where $d$ denotes the dimension of the filtered complex, and $n$ denotes its size. Moreover, we note that since the persistent cup length can be obtained as a byproduct of our computations, this leads to a faster algorithm for computing it for $d \ge 3$. Finally, we introduce a new stable invariant called partition modules of cup product that is more discriminative than persistent $k$-cup modules and devise an $O(c(d)n^4)$ algorithm for computing it, where $c(d)$ is subexponential in $d$.

Colloquium Discrete Geometry

Title: Subdivisions and invariants of matroids
Speaker: Benjamin Schröter (KTH Royal Institute of Technology)
Date: 24.04.2024, 11:00 Uhr
Room: Seminarraum 1, Kopernikusgasse 24/IV.
Abstract:

Matroids are a combinatorial abstraction of both graphs and linear spaces who play a central role in tropical geometry. In my talk I will take a polyhedral view on matroids and demonstrate how this perspective can be used to study classical matroid and graph invariants, tropical moduli spaces as well as problems arising in real life applications, e.g., shortest path problems in optimization, scattering processes in physics or decompositions in phylogenetics.

Combinatorics Seminar

Title: The structure and density of (strongly) $k$-product-free sets in the free semigroup.
Speaker: Frederick Illingworth (University College London)
Date: Friday 19th April 12:30
Room: Online meeting (Webex)
Abstract:

The free semigroup} $\mathcal{F}$ over a finite alphabet $\mathcal{A}$ is the set of all finite words with letters in $\mathcal{A}$ equipped with the operation of concatenation. A subset $S$ of $\mathcal{F}$ is $k$-product-free} if no $k$ words in $S$ concatenate to another word in $S$. How dense can a $k$-product-free subset of $\mathcal{F}$ be? What is the structure of the densest $k$-product-free subsets?

Leader, Letzter, Narayanan, and Walters proved that $2$-product-fee subsets of the free semigroup have density at most $1/2$ and asked for the structure of the densest sets. In this talk I will discuss the answer to their question as well as the answer (both density and structure) for general $k$. This generalises results of {\L}uczak and Schoen for sum-free sets in the integers although the methods used are quite different.

This is joint work with Lukas Michel and Alex Scott.

Meeting link:
\[
\text{https://tugraz.webex.com/tugraz/j.php?MTID=m8500c46344212abf0fa37925da5ef9bf}
\]

Colloquium Discrete Geometry

Title: The Wachspress Geometry of Polytopes --- a bridge between algebra, geometry and combinatorics
Speaker: Martin Winter (University of Warwick)
Date: Wed 17.04.2024, 11:00
Room: Seminarraum 1, Kopernikusgasse 24/IV.
Abstract:

Wachspress Geometry is a young field concerned with a family of closely related mathematical objects defined on polytopes -- the so-called ``Wachspress object''.
At its center, the ``Wachspress coordinates'' have their origin as generalized barycentric coordinates in geometric modeling and finite element analysis, but have since re-emerged in a wide range of seemingly unrelated contexts in algebraic geometry, statistics, spectral graph theory, rigidity theory and convex geometry. Explaining and exploiting this surprising ubiquity is a central motivation of Wachspress Geometry.

My first goal for this talk is to give an introduction to this fascinating subject and to elaborate on the potential of Wachspress Geometry to bridge between the algebra, geometry and combinatorics of polytopes. Subsequently I will focus on two particular applications that emerged in my own research: first, the rigidity and reconstruction of polytopes from partial combinatorial and metric data; second, a novel approach to algorithmically decide the polytopality of simplicial spheres.

First guest lecture within SS24 Elective subject mathematics (Linear Operators)

Title: Eigenfunctions of the Laplacian
Speaker: Jean-Claude Cuenin (Loughborough University, UK)
Date: Start: April 15, 12.00-12.30 (first organizatorial meeting)
Room: TU Graz, Steyrergasse 30, Seminarraum AE02 (STEG006), EG
Abstract:

Outline: The topic of the lecture is eigenfunctions of the Laplace-Beltrami operator on Riemannian manifolds. The first goal is to prove the sharp Weyl formula, which describes the asymptotic distribution of the eigenvalues. The second goal is to prove sharp bounds on Lp norms of eigenfunctions. Lp norms provide a convenient measure for the concentration of eigenfunctions and shed some light on the question `How do eigenfunctions look like’? To tackle this question we will develop tools from harmonic and microlocal analysis. If time permits, we will discuss improvements to these estimates under additional dynamical conditions on the geodesic flow.