Extremal Combinatorics Abstracts

Coarse graph theory is a developing area that focuses on the large-scale geometric structure of graphs, particularly through the lens of quasi-isometry. A central goal is to find coarse analogues of classical graph-theoretic results. We discuss some current progress in this direction.

Joint work with Tung Nguyen and Paul Seymour.

How irregular can the degree distribution of a spanning subgraph of a d-regular n-vertex graph be? As there are d + 1 possible vertex degrees in such a subgraph, the best we could hope for is to have around n/(d + 1) vertices of each degree in {0,1,…,d}. I will discuss a result showing that if d = o(n), then there is always a subgraph in which there are (1 + o(1))n/(d + 1) vertices of degree i, for each i ∈ {0,1,…,d}. This proves a conjecture of Alon and Wei and strengthens a previous result of Fox, Luo, and Pham.

This is joint work with Alexey Pokrovskiy and Benny Sudakov.

In recent years, tools from combinatorics, especially the probabilistic method, have found unexpected applications in the field of dynamical systems theory. In this talk, I will discuss this research trend by focusing on one recent example, namely the construction of flows with minimal subdynamics for arbitrary countable groups.

Based on joint work with Joshua Frisch.

A central open question in extremal design theory is Nash-Williams’ Conjecture from 1970, namely that every triangle-divisible graph on n vertices (for n large enough) with minimum degree at least 0.75n has a triangle decomposition. In this talk, we discuss the history of the problem and our recent resolution of this conjecture, as well as other applications in design theory.

This is joint work with Luke Postle.

In 1970, Nash-Williams conjectured that every triangle-divisible graph on n vertices with minimum degree at least 3n/4 has a triangle decomposition, provided n is large enough. In this talk, we overview our recent proof of this conjecture, highlighting the new techniques we developed to resolve the fractional version as well as the full conjecture.

Joint work with Michelle Delcourt.

We consider the problem of detecting and reconstructing trees planted in a sparse random graph. More specifically, given a k-vertex tree T, we consider the union of a random graph G(n,p), where p = c/n, and a copy of T randomly planted into the vertex set of the random graph. We study how large k has to be so that the presence of the planted tree can be detected. We distinguish two cases: (1) the shape of the tree T is known; and (2) T is an unknown uniformly random tree.

When T is known, we show that if k = Ω(log n) and c < 1.12, then for most trees T, the planted model can be distinguished from G(n,c/n). This may be surprising since, for c ≥ 1, G(n,c/n) contains random trees of size n^2/3−o(1). On the other hand, when p ≥ C/n for a large constant C and k = o(√n), no test can detect the presence of the planted tree for most trees. Both bounds on k are optimal up to a constant factor. Even when the shape of the planted tree is unknown, k = ω(log² n) is sufficient for detection when c ≤ 1.14. We also consider the problem of reconstructing the planted unknown random tree and show that partial reconstruction is possible when k = ω(log² n).

Joint work with Nicolas Broutin, Nina Kamčev, Gábor Lugosi, and Bruce Reed.

Let G be the percolated infinite square lattice with parameter p. Maker and Breaker then play the following game by alternately claiming m and b edges of G, respectively. Breaker’s goal is to isolate the origin from infinity. Maker’s goal is to indefinitely avoid Breaker’s win, meaning that she wants to defend the origin in an infinite connected component after deleting Breaker’s edges.

It is known that on the unpercolated square lattice, meaning when p = 1, Maker wins the game. Using tools from bootstrap percolation, we prove that whenever p < 1, Breaker wins, showing that Maker’s win on the unpercolated board is rather fragile.

This is joint work with Vojtěch Dvořák and Victor Souza.

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 similarly 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 inertia bound is a classical tool from spectral graph theory for upper-bounding the independence number of graphs. However, until a few years ago, we did not have a single example where the inertia bound was provably not tight. Since then, several researchers have investigated its tightness. Most notably, a recent result of Kwan and Wigderson shows that in locally sparse graphs (i.e., C₄-free graphs or graphs of girth 5), the inertia bound is always linear in the number of vertices, while examples of such graphs are known—for example, from finite geometry—with much smaller independence number. Follow-up work of Tang, Zang, and Elphick showed even stronger separation results for complements of pseudorandom graphs, relying on known constructions of triangle-free pseudorandom graphs.

We investigate the tightness of the inertia bound for graph powers. The k-th power of a graph G in this setting is the graph G^(k) on the same set of vertices, with two vertices adjacent if their distance in G is at most k. This class of graphs appears in several contexts, such as the theory of distance-regular graphs and coding theory. An important property is that these graphs are never locally sparse, nor are they easily seen to be complements of pseudorandom graphs, and hence they require new ideas. Using random Cayley graphs and extending results of Alon, we show that for graph powers there can also be a large gap between the inertia bound and the actual independence number.

Joint work with Aida Abiad and Nils van de Berg (TU Eindhoven).

In this talk, I will discuss some recent progress on a relative of the classical Ramsey problem introduced by Erdős and Rogers: What is the largest K_s-free subset that can be found in every K_s+1-free graph on n vertices?

This is based on joint work with Rob Morris and Jacques Verstraete.