Workshop Details

A random walk on the real line, where the steps are chosen from a continuous, symmetric distribution,generates a random permutation (that maps time to relative position). The resulting probability distribution on the symmetric group has remarkable properties. Some were noted by probabilists 75 years ago; others we bring to light with help from the new technology of permutons (limit structures for permutations).

The new stuff is joint work with Peter Francis, a PhD student at Stony Brook.

Cayley graphs play an important role in various mathematical areas and in recent years there has been an interest in studying high-dimensional versions of these graphs. In this talk we will focus on one such extension called Balanced Cayley Complexes (BCC). In particular, we'll discuss a Fourier approach to the homology of BCC's over prime fields with applications to the construction of hypertrees and MDS codes.

Joint work with Gilles Zemor.

We show how conflict-free hypergraph matching results can be applied to obtain asymptotically optimal bounds in generalized Ramsey theory. These applications require large matchings that avoid prescribed configurations and satisfy additional distributional conditions. The idea of finding large hypergraph matchings while controlling additional weighted statistics already appeared in Jeff Kahn’s work from the 1990s.

This is joint work with Felix Joos and Zak Smith.

Having so many combinatorialists as a captive audience, I will give a list of simple to state combinatorial problems, whose solutions have significant consequences for computational complexity theory.

We study the number of Hamilton cycles in Dirac hypergraphs.

Joint work with Tom Kelly and Michael Simkin.

A pair (𝒜, ℬ) of families of subsets of [n] is called cancellative, if whenever A, A′∈𝒜, B∈ℬ satisfy A∪B=A′∪B, then A=A′; and whenever A∈𝒜, B, B′∈ℬ satisfy A∪B=A∪B′, then B=B′. In this talk I will discuss an entropy proof showing that every cancellative pair (𝒜, ℬ) satisfies |𝒜||ℬ|≤2.25ⁿ, matching Tolhuizen's (2.25−o(1))ⁿ lower bound construction.

Joint work with Yijia Fang.

Let f(n) be the smallest integer so that every bounded set in R^d can be covered with f(n) sets of smaller diameter. Borsuk asked in 1933 if f(n)=n+1 for every n and in 1993 Jeff and I showed that this is false in high dimensions. I will present a variety of open problems around Borsuk's problem.

An independent transversal (IT) of a graph G with a given vertex partition P is an independent set in G consisting of one vertex in each of the parts of P. This is a very general notion, and many problems in mathematics can be expressed by asking whether a particular graph G with a particular choice of P has an IT. Various criteria involving properties of G and P are known that will guarantee the existence of an IT in G. More broadly, one may wish to consider the space of all IT's for a given G and P, and investigate how they are related. For example, under what conditions is this space connected, in the sense that one can transition from any IT to any other via a sequence of single-vertex modifications? It has been shown (Buys-Kang-Ozeki, Wdowinski) that with conditions only very slightly stronger than those ensuring the existence of a single IT, this connectivity property also holds. Here we explore further questions of this type, for example what conditions guarantee that such reconfiguration paths in the space of all IT's are short, and whether they can be found efficiently.

Chavátal’s conjecture, from 1974, asserts that for any finite downward closed family of sets, the largest possible size of an intersecting sub-family is attained by some star (dictator). Despite dozens of partial results in special cases, until recently the resolution of the conjecture seemed out of reach. One of the most promising approaches was a beautiful and tantalizing conjecture of Jeff; A formula, that if true would imply the conjecture. Several weeks ago there was an AI-assisted breakthrough by Chang, Liu and Liu, who proved Chvátal’s conjecture, and a special case of Jeff’s formula. An additional effort by Keevash managed to complete the proof of Jeff’s formula. Meanwhile, a separate team, consisting of David Ellis, Yuval Filmus and myself had been trying, using ChatGPT and Claude, to crack the conjecture using a spectral approach. We hadn’t been able to do so until we fed the bot the new proof of CLL. After a couple of additional rounds the bot produced a gem - an otherworldly proof of the conjecture. I’ll present the proof in its entirety, and two surprising spectral conjectures concerning downsets, that we are still unable to crack.

