Organizers : Jeff Kahn, Bhargav Narayanan, Swee Hong Chan, and Natalya Ter-Saakov
Date: November 10, 2025 at 2:00pm
Speaker: Sammy Luo (MIT)
Title: Mutually touching infinite cylinders and Ramsey theory
Abstract: Littlewood asked for the maximum number $N$ of congruent infinite cylinders that can be arranged in $\mathbb{R}^3$ so that every pair touches. In this talk, we discuss the techniques behind some recent improvements on the upper bounds for this problem, culminating in our recent result showing that $N \leq 10$. Paired with a lower bound by Bozóki, Lee, and Rónyai, this establishes that $N \in \{7,8,9,10\}$. Our method is based on linear algebra and Ramsey theory, and makes partial use of computer verification.
Based on joint work with Travis Dillon and Junnosuke Koizumi.
Date: November 3, 2025 at 2:00pm
Speaker: Jonathan Tidor (Princeton University)
Title: Triangle-Ramsey numbers of complete graphs
Abstract: A graph G is called H-Ramsey if every 2-coloring of the edges of G contains a monochromatic copy of H. In general, Ramsey theory studies minimal H-Ramsey graphs: the classical Ramsey number, r(H), can be defined to be the minimum number of vertices in an H-Ramsey graph. The size Ramsey number, introduced by Erdős, Faudree, Rousseau, and Schelp, is defined to be the minimum number of edges in an H-Ramsey graph. We study a generalization of these two notions, the triangle-Ramsey number, defined to be the minimum number of triangles in an H-Ramsey graph. Answering a question of Spiro, we prove that for t sufficiently large, the triangle-Ramsey number of K_t is equal to its Ramsey number choose 3. This generalizes a classical result of Chvátal on the size-Ramsey number of K_t. Our proof uses a number of techniques from probabilistic coloring of graphs.
Based on joint work with Jacob Fox and Shengtong Zhang.
Date: October 27, 2025 at 2:00pm
Speaker: Lior Gishboliner (University of Toronto)
Title: VC-dimension for hypergraphs: improved bounds
Abstract: VC-dimension is an important notion with several applications in graph theory. A fundamental result is that graphs of bounded VC dimension have (small) homogeneous vertex-partitions, i.e., partitions where almost every pair of parts has density close to 0 or 1. Recently, Chernikov and Towsner proved a hypergraph generalization of this fact. The quantitative aspects of their result remain open. I will present some recent progress on this problem, answering two questions of Terry. This is a joint work with Asaf Shapira and Yuval Wigderson.
Date: October 20, 2025 at 2:00pm
Speaker: Boris Bukh (Carnegie Mellon University)
Title: The Oddtown problem modulo a composite number
Abstract: The Oddtown problem is the perhaps the simplest application of the linear algebra method to extremal combinatorics. Motivated by the desire to better understand the method, we examine the generalization to composite moduli.
A family of subsets of $[n]$ is $\ell$-Oddtown if the size of each set is divisible by $\ell$, but no intersection is divisible by $\ell$. How large can $\ell$-Oddtown be? We explain the history of the problem, present the best known bound due to Szegedy, and our improvement to it.
Joint work with Ting-Wei Chao and Zeyu Zheng.
Date: October 13, 2025 at 2:00pm
Speaker: Doron Puder (Tel Aviv University)
Title: Aldous-type spectral gaps in Unitary groups
Abstract: Around 1992, Aldous made the following bold conjecture. Let A be any set of transpositions in the symmetric group Sym(N). Then the spectral gap of the Cayley graph Cay(Sym(N),A) is identical to that of a relatively tiny N-vertex graph defined by A. So even though the spectrum of the Cayley graph contains N! eigenvalues, the largest non-trivial one always comes from a tiny pool of N of them. This conjecture was proven nearly 20 years later by Caputo, Liggett and Richthammer (JAMS, 2010).
Driven by the conviction that such a stunning phenomenon cannot possibly be isolated, Gil Alon and I found a probable parallel of this phenomenon in the unitary group U(N). We have a concrete conjecture supported by simulations, and we prove it in several non-trivial special cases. As it turns out, the corresponding spectrum in the case of U(N) contains the one in Sym(N). Moreover, the critical part of the spectrum in U(N) coincides with the spectrum of an interesting discrete process.
In the talk, I will try to convey these ideas and some of the proofs.
Date: September 22, 2025 at 2:00pm
Speaker: John Byrne (University of Delaware)
Title: New constructions and bounds for nonabelian Sidon sets with applications to Turán-type problems
Abstract: An Sk-set is a subset of a group whose k-tuples have distinct products. An Sk'-set is a subset of a group whose bipartite Cayley graph has no cycle of length 2k. We give explicit constructions of large Sk-sets in the symmetric and alternating groups and of S2-sets in direct powers of these groups. We give probabilistic constructions for 'nice' groups which obtain large S2'-sets in the symmetric group. We also give upper bounds on the size of Sk-sets in certain groups, improving the trivial bound by a constant multiplicative factor. We describe some connections between Sk-sets and extremal graph theory. In particular, we determine up to a constant factor the minimum outdegree of a digraph which guarantees even cycles with certain orientations. As applications, we improve the upper bound on Hamilton paths which pairwise create a two-part cycle of given length, and we show that a directed version of the Erdős-Simonovits compactness conjecture is false. This talk is based on joint work with Michael Tait.
Date: September 15, 2025 at 2:00pm
Speaker: Colin Defant (Harvard University)
Title: Random Combinatorial Billiards and Stoned Exclusion Processes
Abstract: Combinatorial billiards concerns rigid and discretized billiard systems that can be modeled combinatorially or algebraically. I will introduce a random combinatorial billiard trajectory depending on some fixed probability p; when p tends to 0, it recovers Thomas Lam's reduced random walk. This random billiard trajectory can also be interpreted as a random growth process on core partitions. The analysis of the random billiard trajectory relies on new finite Markov chains called stoned exclusion processes, which are variants of certain interacting particle systems. These processes have remarkable stationary distributions determined by well-studied polynomials such as ASEP polynomials, inhomogeneous TASEP polynomials, and open boundary ASEP polynomials; in many cases, it was previously not known how to construct Markov chains with these stationary distributions.