Organizers : Jeff Kahn, Bhargav Narayanan, Swee Hong Chan, and Natalya Ter-Saakov
Date: May 5, 2025
Speaker: Guy Moshkovitz (CUNY)
Title: Ranks and graphs
Abstract: I will discuss a curious property of graphs whose edge set is the solution set of (bilinear) equations, and how it turned out to be important in a recent resolution of the slice rank vs analytic rank problem, the first interesting case of an important conjecture in additive combinatorics.
Based on joint work with Daniel Zhu
Date: April 28, 2025
Speaker: Vishesh Jain (UIllinois-Chicago)
Title: Hitting time mixing for the random transposition walk
Abstract: Consider shuffling a deck of $n$ cards, labeled $1$ through $n$, as follows: at each time step, pick one card uniformly with your right hand and another card, independently and uniformly with your left hand; then swap the cards. How long does it take until the deck is close to random? Diaconis and Shahshahani showed that this process undergoes cutoff in total variation distance at time $t = \lfloor n\log{n}/2 \rfloor$. Confirming a conjecture of N.~Berestycki, we prove the definitive ``hitting time'' version of this result: let $\tau$ denote the first time at which all cards have been touched. The total variation distance between the stopped distribution at $\tau$ and the uniform distribution on permutations is $o_n(1)$; this is best possible, since at time $\tau-1$, the total variation distance is at least $(1+o_n(1))e^{-1}$. Joint work with Mehtaab Sawhney (Columbia University)
Date: April 14, 2025
Speaker: James Leng (UCLA)
Title: Szemerédi’s theorem, primes, and nilsequences
Abstract: Let $r_k(N)$ be the largest subset of $[N] = \{1, \dots, N\}$ with no k-term arithmetic progression. Szemerédi’s theorem states that $r_k(N) = o_k(N)$. We will go over the proof that achieves the best known upper bounds for $r_k(N)$ for general $k$. We will discuss how the mathematics behind the proof relates to counting primes along linear forms and the distribution of orbits on $G/\Gamma$ with $G$ nilpotent and $\Gamma$ discrete and cocompact. This is (partly) based on joint work with Ashwin Sah and Mehtaab Sawhney.
Date: April 7, 2025
Speaker: Youming Qiao (University of Technology, Sydney)
Title: Connections Between Graphs and Matrix Spaces
Abstract: In this talk, we examine some connections between graphs and matrix spaces (linear spaces of matrices). To begin, certain matrix spaces arise naturally from graphs, a construction that dates to the works of Tutte, Edmonds, and Lovász on perfect matchings. Their works established a link between perfect matchings and full-rank matrices. Extending from there, we first show more correspondences between graph structures and matrix space structures, such as independent sets and totally-isotropic spaces, graph connectivity and orthogonal decompositions, and isomorphism notions.
These correspondences between structures also translate to graph-inspired questions and techniques for matrix spaces. We will give a sample of them, such as alternating paths, independence polynomials, Turán and Ramsey type questions, (as time permits :)) expanders (spectral or combinatorial), and threshold phenomena. Many of these techniques and results are motivated by and find applications in other areas, such as invariant theory, group theory, quantum information, and geometry.
Based on joint works with Avi Wigderson, Yuval Wigderson, Gábor Ivanyos, Yinan Li, Chuanqi Zhang, Markus Bläser.
Date: March 31, 2025
Speaker: Daniel McGinnis (Princeton)
Title: A necessary and sufficient condition for $k$-transversals.
Abstract: We solve a long-standing open problem posed by Goodman and Pollack in 1988 by establishing a necessary and sufficient condition for a finite family of convex sets in $\mathbb{R}^d$ to admit a $k$-transversal (a $k$-dimensional affine subspace that intersects each set) for any $0 \le k \le d-1$. This result is a common generalization of Helly's theorem ($k=0$) and the Goodman-Pollack-Wenger theorem ($k=d-1$).
This is joint work with Nikola Sadovek.
Date: March 24, 2025
Speaker: Wesley Pegden (CMU)
Title: Probability spaces driven by geometric constraints
Abstract: What can we understand about probability spaces on "nice" partitions of a geometric region? Can we design efficient samplers for geometric partitions of a region? Can we at least detect extreme outliers? These questions have become particularly salient in the past several years as the techniques developed by mathematicians are now applied to conduct statistical analyses of things like U.S. political districtings. We will discuss some recent developments on probability spaces defined by geometric constraints, including positive and negative results on the mixing times of relevant Markov chains, Markov chain methods which eschew mixing-time requirements, and direct sampling methods.
Date: March 10, 2025
Speaker: Alex Fink (QMUL, IAS)
Title: Speyer's tropical f-vector conjecture and its proof
Abstract: In 2008, looking to bound the face vectors of tropical linear spaces, Speyer introduced the g-invariant of a matroid. He proved its coefficients nonnegative for matroids representable in characteristic zero and conjectured this in general. After introducing these objects, this talk will give an overview of the ingredients in recent work with Andrew Berget that proves the conjecture. A main character is the variety of coordinatewise quotients of points in two linear subspaces, and its initial degenerations which encode a new generalization of external activity to a pair of matroids.
Date: March 3, 2025
Speaker: Richard Montgomery (Warwick, IAS)
Title: Finding regular subgraphs
Abstract: Finding regular subgraphs can be useful. Many results assume a graph is regular or are easier to prove when they are. In 1975, Erdős and Sauer asked for an estimate, for any constant r, on the maximum number of edges an n-vertex graph can have without containing an r-regular subgraph (one in which each vertex is in r edges). The best upper bound on this problem was for a long time one of Pyber from 1985, but the last few years have seen rapid developments, initiated by Janzer and Sudakov, and we now have an efficient framework to find regular subgraphs for not only constant r but the whole range of possible values of r.
I will discuss this framework and its components, which include algebraic techniques of Alon, Friedland and Kalai, the recent breakthroughs on the sunflower conjecture, techniques to find almost-regular subgraphs developed from Pyber’s work, and, crucially, a novel random process that efficiently finds a very nearly regular subgraph in any almost-regular graph.
Joint work with Debsoumya Chakraborti, Oliver Janzer and Abhishek Methuku.
Date: February 24, 2025
Speaker: Huy Tuan Pham (IAS)
Title: Random Cayley graphs and Additive combinatorics from a combinatorial perspective
Abstract: Cayley graphs provide interesting bridges between graph theory, additive combinatorics and group theory. Fixing an ambient finite group, random Cayley graphs are constructed by choosing a generating set at random. These graphs reflect interesting symmetries and properties of the group, at the cost of inducing complex dependencies. I will discuss several insights and stories that we have learned from the analysis of cliques and independent sets in random Cayley graphs.
Date: February 17, 2025
Speaker: Maria-Romina Ivan (Cambridge, IAS)
Title: Posets with Unbounded Saturation Number
Abstract: A poset is short for a partially ordered set. The most common example of a poset is the power set of $[n]$ with the partial relation given by inclusion. Given a fixed poset $\mathcal P$, we say that a family $\mathcal F$ of subsets of $ [n]$ is $\mathcal P$-free if there is no induced copy of $\mahcal P$ formed by elements of $\mathcal F$. We further say that $\mathcal F$ is $\mathcal P$-saturated if it is $\mathcal P$-free and, for any other set $X$ not in $\mathcal F$, the family formed by adding $X$ to $\mathcal F$ contains an induced copy of $\mathcal P$. The size of the smallest $\mathcal P$-saturated family is called the induced saturation number of $\mathcal P$.
The natural question is: what can we say about the saturation number? Even for simple posets such as the the antichain and the butterfly, the question has proved difficult – for the diamond poset the question is surprisingly wide open.
How about the saturation number for an arbitrary poset $\mathcal P$? Freschi, Piga, Sharifzadeh and Treglown proved that the saturation number for any poset is either bounded, or at least $\sqrt n$. What about the upper bound? Or, can we characterise the posets that have unbounded saturation number?
In this talk we will discuss recent developments, most notably a wide class of posets that have unbounded saturation number, as well as a general polynomial upper bound.
Date: February 3, 2025
Speaker: Max Aires (Rutgers)
Title: Balancing extensions in posets of large width
Abstract: A linear extension of P is a linear ordering compatible with the poset relations. Let p(x<y) be the probability that x precedes y in a uniformly random linear extension, and let δ(x,y)=min(p(x<y),p(y<x)) and δ(P) be the maximum value of δ(x,y) over all x,y in P. The following two conjectures about δ(P) are both well-known:
(The "1/3-2/3 Conjecture") δ(P) ≥ 1/3 whenever P is not a chain.
(The "Kahn-Saks Conjecture") δ(P) → 1/2 as w(P) → ∞ (where w(P) is the maximum size of an antichain in P).
While still far from either of these, we prove a number of conditions for δ(P) → 1/2 and δ(P) ≥ 1/e - o(1), using a mix of geometric and probabilistic techniques. Joint with Jeff Kahn.
Date: January 27, 2025
Speaker: Orit Raz (IAS)
Title: Erdős unit distance problem and graph rigidity
Abstract: Erdős unit distance problem asks the following: Let $P$ be a set of $n$ distinct points in the plane, and let $U(P)$ denote the number of pairs of points in $P$ that are at distance 1. How large can $U(P)$ be? In 1946, Erdős showed that for $P=[\sqrt{n}]\times [\sqrt{n}]$, one has $U(P)=\Theta(n^{1+\frac{c}{\log\log n}})$, for some constant $c>0$, and he conjectured that this is best possible. While the problem has received a lot of attention, the best upper bound, established by Spencer, Szemerédi, and Trotter in 1984, is $U(P)=O(n^{4/3})$, with no progress in the last 40 years. One reason for the difficulty of the problem is that the current combinatorial geometry tools, dealing with properties of unit circles, actually apply to more general families of curves. For the latter families, the upper bound of $O(n^{4/3})$ is, in fact, tight.
In the talk, I will introduce a completely new approach to the unit distance problem, relating the problem to a question in graph rigidity theory. Specifically, I will present a new structure theorem, that applies to point configurations with many unit distances, and pose a new conjecture regarding rigid subgraphs. I will then explain how a solution of the rigidity conjecture, would, for the first time, yield an improvement of the aforementioned upper bound for the unit distance problem. If time permits, I will explain how to prove a weaker version of the rigidity conjecture, by reducing the problem to a line-line incidence question in $\mathbb{R}^3$.
The talk is based on a joint work with J. Pach and J. Solymosi.