Princeton Combinatorics Learning Seminar

January 30: Jonathan Tidor
Title ― Distinct distances and the polynomial method I
Abstract ― In 2010, Guth and Katz proved that a set of n points in the plane determine at least n/log n pairwise distinct distances. This essentially resolves a longstanding conjecture of Erdos called the distinct distances problem. Their proof introduced a new tool called the "polynomial method" (more specifically, "polynomial partitioning") which has become a very important technique in discrete geometry in the years since.

February 6: Alex Divoux
Title ― Distinct distances and the polynomial method II
Abstract ― In this talk, we prove the Szemerédi-Trotter theorem using polynomial partitioning. To do so, we first prove polynomial partitioning, a tool introduced by Guth and Katz in 2015 which guarantees the existence of a low degree polynomial whose zero set partitions R^n in a nice way. This talk will be the second in a series of five on the polynomial method.

February 13: Varun Sivashankar
Title ― Distinct distances and the polynomial method III
Abstract ― In this talk, we will discuss a result of Guth and Katz that shows that any N points in the plane determine at least n^(1-eps) distinct distances. The argument involves constructing a line for every pair of points and studying the incidence geometry of this set of lines. We will assume without proof a bound on the number of lines contained in an irreducible algebraic surface, which will be the focus of the next talk in this series.

February 20: Julien Codsi
Title ― Distinct distances and the polynomial method IV
Abstract ― In the previous talk, we saw that a strong upper bound on the number of r-rich points determined by a set of lines in R^3, under the assumption that not too many lines lie in any given irreducible algebraic surface, yields a corresponding lower bound for the distinct distances problem. In this talk, we explain how such bounds can be obtained using polynomial partitioning.

February 27: Hung-Hsun Hans Yu
Title ― Distinct distances and the polynomial method V
Abstract ― In this talk, we will prove the polynomial partitioning theorem for lines. We will see how the proof for points breaks and introduce new ideas to fix it.

March 19: Maya Sankar
Title ― Neighborhood complexes and Kneser graphs
Abstract ― We will discuss neighborhood complexes and box complexes, topological spaces associated to a graph which can be used to bound its chromatic number. We will see how these can be used to lower-bound the chromatic numbers of Kneser graphs

March 27: Daniel McGinnis
Title ― The topological Tverberg theorem
Abstract ― Tverberg’s theorem says that if you have (r-1)(d+1)+1 points in R^d, then the points can be partitioned into r parts so that the convex hulls of the parts all intersect. The topological Tverberg theorem states for any continuous map from the (r-1)(d+1) dimensional simplex to R^d, there are r pairwise disjoint face of the simplex whose images all intersect, but in this case, the condition that r is a prime power is needed. We discuss the proof of these results, which uses the “configuration space/test map” scheme.

April 3: Daniel Zhu
Title ― Evasiveness
Abstract ― In 1973, Aanderaa, Karp, and Rosenberg made the striking conjecture that every nontrivial monotone graph property is evasive. In 1983, Kahn, Saks, and Sturtevant proved, perhaps more strikingly, that this is true when the graph has a prime power number of vertices. We will discuss this result and its (topological) proof.

April 10: Daniel Carter
Title ― Pastures and matroid foundations
Abstract ― Pastures, defined by Baker--Lorscheid around 2018, are algebraic structures that generalize fields and have nice categorical properties. As with fields, one can consider the problem of representing a matroid over a pasture. For each matroid M there is a special pasture called the foundation F(M) such that the representations of M over a pasture P are in bijection with the pasture homomorphisms F(M) -> P. Time permitting, we will discuss the following amazing results: (1) The foundation of any matroid can be computed only knowing information about its minors of size at most 7; therefore this information is also sufficient to compute all representations of a matroid over any field. (2) A binary matroid can either be represented over all fields or only over the fields of characteristic 2 (Tutte), a similar but more complicated characterization for ternary matroids (Whittle), and a unification of these two results for matroids with no U(2,5) or U(3,5) minor.

April 24: Vanshika Jain
Title ― Long intervals in sumsets
Abstract ― In this talk I’ll discuss how repeated addition forces structure through two results, one of Lev and another of Conlon–Fox–Pham. I’ll explain Lev’s sharp threshold theorem for sumsets of dense subsets of [0,l]. Then, I’ll turn to the result of Conlon–Fox–Pham: if A is a subset of [n] and has size greater than Csqrt(n), then the sumset of A contains a homogeneous arithmetic progression of length n.

September 15: Hung-Hsun Hans Yu
Title ― Random cycle factor in regular graphs
Abstract ― It is an easy fact that a uniformly chosen permutation on n elements has log n cycles. Such permutation can be thought of as a random cycle factor of the complete directed graph (with self-loops). In general, we can ask: Given a d-regular digraph on n vertices, what is the expected number of cycles in a uniformly random cycle factor of the digraph? In this talk, I will present a recent paper by Christoph, Draganic, Girao, Hurley, Michel and Muyesser that proves a sharp O(nlog d/d) bound using the entropy method.

September 22: Sergio Cristancho
Title ― Counting homomorphisms to antiferromagnetic graphs via Lorentizian polynomials
Abstract ― The goal of this talk is to (attempt to) explain some of the ideas in an interesting new paper of Lee, Oh and Seo (arXiv:2506.13659v2). In their paper, for a large class of graphs, they obtain inequalities regarding the number of graph homomorphisms to an antiferromagnetic graph as the target. These inequalities generalize results in extremal combinatorics, such as bounds on the number of stable sets of regular graphs. Their proof involves Alexandrov-Fenchel type inequalities associated to Lorentzian polynomials obtained from graphs. To their knowledge (and mine) is the first instance of the theory of Lorentzian polynomials being used in extremal combinatorics.

