Schedule and Abstracts 2025/2026

If not stated otherwise, the talk will take place Wednesdays starting at 4:15pm in A3/SR 024
Date Speaker Title
02.07.2026
4:15 pm
A3, Hörsaal 001 		Hiệp Hàn (Universidad de Santiago de Chile) Quasi-randomness and (hyper)graph spectra
26.06.2026
4:15 pm
A3, SR120 		Letícia Mattos (Universität Heidelberg) On the Prague dimension of sparse random graphs
10.06.2026 Weichan Liu (Shandong University) Upper bounds on the running time of bootstrap percolation
01.06.2026
4:15 pm
A3, SR024 		László Kozma (TU Dresden) Improved time-space tradeoff for TSP via extremal set systems
27.05.2026 Sebastian Tievenow (FU Berlin) Hamiltonicity of expanders
18.05.2026
4:15 pm
A3, SR120 		Dhruv Mubayi (University of Illinois Chicago) Pentagons in triple systems
13.05.2026 Silas Rathke (FU Berlin) Maker-Breaker games on a budget
29.04.2026
4:15 pm
A3, SR024 		Jack Allsop (FU Berlin) Substructures in random Latin squares
22.04.2026
4:15 pm
A3, SR024 		Zhuo Wu (Universitat Politècnica de Catalunya) Chromatic thresholds for linear equations and recurrence
19.03.2026 Bogdan Chornomaz (Technion) Topological tools in PAC learning
18.02.2026
4:15 pm
A3, SR120 		Rajko Nenadov (University of Canterbury) Universality for graphs and hypergraphs
22.01.2026
4:15 pm
A3, SR120 		Jakob Zimmermann (FU Berlin) Bipartite Turán problem on cographs
14.01.2026
4:15 pm
A3, SR120 		Felix Clemen (University of Victoria) Regular Simplices in Higher Dimensions
08.01.2026 Michael Zheng (Emory University) A Lovász-Kneser theorem for triangulations

Abstracts

02.07.2026
Hiệp Hàn (Universidad de Santiago de Chile)
Quasi-randomness and (hyper)graph spectra
Abstract: Spectral aspects have played a central role in the theory of quasi-randomness and regularity approximation. For example, dense quasi-random graphs can be characterized by the spectral gap between the top eigenvalue and the so-called second eigenvalue, while Frieze and Kannan showed that the spectral decomposition of a graph can be utilized to regularize it. In an on-going project, we investigate related questions and phenomenons for sparse graphs and hypergraphs. In particular, we study quasi-randomness, spectral regularity and the Hoffman's bound for hypergraphs relying on the variational notion of hypergraphs eigenvalues due to Friedman-Wigderson. Several applications will be discussed.
26.06.2026
Letícia Mattos (Universität Heidelberg)
On the Prague dimension of sparse random graphs
Abstract: The Prague dimension of a graph \(G\) is defined as the minimum number of complete graphs whose direct product contains \(G\) as an induced subgraph. Introduced in the 1970s by Nešetřil, Pultr, and Rödl – and motivated by the work of Dushnik and Miller, as well as by the induced Ramsey theorem – determining the Prague dimension of a graph is a notoriously hard problem.

In this talk, we will show that for all \(ε > 0\) and \(p\) such that \(n^{−1+ε} ≤ p ≤ n^{−ε}\), with high probability the Prague dimension of \(G(n,p)\) is \(Θ_ε(pn)\), which improves upon a recent result by Molnar, Rödl, Sales and Schacht. Inspired by the work of Bennett and Bohman, our approach centres on analysing a random greedy process that builds an independent set of size \(Ω(\log(pn)/p)\) by iteratively selecting vertices uniformly at random from the common non-neighbourhood of those already chosen. Using the differential equation method, we show that every non-edge is essentially equally likely to be covered by this process, which is key to establishing our bound. Based on a joint work with Felix Joos.
10.06.2026
Weichan Liu (Shandong University)
Upper bounds on the running time of bootstrap percolation
Abstract: For \(k\)-graphs \(F\) and \(H_0\) the \(F\)-bootstrap percolation process (or \(F\)-process) starting with \(H_0\) is a sequence \((H_i)_{i\geq0}\) of \(k\)-graphs such that \(H_{i+1}\) is obtained from \(H_i\) by adding all those \(e\in V(H_0)^{(k)}\setminus E(H_i)\) as edges that complete a new copy of \(F\). The running time of this \(F\)-process, denoted by \(M_F(H_0)\), is the smallest \(i\) with \(H_i=H_{i+1}\). Bollobás proposed the problem of determining the maximum running time for \(n\in\mathbb{N}\), i.e., \(M_F(n)=\max_{\vert V(H_0)\vert=n}M_F(H_0)\). This problem has received a lot of attention recently and various lower bound constructions are known, some with connections to additive combinatorics. However, upper bounds have remained notoriously difficult. For instance, before our work, the best known upper bound for \(M_{K_t}(n)\), with \(t\geq5\), was the trivial bound \(\binom{n}{2}\).