Many well-studied random graph models like random Cayley graphs share the property that each edge e appears mutually independently of all edges except those in a bounded degree graph G_e. It turns out that this property is sufficient to prove many interesting results about such random graphs. This perspective led to the solution of open problems in information theory, additive combinatorics, Ramsey theory, and random graph models.

Joint work with David Conlon, Huy Tuan Pham, and Liana Yepremyan.

Suppose that H is a uniform hypergraph with vertex set V. The hypergraph container lemmas supply a decomposition of the family of subsets of V that are independent in H into a 'small' number of 'simple' pieces. We will present a similar-spirited decomposition lemma that employs a weaker notion of 'simple' but applies to arbitrary families of subsets of V.

This is joint work with Gady Kozma, Asaf Shapira, and Adam Zsolt Wagner.

The Erdős-Sós Conjecture was recently proved by GPT-6 Astra, using an ingenious and surprising argument. We present a simplified version of this argument in (we hope) a more natural form. We also prove a related conjecture of Addario-Berry, Havet, Linhares Sales, Reed and Thomassé, and give a substantially simplified proof of an analogous result for eulerian digraphs, again proved by GPT-6 Astra, and announced by Mubayi and Verstraete. In addition, we determine the extremal (di)graphs for all three problems.

Joint work with Oliver Riordan.

Consider the following problem of learning an unknown linear order on n items. In each round, the learner guesses a complete ordering of the items and receives either confirmation that the guess is correct or a counterexample: a pair of items in the wrong order. The goal is to minimize the number of queries, when up to k of the returned answers may be incorrect. We determine the optimal query complexity of the problem up to a constant factor for all n and k. The proof is geometric, inspired by the work of Jeff Kahn and his collaborators on balancing poset extensions.

Joint work with Shay Moran and Shlomo Moran.

Let X = [n] be a finite set of points. An (x,y)-path is a sequence of distinct points that starts with x and ends with y. A path system \Pi on X is a collection of paths with exactly one (x,y)-path for every two distinct points x, y in X. Think of this path P_{x,y} as the chosen path between these two points. We always assume that P_{y,x} coincides with P_{x,y} read in reverse. Every path system gives rise to a graph (X,E) where xy is an edge whenever the path P_{x,y} = x,y, so many of our results are graph-theoretic. We say that the path system \Pi is consistent if the following holds: For every point z on the path P_{x,y}, this path is the concatenation of the paths P_{x,z} and P_{z,y}. It is easy to construct metric consistent path systems: Assign a positive distance w(u,v) with every pair of points u,v in X and let P_{x,y} be a w-shortest x,y path. Q; Is every consistent path system necessarily metric? The answer is negative and we give various quantitative manifestations of this statement. In particular we ask: is every consistent path system approximately metric? The answer is that the largest metric distortion of a consistent path system is \Theta(\sqrt n).

All the papers in this domain are joint with my student Daniel Cizma, some are also with Maria Chudnovsky, if time allows I will also mention a recent result with my students Itai Goldflam

Joint with Michael Anastos and Bob Krueger. We show that if each vertex of the n-cube independently chooses k∼ log₂n random neighbors then w.h.p. the resulting random subgraph has a perfect matching. Our result is best possible up to a small additive constant.

A classical problem in real algebraic geometry is to understand when a polynomial is nonnegative and whether its nonnegativity admits a universal certificate. Closely related questions arise in combinatorics. Graph homomorphism densities form a commutative algebra with many of the formal features of a polynomial ring, and inequalities between graph densities can be viewed as positivity questions in this algebra. Lovász, Szegedy, and Razborov raised related questions about whether all valid graph-density inequalities admit finite algebraic certificates such as sum-of-squares. The work of Hatami and Norine uncovered fundamental obstructions in the graphon setting. I will discuss related questions for more general kernels.

I will then turn to a noncommutative polynomial world. Words in matrices and their transposes are the monomials of a free noncommutative (*)-algebra, and one can ask which such noncommutative polynomials or monomials are universally positive under matrix substitutions. These questions have connections to matrix theory and to problems originating in quantum statistical mechanics. In this setting, the structure of positivity and the nature of its certificates look strikingly different from their commutative graph-density counterparts. Surprisingly, graph homomorphisms reappear in the analysis.

The talk will compare these two worlds through a common question: when can universal positivity be recognized, certified, and explained by underlying combinatorial structure?