September 29: Varun Sivashankar
Title ― Recent progress on the lonely runner problem
Abstract ― Suppose n people are running around a unit length circular track with variable speeds. The lonely runner conjecture states that at some point, every runner is at distance at least 1/(n+1) from the starting point. We will discuss a recent paper by Rosenfeld that resolves the conjecture for n = 7.

October 6: Daniel Zhu
Title ― Combinatorial nullstellensatz and the additive basis conjecture
Abstract ― We discuss a very recent preprint of Yu proving that given any four bases of F3^n, every vector in F3^n can be expressed as the sum of a submultiset of the union of the bases. This proves the additive basis conjecture over the finite field F3. The proof involves multivariate polynomials and can be thought of as establishing a certain "regularity-type" phenomenon over these polynomials.

October 20: Daniel Carter
Title ― Undecidability results in graph theory
Abstract ― Let H be a graph, F a finite set of graphs, and a,b,c,d four vertices in H. Is there an F-free graph containing H plus an a-b path and a c-d path? We show this problem and some others are undecidable.

October 27: Dmitry Krachun
Title ― Trace reconstruction problem
Abstract ― I will talk about the trace reconstruction problem: how to recover a binary string of length n given access to its independent “traces” — copies where each symbol is independently deleted with some probability. I will describe how the upper bound improved from exp(O(n^(1/2))) to exp(O(n^(1/3))) traces using complex analysis (Nazarov & Peres, 2017), and mention the further improvement to exp(\tilde{O}(n^(1/5))) (Chase, 2020). For lower bounds, I will present a construction of pairs of strings that cannot be distinguished with fewer than n^(5/4)/sqrt(log n) traces (Holden & Lyons, 2018), and briefly discuss the later improvement to Omega(n^(3/2)/log^7 n) (Chase, 2019). Despite all the progress, the gap between the bounds remains huge, so many open questions still persist.

November 10: Daniel McGinnis
Title ― Algebraic Shifting
Abstract ― Algebraic shifting is an operation on simplicial complexes introduced by Gil Kalai that transforms a simplicial complex to a "shifted" complex which satisfies certain nice combinatorial properties. We will discuss algebraic shifting over the polynomial ring k[x1,...xn], which essentially amounts to taking the generic initial ideal of the Stanley-Reisner ideal of a complex. The goal is to give the definition of algebraic shifting, show why algebraic shifting preserves the f-vector and topological Betti numbers of the complex, and maybe demonstrate an application of algebraic shifting.

November 17: Jason Prodromidis
Title ― The Small Subgraph Conditioning Method
Abstract ― The small subgraph conditioning method was introduced in the 1990's in order to prove that almost every regular graph has a Hamiltonian cycle. Since then, it has been used in multiple counting problems, in situations where there is control on the first and the second moment of a random variable, but the second moment method does not work. In this talk, we present this method and talk about as many applications as possible on Hamiltonian cycles, matchings and spin systems in various random graph settings.

December 1: Jiamin Wang
Title ― Universality of cutoff for riffle shuffling
Abstract ― A Gilbert--Shannon--Reeds (GSR) shuffle is performed on a deck of N cards by cutting the top n~Bin(N,1/2) cards and interleaving the two resulting piles uniformly at random. The celebrated "Seven shuffles suffice" theorem of Bayer and Diaconis established cutoff for this Markov chain: to leading order, total variation mixing occurs after precisely (3/2)log_2(N) shuffles. Later work of Lalley and the Sellke extended this result to asymmetric binomial cuts n~Bin(N,p) for all p\in (0,1). In this talk, I will talk about cutoff for riffle shuffles with general pile size distribution. This talk is based on joint work with Mark Sellke and Jialu Shi. See https://arxiv.org/abs/2510.22783.

February 4: Dmitry Krachun
Title ― Tight lower bound on A+λA for algebraic integer λ
Abstract ― Given a real (complex) number λ and a finite set A of real (complex) numbers consider the set A+λA:={a+ λb| a, b ∈ A}. It is then natural to ask how small this set can be for a set A of fixed large size. This question has been extensively studied by many authors over the last decades and essentially resolved for the case of a rational λ by B. Bukh and for a transcendental λ in a recent work by D. Conlon and J. Lim. 

In this talk I will speak about a joint work with F. Petrov in which the case of algebraic integer λ is resolved. The proof combines equivariant version of Freiman’s theorem and a structural lemma about discrete sets of positive density which allows to transfer continuous results to the discrete world.

February 11: Andrew Lin
Title ― Algorithms and reductions for learning parity with noise
Abstract ― The learning parity with noise (LPN) problem involves learning a uniformly random parity function given samples which are corrupted independently with noise. We present a 2^O(n/log n) algorithm for LPN by Blum, Kalai, and Wasserman, and a reduction from LPN in dimension k log n to k-sparse LPN in dimension n by Bangachev, Bresler, Tiegel, and Vaikuntanathan.

February 18: Daniel Carter
Title ― The minimum number of triangles in graphs with a given number of edges
Abstract ― In 2008, Razborov proved that a graph with n vertices and r * n^2/2 edges has at least
(t + 1) * (t - 2 * sqrt(t * (t - r * (t + 1)))) * (t + sqrt(t * (t - r * (t + 1))))^2 / (t^2 * (t + 1)^2) * n^3/6 - o(n^3) triangles,
where t = floor(1 / (1 - r)), and this bound is tight. We discuss the proof and some consequences.

February 25: Daniel Zhu
Title ― Edge universality in random regular graphs I
Abstract ― A recent preprint of Huang, McKenzie, and Yau proves that the distribution of the largest (and smallest) nontrivial eigenvalues of a random d-regular graph converges, after proper normalization, to the distribution of the largest eigenvalues in the Gaussian orthogonal ensemble, a ubiquitous construction in random matrix theory. As a corollary, about 69% of all d-regular graphs are Ramanjuan. This is the first of two talks about the proof, discussing the use of Stieltjes transforms in random matrix theory and a random resampling procedure used to control them.

