Schedule and Abstracts 2025/2026

If not stated otherwise, the talk will take place Wednesdays starting at 4:15pm in A3/SR 119
Date Speaker Title
18.05.2026
4:15 pm
A3, SR120 		Dhruv Mubayi (University of Illinois Chicago) Pentagons in triple systems
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

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\).
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.
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