Here we discuss our recent work providing the first non-trivial upper bound for this problem. In fact, our result provides a non-trivial upper bound on the running time of the \(F\)-process for every \(k\)-graph \(F\). Curiously, we obtain this upper bound by connecting this problem with the Turán problem. In addition, we introduce another recent work in which we prove that the running time of the bootstrap percolation process for extension hypergraphs is bounded by a constant.

Based on joint work with Schülke and Zhang, and with Nie, Piga, and Schülke.
01.06.2026
László Kozma (TU Dresden)
Improved time-space tradeoff for TSP via extremal set systems
Abstract: The best known exact algorithms for the traveling salesman problem (TSP) achieve \(2^n\) time and \(2^n\) space, or \(4^n\) time and polynomial space. (Bellman, Held, Karp, resp., Savitch, Gurevich, Shelah). An easy combination of the two approaches yields a tradeoff between \(T^n\) time and \(S^n\) space at certain points of the curve \(TS = 4\).

We give a tradeoff scheme that improves upon this for all \(2<T<4\), in particular yielding a minimum of \(TS < 3.572\). The result hinges on a natural combinatorial question about the existence of sparse set systems with many maximal chains.

Joint work with Justin Dallant.
27.05.2026
Sebastian Tievenow (FU Berlin)
Hamiltonicity of expanders
Abstract: An \(n\)-vertex graph \(G\) is a \(C\)-expander if \(|N(X)|\geq C|X|\) for every \(X\subseteq V(G)\) with \(|X|< n/2C\) and there is an edge between every two disjoint sets of at least \(n/2C\) vertices. In this talk, we will take a look at the work of Draganić, Montgomery, Correia, Pokrovskiy and Sudakov, who managed to complete a long line of research on the Hamiltonicity of sparse graphs by proving the existence of a constant \(C>0\) for which every \(C\)-expander is Hamiltonian.
18.05.2026
Dhruv Mubayi (University of Illinois Chicago)
Pentagons in triple systems
Abstract: We consider the question of determining the number of pentagons in a linear triple system and show some connections to number theory, graph theory, theoretical computer science, and geometry. This is joint work with Jozsef Solymosi.
13.05.2026
Silas Rathke (FU Berlin)
Maker-Breaker games on a budget
Abstract: We introduce a new variant of the Maker-Breaker game where Breaker is allowed to keep edges as a budget to use them in later rounds. We will see that this can drastically change the threshold bias for some games. However, for the \(H\)-game, the order of magnitude stays the same. We then focus on the triangle game where it is widely open to determine the constant factor of the threshold function in the original Maker Breaker game. For the budget version, we determine the threshold function precisely. Finally, we consider a game which lies between the original and the budget version of the triangle game. There, we are also able to determine the constant factor of the threshold function. Joint
work with Sebastian Lüderssen and Fabien Nießen.
29.04.2026
Jack Allsop (FU Berlin)
Substructures in random Latin squares
Abstract: In this talk, we will discuss the probability of substructures occurring in random Latin squares. A consequence of our main result is that for a partial Latin square \(P\) of order \(n\) with \(o(n)\) non-empty rows and columns (as \(n \to \infty\)) and \(k\) total non-empty cells and a random Latin square \(\mathbf{L}\) of order \(n\), the probability that \(\mathbf{L}\) contains \(P\) lies between \(((1/22-o(1))/n)^k\) and \(((22+o(1))/n)^k\). We apply this result to subsquares in random Latin squares to obtain the first proof of the fact that the expected number of subsquares of order \(3\) in a random Latin square of order \(n\) is non-vanishing as \(n \to \infty\). We are also able to provide the best known asymptotics for the expected number of subsquares of any order \(m\) in a random Latin square of order \(n\) for any \(m\) satisfying \(4 \leq m \leq \alpha n\) with \(\alpha < 1/3\).
22.04.2026
Zhuo Wu (University of Warwick)
Chromatic thresholds for linear equations and recurrence
Abstract: Motivated by classical problems in extremal graph theory, we study a chromatic analogue of Roth-type questions for linear equations over \(\mathbb F_p\). Given a homogeneous equation \(\mathcal L:\sum_{i=1}^k c_i x_i=0\) with \(k\ge 3\), we study \(\mathcal L\)-solution-free sets \(A\subseteq \mathbb F_p\) through the chromatic number of the Cayley graph \(\mathsf{Cay}(\mathbb F_p,A)\). We introduce the \emph{chromatic threshold} \(\delta_\chi(\mathcal L)\), the minimum density that guarantees bounded chromatic number of \(\mathsf{Cay}(\mathbb F_p,A)\) among all \(\mathcal L\)-solution-free sets \(A\), and determine exactly when \(\delta_\chi(\mathcal L)=0\). Strikingly, this happens if and only if \(\mathcal L\) contains a zero-sum subcollection of at least three coefficients.