March 4: Noah Kravitz
Title ― Edge universality in random regular graphs II
Abstract ― This is the second of two talks about the recent work of Huang, McKenzie, and Yau on the spectra of random d-regular graphs.  Last week Daniel introduced the conceptual framework for the result and proof strategy.  This week I will highlight a few of the (many) technical tools involved.

March 18: Varun Sivashankar
Title ― Local maxima of quadratic Boolean functions
Abstract ― Given a real valued quadratic function on the boolean hypercube {0,1}^n, how many strict local maxima can it have? Holzman conjectured that the answer should be binom(n,n/2) which is easily achieved. We will discuss a short but clever proof [Spink 2013] via a generalization of Sperner's lemma.

April 1: Vanshika Jain
Title ― Hitting time mixing for the random transposition walk
Abstract ― In this talk, I will present the paper Hitting Time Mixing for the Random Transposition Walk by Vishesh Jain and Mehtaab Sawhney. The paper studies the random transposition walk—a model for shuffling n cards by swapping two randomly selected cards at each step. While Diaconis and Shahshahani established a cutoff at floor(n(log n)/2) steps, Jain and Sawhney confirm Berestycki’s conjecture by proving a “hitting time” result: at the first time when every card has been touched, the deck’s distribution is nearly uniform.

April 8: Julien Codsi
Title ― The weak Hedetniemi's conjecture
Abstract ― Hedetniemi's conjecture posits a relationship between the chromatic number of a graph product and the chromatic numbers of its factor graphs. Although the conjecture has been disproven, a compelling question remains: by how much is it false? Interestingly, the answer seems to be all or nothing—the conjecture is either wildly incorrect or weakly accurate, with no middle ground.

April 25: Kevin Ren
Title ― 3D Kakeya
Abstract ― Fix small delta > 0. A Kakeya set in R^N is a union of delta^(1-N) many delta x delta x ... x delta x 1-tubes, with one tube for every possible direction. Any Kakeya set has volume at most 1; the Kakeya set conjecture states that it has volume at least C_eps delta^eps for any eps > 0. The conjecture has a classical proof by Davies and Cordoba in 2 dimensions; the higher dimensional case has proven to be much harder. We will discuss the recent resolution of the 3D case by Hong Wang and Josh Zahl.

September 12: Cosmas Kravaris
Title ― The size of the range of the simple random walk on the plane
Abstract ― Consider the standard simple random walk on the planar grid Z². Look at the range up to time n, which is the size of all the vertices visited at least once. We'll show the theorem of Dvoretzky and Erdős (1951) which states that as n goes to infinity, the size of the range divided by n/log(n) converges almost surely to π.

September 19: Daniel Carter
Title ― Automata theory methods in discrete math
Abstract ― We give some basic definitions and results in automata theory, including the notion of tree automata. We present several applications in discrete math, particularly to the study of tree decompositions and algorithms, culminating in Courcelle's theorem.

September 26: Andrew Lin
Title ― Kikuchi graphs
Abstract ― We will introduce Kikuchi graphs, which have recently been used to prove results in extremal combinatorics and theoretical computer science. To illustrate this we will present proofs of Feige's conjecture (up to logarithmic factors) on even covers in dense hypergraphs and lower bounds on locally decodable codes.

October 3: Varun Sivashankar
Title ― Number of cycle sets
Abstract ― A subset S of [n] is called a cycle set if there exists a graph G on n vertices such that the set of cycle lengths of G is equal to S. Erdos conjectured that the number of cycle sets is o(2^n). Verstraëte showed that there exists an explicit constant c such that the number of cycle sets is O(2^{n - n^c}). We will prove this by showing that almost all cycle sets must have long arithmetic progressions. [On the Number of Cycle Sets, Jacques Verstaëte]

October 10: Julien Codsi
Title ― Hamiltonicity of vertex-transitive graphs
Abstract ― In 1969, Lovász conjectured that every connected vertex-transitive graph contains a Hamiltonian path. Similarly, in 1978, Thomassen conjectured that, with finitely many exceptions, all connected vertex-transitive graphs possess a Hamiltonian cycle. Despite considerable effort, both conjectures remain open. This talk will explore recent advancements on weaker versions of these statements, as well as specific cases where these conjectures hold true.

October 24: Vanshika Jain
Title ― Strategies for bounding combinatorial discrepancy
Abstract ― Combinatorial discrepancy theory studies how to color elements of a set to minimize the imbalance across various subsets. Given a system of sets S_1,..., S_n, each a subset of {1,..., n}, and a two-coloring of the elements {1,..., n}, the discrepancy is the maximum absolute difference between the number of elements of each color in any set S_i. In this talk, we will explore one method to derive upper bounds and another to establish lower bounds on the discrepancy of a given system of sets. This presentation is inspired by Chapter 4 of Geometric Discrepancy by Matoušek.

October 31: Noah Kravitz
Title ― Tverberg's theorem, twice over
Abstract ― Tverberg's Theorem says that any set X of (r-1)(d+1)+1 points in R^d can be partitioned into sets X_1,...,X_r such that the intersection of the convex hulls of the X_i's is nonempty.  (Smaller sets X typically do not have this property.)  Tverberg's original proof (1965) was fairly complicated.  I will discuss two simpler proofs, due to Sarkaria (2000) and Bárány (2023).

November 7: Shouda Wang
Title ― Characterization of f-vectors of simple polytopes
Abstract ― For a convex polytope, the vector whose k-th coordinate is equal to the number of its k-dimensional faces is the f-vector of this polytope. The g-theorem states that f-vectors are characterized by the Dehn-Sommervill equations, unimodality, and M-sequenceness. I’ll explain where this conjecture comes from and show how to use “morse theory for polytopes” and “flips” to prove the necessity.

