Seminars and Colloquia by Series

Path partitions in regular (directed) graphs

Series
Combinatorics Seminar
Time
Friday, April 24, 2026 - 15:15 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Akif Yildiz – Centrum Wiskunde & Informatica –

As a generalization of Hamiltonicity problems, one may consider partitioning the vertices of a (directed) graph into as few paths (or cycles) as possible. Ore's classical theorem gives a tight upper bound on the number of paths needed to cover an n-vertex graph, with imbalanced bipartite graphs showing that the bound is best possible. A conjecture of Magnant and Martin (2009) suggests that Ore's bound can be significantly improved for regular graphs. This is also connected to the famous linear arboricity conjecture and has attracted considerable attention in recent years, including a very recent result establishing the conjecture up to a factor of two. In this talk, I will discuss directed and oriented variants of this conjecture and present some results in these settings. Based mostly on joint work with Allan Lo and Viresh Patel.

Spanning trees and discrete curvature on graphs

Series
Combinatorics Seminar
Time
Friday, April 17, 2026 - 15:15 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Karel Devriendt – Oxford University

Kirchhoff's celebrated matrix tree theorem expresses the number of spanning trees of a graph as a minor of the Laplacian matrix of the graph. In modern language, this determinantal counting formula reflects the fact that spanning trees in a graph form a regular matroid. In this talk, I will give a short historical overview of the tree-counting problem and a related quantity from electrical circuit theory: the effective resistance. I will describe a characterization of effective resistances in terms of a certain polytope and discuss a recent application to discrete notions of curvature on graphs. The talk is based on the article: https://arxiv.org/abs/2410.07756

Randomly piercing algebraic sets

Series
Combinatorics Seminar
Time
Friday, April 3, 2026 - 15:15 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Nathan Tung – Stanford University –

How large of a random subset $D \subset \mathbb{F}_p^n$ does one need to almost surely intersect zero sets cut out by at most $s$ polynomials each of degree at most $k$? We determine the sharp threshold for this problem for all fixed $s$ and $k$. A corollary is that there exists a dense subset $A \subset \mathbb{F}_p^n$ free of k-term arithmetic progressions with common difference in a sufficiently small $D$, improving the lower bound for what is known as Szemerédi’s theorem with random differences. Our bound is the first to capture dependence of $|D|$ on $|A|$ in the finite field setting, giving better dependence than what is known in the integers. Based on joint work with Daniel Altman.

Ramsey and Turán numbers of sparse hypergraphs

Series
Combinatorics Seminar
Time
Friday, February 27, 2026 - 15:15 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jonathan Tidor – Princeton University –

The degeneracy of a graph is a measure of sparseness that appears in many contexts throughout graph theory. In extremal graph theory, it is known that graphs of bounded degeneracy have Ramsey number which is linear in their number of vertices (Lee, 2017). Also, the degeneracy gives good bounds on the Turán exponent of bipartite graphs (Alon--Krivelevich--Sudokav, 2003). Extending these results to hypergraphs presents a challenge, as it is known that the naïve generalization of these results -- using the standard notion of hypergraph degeneracy -- are not true (Kostochka--Rödl 2006). We define a new measure of sparseness for hypergraphs called skeletal degeneracy and show that it gives information on both the Ramsey- and Turán-type properties of hypergraphs.

 

Based on joint work with Jacob Fox, Maya Sankar, Michael Simkin, and Yunkun Zhou

Exact threshold for non-linear Hamilton cycles

Series
Combinatorics Seminar
Time
Friday, February 6, 2026 - 15:15 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Byron Chin – MIT –

For positive integers $r > \ell \geq 1$, an $\ell$-cycle in an $r$-uniform hypergraph is a cycle where each edge consists of $r$ vertices and each pair of consecutive edges intersect in $\ell$ vertices. For $\ell \geq 2$, we determine the exact threshold for the appearance of Hamilton $\ell$-cycles in an Erd\H{o}s--R\'enyi random hypergraph, confirming a conjecture of Narayanan and Schacht. The main difficulty is that the second moment is not tight for these structures. I’ll discuss how a variant of small subgraph conditioning and a subsampling procedure overcome this difficulty.

Improving $R(3,k)$ in just two bites

Series
Combinatorics Seminar
Time
Friday, January 23, 2026 - 15:15 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Florian Pfender – University of Colorado Denver –

We present a random construction proving that the extreme off-diagonal Ramsey numbers satisfy $R(3,k)\ge  \left(\frac12+o(1)\right)\frac{k^2}{\log{k}}$ (conjectured to be asymptotically tight), improving the previously best bound $R(3,k)\ge  \left(\frac13+o(1)\right)\frac{k^2}{\log{k}}$. In contrast to all previous constructions achieving the correct order of magnitude, we do not use a nibble argument.

Beyond the paper, we will explore a bit further how the approach can be used for other problems.

Longest Common (and Increasing) Subsequences in Random Words: Differences and Similarities

Series
Combinatorics Seminar
Time
Friday, November 21, 2025 - 15:15 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Christian Houdre – Georgia Institute of Technology –

Let $LC_n$ be the length of the longest common subsequences of two independent random words whose letters are taken  

in a finite alphabet and when the alphabet is totally ordered, let $LCI_n$ be the length of the longest common and increasing subsequences of the words.   Results on the asymptotic means, variances and limiting laws of these well known random objects will be described and compared.  

Local Permutation Removal;

Series
Combinatorics Seminar
Time
Friday, November 14, 2025 - 15:15 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Ruilin Shi – Duke University –

The permutation removal lemma was first proved by Klimosová and Král’, and later reproved by Fox and Wei in the context of permutation property testing. In this talk, we study a local version of the permutation removal problem. We show that for any permutation σ not equal to 12, 21, 132, 231, 213, or 312, there exists ε(σ) > 0 such that for any sufficiently large integer N, there is a permutation π of length N that is ε-far from being σ-free with respect to the ρ∞ distance, yet contains only a single copy of σ. Here, the ρ∞ distance is defined as an L∞-variant of the Earth Mover’s Distance between two permutations. We will also discuss our result on the local induced graph removal problem. This is joint work with Fan Wei.

Problems and Results for Geometric Graphs and Hypergraphs

Series
Combinatorics Seminar
Time
Friday, October 24, 2025 - 15:15 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jacques Verstraëte – University of California San Diego –

A geometric graph consists of a set of points in the plane together with line 

segments between some pairs of points. A convex geometric graph is a geometric graph whose 

points are in convex position. We present some old and new extremal results and applications, 

and their extension to geometric hypergraphs, together with a variety of open problems. 

 

Partly joint work with Zoltan Furedi, Tao Jiang, Sasha Kostochka and Dhruv Mubayi

Pages