A key ingredient is a quantitative chromatic lower bound for Cayley graphs on \(\mathbb Z_p^n\) generated by Hamming balls around the all-ones vector. This is achieved by introducing a new Kneser-type graph that admits a natural embedding into \(\mathbb Z_p^n\), together with an equivariant Borsuk--Ulam type argument. As a consequence, we resolve a question of Griesmer. We also relate our classification to the hierarchy of measurable, topological, and Bohr recurrence.
19.03.2026
Bogdan Chornomaz (Technion)
Topological tools in PAC learning
Abstract: In the past few years, together with several collaborators, we have developed a framework linking PAC learning theory to topological combinatorics. At its core lies the notion of the spherical dimension of a concept class. Since the most established complexity measure in PAC learning is VC dimension, a natural question arises: can spherical dimension be bounded in terms of VC dimension? This question is compelling from both the learning-theoretic and the topological standpoint. In this talk, I will outline how the connection between these two dimensions arises, and survey what we know, and don't know, about their relation.
18.02.2026
Rajko Nenadov (University of Canterbury)
Universality for graphs and hypergraphs
Abstract: A graph \(G\) is universal for a (finite) family of graphs if every graph H from this family is a (not necessarily induced) subgraph of \(G\). The complete graph with \(n\) vertices is universal for the family of all graphs with \(n\) vertices, and this is clearly the smallest universal graph for this family. However, if we restrict our attention to a family of graphs with some additional properties, more efficient (in terms of the number of edges) universal graphs might exist. This is a natural combinatorial question, with applications in VLSI circuit design, data storage, and simulation of parallel computer architecture.

The problem of estimating the minimum possible number of edges in a universal graph for various families has received a considerable amount of attention. The previous work deals with families of graphs with properties which naturally bound their density, such as graphs with bounded maximum degree, forests and, more generally, graphs with bounded degeneracy, as well as families of graphs with additional structural properties such as planar graphs and graphs with small separators, to name a few.

In this talk I will present state of the art and discuss commonly used techniques, as well as state some interesting open problems.
22.01.2026
Jakob Zimmermann (FU Berlin)
Bipartite Turán problem on cographs
Abstract: A cograph is a graph that contains no induced path \(P_4\) on four vertices or equivalently a graph that can be constructed from vertices by sum and product operations.
We study the bipartite Turán problem restricted to cographs: for fixed integers \(s \leq t\), what is the maximum number of edges in an \(n\)-vertex cograph that does not contain \(K_{s,t}\) as a subgraph?
This problem falls within the framework of induced Tur\'an numbers \(\text{ex}(n, \{K_{s,t}, P_4\text{-ind}\})\) introduced by Loh, Tait, Timmons, and Zhou.

Our main result is a Pumping Theorem : for every \(s\le t\) there exists a period \(R\) and core cographs such that for all sufficiently large \(n\) an extremal cograph is obtained by repeatedly pumping one designated pumping component inside the appropriate core (depending on \(n\bmod R\)). We determine the linear coefficient of \(\text{ex}(n, \{K_{s,t}, P_4\text{-ind}\})\) to be \(s-1 + \frac{t-1}{2}\). Moreover, the pumping components are \((t-1)\)-regular and have \(s-1\) common neighbours in the respecitve core graphs, giving the extremal cographs a particularly rigid extremal star-like shape.

Motivated by the rarity of complete classification of extremal configurations, we completely classify all \(K_{3,3}\)-free extremal cographs by proof. We also develop a dynamic programming algorithm for enumerating extremal cographs for small \(n\).
14.01.2026
Felix Clemen (University of Victoria)
Regular Simplices in Higher Dimensions
Abstract: A classical problem in combinatorial geometry, posed by Erdős in 1946, asks to determine the maximum number of unit segments in a set of \(n\) points in the plane. Since then a great variety of extremal problems in finite point sets have been studied. Here, we look at generalizations of this question concerning regular simplices. Among others we answer the following question asked by Erdős: Given \(n\) points in \(\mathbb{R}^6\), how many triangles can be equilateral triangles? For our proofs we use hypergraph Turán theory and linear algebra. This is joint work with Dumitrescu and Liu.
08.01.2026
Michael Zheng (Emory University)
A Lovász-Kneser theorem for triangulations
Abstract: We show that the Kneser graph of triangulations of a convex n-gon has chromatic number \(n - 2\). Joint work with Anton Molnar, Cosmin Pohoata, and Daniel G. Zhu

Links

Archives