November 14: Max Xu
Title ― Clique numbers of Paley graphs and additive decomposition
Abstract ― I will explain the short and elegant paper of B. Hanson and G. Petridis (https://arxiv.org/abs/1905.09134). They prove that the clique number of the Paley graph is at most \sqrt{p/2}+1 and that any supposed additive decompositions of the set of quadratic residues can only come from co-Sidon sets.

November 21: Daniel Zhu
Title ― Hypertrees
Abstract ― Everyone knows that a tree is a graph that is connected and acyclic. However, the appropriate extension of this notion to hypergraphs is much less clear. In this talk, I will discuss a definition of hypertree and a result of Kalai (1983) enumerating the number of hypertrees on n labeled vertices. Perhaps surprisingly, we will find that the correct language to express these notions is that of algebraic topology.

December 7: Hung-Hsun Hans Yu
Title ― An application of topological invariants in graph theory
Abstract ― In this talk, I will talk about a recent result of Mike Krebs and Maya Sankar that shows the following interesting statement: an abelian group G admits some Cayley graph with chromatic number 3 if and only if its exponent does not divide 4. 

The key ingredient is a lemma that improves Lovász's classical result on inequalities between chromatic number and (topological) connectivity.

February 8: Varun Sivashankar
Title ― Essentially tight bounds for rainbow cycles in proper edge-colourings
Abstract ― In a proper edge coloring of a graph, a ‘rainbow’ cycle is a cycle where every edge has a different color. In this talk, we will discuss a recent paper that shows that for a graph with sufficiently many edges (n log n log log n), we can find a rainbow cycle in any proper edge coloring of the graph. The key idea involves passing the problem to a sublinear expander graph along with some probabilistic arguments. We will highlight the key ideas in the proof and the details of significant intermediate lemmas.

February 15: Daniel Carter
Title ― You could have invented flag algebras
Abstract ― Flag algebras are a powerful tool in extremal graph theory introduced by Alexander Razborov in 2007. They allow for automatic discovery of nontrivial bounds on subgraph densities in graphs. We describe some of the main ideas behind flag algebras: types and flags, the downward operator, semidefinite programming, and graph limits -- and how they are simpler than they first appear.

February 22: Daniel Zhu
Title ― An introduction to asymptotic spectra
Abstract ― What is the computational complexity of matrix multiplication? What is the Shannon capacity of the 7-cycle? What is the size of the largest set in F_p^n containing no line? It turns out that these questions all are the same "type" of question, and can be unified in a theory of amortization developed by Strassen in the late 1980s. We introduce the basic concepts of this theory, following the recent survey of Wigderson and Zuiddam. Surprisingly, the central construction is quite reminiscent of the definition of an affine scheme.

February 29: Andrew Lin
Title ― The power of many colours
Abstract ― In this talk we consider generalizations of two classical problems: one problem, derived from a problem of Erdos and Renyi, where given any r-edge coloring of K_n, we ask to find the maximum number of vertices guaranteed to be adjacent to edges of the same color, and another problem by Gerencser and Gyarfas, where given any r-edge coloring of K_n, we ask for the largest monochromatic connected component we are guaranteed to find. In the power of many colors generalization, we look for objects using up to s colors rather than monochromatic objects. We will present bounds for these two problems from a recent work by Alon, Bucic, Christoph, and Krivelevich.

March 7: Dmitry Krachun
Title ― Almost all orbits of the Collatz map attain almost bounded values
Abstract ― The Collatz map is defined on the set of positive integers as follows: for odd x, Col(x) = 3x + 1 and for even x, Col(x) = x/2. The notorious Collatz conjecture states that the orbit N, Col(N), Col(Col(N)), and so on, of any positive integer N eventually reaches 1. Let Col_min(N) denote the smallest number in the orbit of N. It has long been understood that one can control the iterations of the Collatz map up to the k-th iteration with k of the order roughly log(N) by considering N modulo a suitable power of two. These local considerations eventually lead to the result of Korec: For any θ > log_4(3), for almost all N, one has Col_min(N) < N^θ.
Recently, Terrence Tao combined these local considerations with a certain invariant measure type argument to significantly improve the result of Korec. Specifically, he proved that for any function f(N) tending to infinity, almost all N satisfy Col_min(N) < f(N). Here almost all is understood in the sense of logarithmic density.
In this talk, I will explain the main ideas in the proof, closely following Tao's paper, which shares the title with this talk. If time permits, I will also discuss potential directions for future research.

March 21: Hsun-Hung Hans Yu
Title ― Ordinary lines
Abstract ― The Sylvester--Gallai theorem asserts that for any finitely many points not on a single line, there exists a line passing through exactly two of the points. This kind of line is called ordinary. In this talk, I will talk about a result of Green and Tao that determines the minimum number of ordinary lines for n points when n is large enough. The main intermediate result in the proof is a strong structural theorem, which roughly says that points with linearly many ordinary lines should mostly lie on a cubic curve.

March 28: Cosmas Kravaris
Title ― Bounded distortion Ramsey families
Abstract ― Given C>1, a set X, and two metrics d and d' on X, we say that (X,d') is a C-distorted copy of (X,d) whenever the product of the Lipschitz constant of Id:(X,d) -> (X,d') and the Lipschitz constant of Id:(X,d') -> (X,d) is at most C. Following Matoušek(1992), a sequence of metric spaces ((X_n,d_n))_n is a bounded distortion Ramsey family if for any k, any small ε>0 and any large C>1 we have for sufficiently large n that any C-distorted copy of (X_n,d_n) contains a (1+ε)-distorted copy of (X_k,d_k). In this talk, we provide 3 examples of bounded distortion Ramsey families. Firstly, X_n = {1,2,..,n} with the trivial metric, i.e. any two distinct points have distance 1. Secondly, X_n = {1,2,..,n} with the metric inherited from the real line: d(i,j)=|i-j|. Thirdly, X_n = {0,1}^n the n-dim Hamming cube with the Hamming metric. The last example is due to Bourgain-Milman-Wolfson(1986), using a non-linear analogue of Rademacher type.

