Organizers : Jeff Kahn, Bhargav Narayanan, Swee Hong Chan, and Natalya Ter-Saakov
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.