4-week Mini Series: Special Year

April 4: Cooper Kofron
Title ― It's all about the fans
Abstract ― We outline the connections between combinatorics and algebraic geometry, coming in the theory of toric varieties. We introduce fans, a combinatorial object, and show how to obtain convex polytopes and toric varieties from fans. We also explain how every matroid has an associated fan structure, it’s Bergman fan. Combinatorial properties of fans reflect geometric properties of these objects, and we focus on concrete examples of this behavior. This lays the groundwork for a bridge between the fields of algebraic geometry, convex geometry, matroid theory and combinatorics. 

April 11: Sergio Cristancho
Title ― Lorentzian polynomials, convexity, and matroids
Abstract ― The objective of this talk is to give a broad introduction to the novel theory of Lorentzian polynomials due to Brändén and Huh. Lorentzian polynomials link objects exhibiting discrete convexity (like Newton polytopes, discrete matroids) to those with continuous convexity (like quadratic forms and convex bodies) in a very deep and structural manner. We will enumerate (if time allows with some proofs) some of the main properties and connections to algebraic geometry, convex geometry and combinatorics.

April 18: Noah Kravitz
Title ― Schubert calculus
Abstract ― Schubert calculus provides a systematic way to answer questions such as, "How many lines intersect a generic quadruple of lines in P^3?"  Along the way, we will also encounter the Grassmannian, symmetric functions, and Young tableaux.

April 25: Vanshika Jain
Title ― Knutson-Tao puzzles
Abstract ― During the last lecture, we saw how the theory of Schubert calculus provides powerful tools for solving problems related to the enumeration of geometric configurations. In this talk, we will explore Knutson-Tao puzzles, a combinatorial approach that computes Schubert calculus. 

3-week mini series: Algebraic Methods in Combinatorics

September 13th: Noah Kravitz

Title: Nearly sharp bounds for the Ramsey numbers r(4,t)

Abstract: The Ramsey number r(s,t) is defined to be the smallest natural number n such that every graph on n vertices contains either a clique of size s or an independent set of size t.  Last semester Xiaoyu talked about a breakthrough relating to the growth rate of the "diagonal" Ramsey numbers r(t,t).  In the extreme opposite regime, one can study the growth rate of r(s,t) for s fixed and t going to infinity.  In this direction, I will focus on recent work of Mattheus and Verstraete that determines r(4,t) nearly exactly. 

September 20th: Cosmas Kravaris

Title: Random algebraic construction of extremal graphs

Abstract: Given a finite graph H and a natural number n, ex(n,H) is the largest possible number of edges of an n-vertex graph G with no copy of H (i.e. no injective graph homomorphism from H to G). We are interested in the asymptotics of ex(n,H) as n goes to infinity. Turán's theorem determines ex(n,H) when H is a complete graph, and the Erdős-Stone-Simonovits theorem determines ex(n,H) when H has chromatic number at least 3.  When H is bipartite, little is known. In this talk we will give a random algebraic construction of Bukh for constructing n-vertex graphs with many edges and no copy of the complete bipartite graph K_{s,t} for every s and some large value t. The idea is to sample uniformly a polynomial and consider a "polarity-type" graph associated to it. If time permits, related bounds and constructions will be discussed. The talk is based on the paper of Bukh (2015) and the book of Zhao (2023).

September 27th: Hung-Hsun Hans Yu

Title: Toward the Tight Density in the Finite Field Kakeya Problem

Abstract: The finite field Kakeya problem was first raised as the finite field model for the famous Kakeya conjecture, which asks to lower bound the dimension of a set in the Euclidean space containing a segment of length one in each direction. The finite field model was first solved, by Dvir, where he introduced the polynomial method to show that any Kakeya set must have constant density. This result was refined by Dvir, Kopparty, Saraf and Sudan later, where they introduced the method of multiplicities. The work left a multiplicative gap of two between the upper bound and the lower bound of the density, which was recently closed up by Boris Bukh and Ting-Wei Chao. In the talk, I will give a proof of Dvir, Kopparty, Saraf and Sudan's result, and I will also talk about where Bukh and Chao managed to get an improvement..

2-week Mini Series: Local Algorithms and Factors of IID

October 4th: Jason Prodromidis

Title: Local Algorithms: Applications and Obstructions

Abstract: In this talk, we will be introducing the notion of local algorithms. As we will see, in the case of the independence number of a typical d-regular graph, local algorithms work well, but not as well as we would like them to. The analysis of the problem will show that certain obstructions can arise, when trying to make a local algorithm work to find a set with specific properties. If time permits, we will also mention a group theoretic application of those types of algorithms, as well as results that describe the regimes that local algorithms can be used in a more general setting.

October 11th: Eyob Tsegaye

Title: Factors of IID for Graph Colorings and Graph Cuts

Abstract: We will be continuing the discussion last week of local algorithms, but taking it in a different (but very related) direction to discuss factors of iid. We will use the theory here to show that there exist 5-colorings of infinite random planar graphs which are invariant under isometries of the plane. We will then give a more concrete combinatorial application and show how factors of iid can be used to give upper and lower bounds on the limiting minimum and maximum relative size of a bisection in families of d-regular graphs

3-week Mini Series: Sumset Problems

October 25th: Daniel Zhu

Title: Fourier analysis and the Erdős distinct subset sets problem

Abstract: We discuss the application of Fourier-analytic techniques to the Erdős distinct subset sets problem, including a new exposition of the lower bound of Dubroff, Fox, and Xu (2020). Time permitting, we will also discuss a recent result of Cambie, Gao, Kim, and Liu extending the problem to a modular setting.

November 1st: Daniel Carter

Title: On the Diameter of Finite Sidon Sets

Abstract: A Sidon set, also known as a Golomb ruler or B_2 set, is a set of integers where every difference of pairs of distinct elements is unique. An old result of Erdős-Turán states that any k-element Sidon set must have diameter at least k^2 - (b + o(1)) k^(3/2) for some 0 ≤ b ≤ 2; Erdős offered $1000 for a proof or disproof that b = 0. We discuss recent work improving the upper bound on b by Balogh, Füredi, and Roy (2021); O'Bryant (2022); and myself, Hunter, and O'Bryant (2023).

November 8th: Kunal Chawla

Title: The Bourgain-Gamburd expansion machine

Abstract: I will describe an interesting, hands-on proof of expansion for Cayley graphs of SL(n, F_p) by Bourgain and Gamburd (2008). Instead of relying on Property T or deep number theory, the proof relies on analytic and combinatorial methods, using estimates on product sets to show equidistribution of the random walk.

November 15th: Kevin Ren

Title: Pinned Distances in the Plane

Abstract: Given a set of n points, it is known (Guth-Katz '15) that they span >= c (n/log n) distinct distances, which nearly matches the sqrt(n) x sqrt(n) grid example which (exercise!) gives O(n/sqrt(log n)). However, the pinned version, which asks for a point in the set that spans a lot of distances with the other points, remains more elusive. Following Solymosi-Tóth ('01), we show that there exists a point that spans >= c n^(6/7) distinct distances with the other points. This is accomplished through a clever combination of tools in discrete incidence geometry.

November 29th: Seoyeon Yang

Title: Uniqueness of giant component on expander graphs

Abstract: Emergence of a giant component in a random graph is an interesting phenomenon in percolation theory. There's a conjecture on general graphs that under a certain condition, there's an emergence of the unique giant component. We discuss this on the expander graphs using double counting. If time permits, we discuss the critical probability for finite regular expanding graphs of high girth. Based on the work of Alon, Benjamini, and Stacey (2005).

December 6th: Vanshika Jain

Title: Exploring the Representations of the General Linear Group GL_m(C) Through Young Tableaux

Abstract: To study the representations of the general linear group GL_m(C), we first study a linear algebraic construction, which extends symmetric and exterior products. Central to our study is the use of Young tableaux, which provide a parametric framework for these representations. Then, we will look at how these representations can also be constructed from representations of the symmetric group, and show their relation to certain quadratic equations. 

January 30

Speaker: Florian Richter

Title: Finding infinite arithmetic structures in sets of positive density

Abstract: In the 1970's Erdos asked several questions about what kind of infinite arithmetic structures can be found in every set of natural numbers with positive density. In recent joint work with Bryna Kra, Joel Moreira, and Donald Robertson we use ergodic methods to resolve some of these long-standing problems. This talk will provide an overview of our results and describe some of the dynamical structures that are used to prove them.

3-week mini series: Entropy methods

February 6

Speaker: Noah Kravitz

Title: Entropy and counting (Entropy week 1/3)

Abstract: The goal of this talk is to demonstrate how entropy methods can be useful in extremal graph theory.  After giving a brief review of the basic properties of entropy, I will outline several short entropic proofs of “classic” results (e.g., Bregman's Theorem) and motivate the definition of graph entropy.  This talk is based on a survey paper of Radhakrishnan.

February 13

Speaker: Hans Yu

Title: Application of the entropy method: Sidorenko's conjecture (Entropy week 2/3)

Abstract: In the second week of the series, we will apply the entropy method to prove special cases of a graph-theoretic conjecture of Sidorenko. The conjecture, in some sense, claims a lower bound on the number of copies of a given bipartite graph in another graph in terms of its number of edges.  We will see how basic properties covered in the previous week can be combined to lead to something nontrivial.

February 20

Speaker: Eyob Tsegaye

Title: Application of the entropy method: the Sunflower Conjecture (Entropy week 3/3)

Abstract: In the third and final week of the series on entropy methods, we look at the sunflower conjecture! A sunflower is a (finite) family of subsets of some larger set that are disjoint apart from their mutual intersection. We show how entropy methods can be used to achieve the best currently known bound on how large a family of sets can be before it contains a sunflower. This talk follows a blog post by Terry Tao.

2-week mini series: Slice-rank and applications

February 27

Speaker: Aleksa Milojevic

Title: Sunflowers via slice-rank (Slice-rank week 1/2)

Abstract: We will start by reviewing the solution to the capset problem by Croot, Lev, Pach and Ellenberg, Gijswijt, and then present a version of the polynomial method, called the slice rank method, introduced by Tao to symmetrize their proof. Then, we will discuss how slice rank can be used in other combinatorial problems, for example to bound the size of the biggest family of subsets of {1, 2, ..., n} without k-sunflowers. Additionally, we will cover applications of the slice rank method beyond sunflowers if time constraints allow.

March 6

Speaker: Cosmas Kravaris

Title: Slice rank of tensor powers: upper and lower bounds (Slice-rank week 2/2)

Abstract: The slice rank of a function T from A x A x A to the reals is bounded by the number of slice sets (subsets of  A x A x A where one coordinate is fixed) which cover the support of T. Fixing a linear order on each A and taking an antichain of maximal elements of the support of T, the minimum number of slice sets which cover this antichain is a lower bound for the slice rank of T. Using this, we show that the slice rank solution to the capset problem does not (naively) generalize to k-APs when k>=8. Moving on, we can form the tensor power T^n from A^n x A^n x A^n to the reals and look at the exponential growth rate of the slice rank of T^n as n grows. The bounds for the sunflower and capset tensors we saw last time are upper bounds for this rate. Using the asymptotic equipartition property, this rate is given via an entropy condition, and (if time permits) the exact rates are computed for the sunflower and capset tensors. The talk follows the 2016 blog post of Sawin and Tao.

March 13: SPRING BREAK

March 20

Speaker: Noah Kravitz

Title: New bounds for sets avoiding 3-term arithmetic progressions

Abstract: A set of integers is called 3AP-free if it does not contain a non-trivial 3-term arithmetic progression {x, x+y, x+2y}.  What is the largest possible size of a 3AP-free subset of the first N integers?  Roth showed that the answer is <<N/loglogN (in particular, o(N)).  A recent breakthrough of Kelley and Meka improves this bound to <<N exp(-\Omega(logN)^{1/11}); this is the first upper bound of the same “shape” as the lower bound coming from Behrend’s construction of 3AP-free sets.  I will give a gentle introduction to the ideas of Kelley and Meka’s proof in the finite field setting.

March 27

Speaker: Eyob Tsegaye

Title: Adjacent transposition shuffle via censoring inequalities

Abstract: The adjacent transposition shuffle is a method of card shuffling where at each step a pair of adjacent cards in the deck is swapped. In 2016, Lacoin showed that this shuffle has a mixing time of (1/pi^2+o(1))N^3logN. The proof is motivated by a simple yet powerful idea by Peres and Winkler that fewer shuffles can only hurt you (if we censor certain updates, it will take longer to mix). This intuition is not true in general and requires some subtle requirements about the "monotonicity" of the underlying system. In this talk, we will discuss what monotonicity means in this context, formalize this intuition, and see how it is used in the context of the adjacent transposition shuffle.

April 3

Speaker: Xiaoyu He

Title: An exponential improvement for diagonal Ramsey

Abstract: In the biggest breakthrough in Ramsey theory since Erdos' first-moment paper, Campos, Griffiths, Morris, and Sahasrabudhe have proved that the diagonal Ramsey number R(k) satisfies R(k) <= (4-epsilon)^k. The classical Erdos-Szekeres algorithmic proof of 4^k searches for a monochromatic clique by iteratively restricting to monochromatic neighborhoods. The new algorithm cleverly pursues two Erdos-Szekeres search paths simultaneously, one diagonal and one extremely off-diagonal. In this talk we give an overview of the Campos-Griffiths-Morris-Sahasrabudhe algorithm, which is easy to state but hard to analyze.

I also discuss my personal intuition for why (at first blush) this proof seems surprisingly specific to this particular Ramsey number, and not to generalize to off-diagonal, directed, or bipartite Ramsey numbers. It seems there are actually two exponential gaps in the bounds sqrt(2)^k <= R(k) <= 4^k, a local-to-global gap from sqrt(2)^k to 2^k and a color-inefficiency gap from 2^k to 4^k, and this new proof improves entirely on the latter half of the picture.

April 10

Speaker: Tung Nguyen

Title: Extensions of Rödl’s theorem

Abstract: An early application of the regularity lemma, Rödl’s theorem from 1986 says that every graph with no induced copy of a given graph contains a linear-sized vertex subset inducing a very sparse or very dense subgraph. It has found many applications, in particular in the investigation of quasirandomness and the Erdős–Hajnal conjecture. This talk first surveys several extensions of this result, focusing on both quantitative and qualitative aspects, and then discusses in-depth a proof of one such extension due to Chudnovsky, Scott, Seymour, and Spirkl.

April 17

Speaker: Cosmin Pohoata

Title: Convexity, color avoidance, and perfect k-hash codes

Abstract: In this talk I will discuss a few favorite open problems that are related in some way or another with Ramsey numbers, the Erdős-Szekeres problem, and the polynomial method (and also the words from the title), together with casual speculations.

April 24

Speaker: Jason Prodromidis

Title: The Study of the Ising Model via Percolation

Abstract: The Ising model is a very important model in statistical physics, introduced more than a century ago. Since then, the model itself and its variants have been objects of study in Probability Theory. In this talk, we will introduce the Ising model in Z^d and discuss some of its properties, which are mostly related to phase transition properties. An important tool in our study will be the connection of the Ising Model to a percolation model, known as the Random Cluster Model.

May 1

Speaker: Matija Bucic

Title: Robust sublinear expanders

Abstract: Expander graphs have been perhaps one of the most widely useful classes of graphs ever considered. In this talk we will focus on a fairly weak notion of expanders called sublinear expanders, first considered in combinatorics by Komlos and Szemeredi around 25 years ago. They have found many remarkable applications ever since incliding resolutions of multiple classical questions in the field.

In this talk we will focus on a more recent idea that one may impose a certain robustness condition on sublinear expanders which still allows for an (almost) decomposition lemma to hold while on the other hand allowing us to prove a number of properties usually associated with much stronger expander graphs.

After introducing the notions and giving a high level overview of how and when these type of ideas may be useful we will discuss a number of properties of such robust sublinear expanders and give an illustration of how they can be used.

September 14

Speaker: Xiaoyu He

Title: Slow and Lonely Runners

Abstract: One formulation of the Lonely Runner Conjecture states that if 0 < v_1 < v_2 <...< v_n are n positive integers, then there is a time t such that every (v_i t) is at least 1/(n+1) away from an integer. This talk is about a recent line of attack on this problem by Bohman and Peng, who showed that if all the speeds are at most (2-\epsilon) n, then the conjecture is true. They reduce this toy problem to a certain graph/hypergraph problem about matchings and vertex covers, and finish it off with number-theoretic techniques related to the Jacobsthal function.

September 21

Speaker: Noah Kravitz

Title: Hamidoune’s isoperimetric method

Abstract: In additive combinatorics, it is often desirable not only to establish general inequalities but also to solve the associated “inverse problems” of determining when equality (or near-equality) occurs.  For example, the Cauchy-Davenport Theorem asserts that if A,B are subsets of the cyclic group mod p, then |A+B| is at least min{|A|+|B|-1, p}, and Vosper’s Theorem shows (essentially) that equality holds if and only if A, B are arithmetic progressions with the same common difference.  The topic of this talk is Hamidoune’s elementary but versatile “isoperimetric method” for attacking such inverse problems.  In particular, I will describe Hamidoune’s alternative proof of (a generalization of) Vosper’s Theorem and Tao’s use of similar machinery to establish a non-abelian Freiman-Kneser-type theorem.

September 28

Speaker: Fan Wei

Title: On the limits of bounded degree graphs

Abstract: In this short talk, I will give a gentle introduction to the graph limit theory of bounded degree graphs, and show how some results, such as property testing, which is well-studied in the setting of dense graphs, also have its somewhat more restricted forms when discussing bounded degree graphs.

October 5

Speaker: Tara Abrishami

Title: Infinite families of bipartite Ramanujan graphs

Abstract: In this talk, I will give an overview of the proof that there exist infinite families of bipartite Ramanujan graphs by Marcus, Spielman, and Srivastava (here). The proof relies on a method called interlacing polynomials. If a family of polynomials is interlacing, then there exists a polynomial in the family whose largest root is at most the largest root of the sum. I will also mention some other results obtained by the same method, as time permits.  

October 12

Speaker: Cosmas Kravaris

Title: Concentration of measure for the Hamming cube and the symmetric group

Abstract: We begin with the definition of a Levy family of metric measure spaces, an axiomatization of the phenomenon of concentration of measure. We list some examples and state the main two theorems of this talk: the Hamming cubes form a Levy family and the symmetric groups form a Levy family. We then recall some basic definitions about martingales and state the key ingredient in the proof: Azuma’s martingale inequality. As time permits, we outline a proof of Azuma’s inequality and the main two theorems. This talk is based on the 1986 book of Milman and Schechtman “Asymptotic Theory of Finite Dimensional Normed Spaces”.

October 19: OCTOBER BREAK

October 26

Speaker: Hans Yu

Title: The method of hypergraph containers

Abstract: Given an Erdős–Rény random graph G(n,p), we may ask how big p should be in order for it to exhibit some Ramsey-type or Turán-type behavior. Problems of this flavor were studied using tools designed speicifcally for sparse rsets, such as the transference machinery or the sparse regularity lemma. However, in this talk, I will talk about yet another approach, discovered by Saxton–Thomason and Balogh–Morris–Samotij independently, that unifies lots of results using the method of hypergraph containers. I will mention two applications of the hypergraph container theorem, and sketch a proof of the theorem if there is time.

November 2

Speaker: Ryan Alweiss

Title: Monochromatic sums and products of polynomials

Abstract: A celebrated result of Moreira from 2016 is that the pattern {x,x+y,xy} is partition regular; i.e. any coloring of N with finitely many colors has x,x+y,xy all the same color.  Before this, it was not even known if x+y,xy is partition regular; in the 70s Hindman conjectured that {x,y,x+y,xy} is partition regular and this remains unsolved.  In this talk, we will generalize Moreira's result, and prove that {x,x+y,xy} is partition regular in a more general setting, over polynomial rings such as the rings of polynomials of t with 0 constant term.  In addition to being more general, the proof is considerably shorter and simpler.

November 9

Speaker: Micha Christoph

Title: Breaking the degeneracy barrier for coloring graphs with no K_t-minor

Abstract: In 1943, Hadwiger conjectured that every Graph with no K_t minor is t-1 colorable. Solving this conjecture is considered to be one of the most important open problems in graph theory. In the 80s, Kostochka and independently Thomason showed that every graph with no K_t minor is O(t(log t)^{1/2})-degenerate and therefore, also O(t(log t)^{1/2}) colorable. Much more recently (2020), Norin, Postle and Song made the first significant improvement on this bound, using a method called density increment. They showed that every graph with no K_t minor is O(t(log t)^{a}) colorable for any a>¼. In this talk we will discuss their approach and if time permits also have a look at the differences to the even newer paper by Delcourt and Postle (2021) improving the above bound to O(t * log log t).

November 16

Speaker: Tung Nguyen

Title: Highly connected subgraphs

Abstract: This talk aims to survey some results and conjectures regarding sufficient conditions for a graph to contain a highly connected subgraph (possibly with some additional properties). These sufficient conditions involve average degree, minimum degree, and chromatic number.

November 23; THANKSGIVING

November 30

Speaker: Alan Chang

Title: Spherical designs

Abstract: A spherical design of strength t is a finite subset X of the sphere S^(n-1) such that the average value of any polynomial f of degree t or less on X equals the average value of f on the whole sphere. In this talk, we show how Delsarte, Goethals, and Seidel used spherical harmonics to prove a lower bound on the size of a spherical design. (In a 2013 paper, Bondarenko, Radchenko, and Viazovska showed that this lower bound is tight, up to a constant factor.)

December 7

Speaker: Jason Prodromidis

Title: It all starts from Erdos-Littlewood-Offord

Abstract: In 1943, in a paper studying the roots of random polynomials, Littlewood and Offord proved a very nice Lemma for sums with random signs. Two years later, Erdos optimized that result, and his result is today referred to as the Erdos-Littlewood-Offord Lemma. GIven this Lemma itself and its proof, it is possible to ask many questions, towards many different directions. The purpose of this talk is to ask and answer as many questions as possible, that naturally arise from the Erdos-Littlewood-Offord Lemma.

December 14

Speaker: Cosmas Kravaris

Title: Ramsey theory for trees

Abstract: Consider the binary tree with N levels. Weight each vertex with the number 2^-l where l is the level of the vertex (i.e. 0, 1, ... N-1). In 2003, Furstenberg and Weiss proved the following Szemeredi-type theorem: for any δ>0 and k, there exists N such that every subset of the binary tree with N levels with density > δΝ contains an "arithmetic replica" of the binary tree with k levels. Their proof relies on recurrence properties of Markov chains on trees. In this talk, we provide a proof of this theorem by Pach, Solymosi and Tardos (2012) using elementary methods (+ assuming Szemeredi's theorem). Pach, Solymosi and Tardos (2012) also give an asymptotically tight construction of colorings of the binary rooted tree with no monochromatic "replicas". Their construction is probabilistic and relies on Azuma's inequality.