Georgia Institute of Technology College of Sciences

Let $d\geq 2$, and $n\geq 2d+2$. Frankl and Pach initiated the study of the maximum size of a $(d+1)$-uniform set system in $[n]$ with VC-dimension at most $d$. The best-known upper bound is essentially $\binom{n}{d}$, and the best-known lower bound is $\binom{n-1}{d} + \binom{n-4}{d-2}$. In this talk, I will discuss some recent improvements on the upper bound and some interesting connections between this problem and the celebrated Erdős--Ko--Rado theorem. In particular, I will discuss our conjecture, which can be viewed as a generalization of the EKR as well as an "uniform version" of the disproved Erdős--Frankl--Pach conjecture, and highlight some of our partial progress. Joint work with Ting-Wei Chao, Zixiang Xu, and Shengtong Zhang.

A basic result of probabilistic combinatorics, originally due to Erdős and Rényi, is the determination of the threshold at which the random graph $G_{n,p}$ contains a triangle with high probability. But one can also ask more refined versions of this question, where we ask not just for one triangle but for many triangles which interact in complicated ways. For example, what is the threshold at which we can no longer partition $G_{n,p}$ into two triangle-free subgraphs?


In this talk, I will discuss the proof of the Kohayakawa–Kreuter conjecture, which gives a general answer to all such questions. Rather surprisingly, a key step of the proof is a purely deterministic graph decomposition statement, closely related to classical results such as Nash-Williams' tree decomposition theorem, whose proof uses techniques from combinatorial optimization and structural graph theory.

Based on joint works with Micha Christoph, Eden Kuperwasser, Anders Martinsson, Wojciech Samotij, and Raphael Steiner.

A semialgebraic hypergraph is a hypergraph whose edges can be described by a system of polynomial inequalities. Semialgebraic hypergraphs appear in many problems in discrete geometry. There has been growing interest in semialgebraic hypergraphs since the discovery that they satisfy strong regularity lemmas, where between most parts, the hypergraph is either complete or empty. In this talk, I will talk about an optimal regularity lemma along these lines and several applications. Based on joint work with Jonathan Tidor.

The ($2$-dimensional) assignment problem is to find, in an edge weighted bipartite graph, an assignment (i.e., a perfect matching) of minimum total weight. Efficient algorithms for this problem have been known since the advent of modern algorithmic analysis. Moreover, if the edge weights are i.i.d. Exp(1) random variables and the host graph is complete bipartite, seminal results of Aldous state that the expected weight of the optimal assignment tends to $\zeta(2)$.

We consider high-dimensional versions of the random assignment problem. Here, we are given a cost array $M$, indexed by $[n]^k$, and with i.i.d. Exp(1) entries. The objective is to find a ${0,1}$-matrix A that minimizes $\sum_{x \in [n]^k} A_xM_x$, subject to the constraint that every axis-parallel line in A contains exactly one 1. This is the planar assignment problem, and when $k=2$ is equivalent to the usual random assignment problem. We prove that the expected cost of an optimal assignment is $\Theta(n^{k-2})$. Moreover, we describe a randomized algorithm that finds such an assignment with high probability. The main tool is iterative absorption, as developed by Glock, Kühn, Lo, and Osthus. The results answer questions of Frieze and Sorkin. The algorithmic result is in contrast to the axial assignment problem (in which A contains exactly one 1 in each axis-parallel co-dimension 1 hyperplane). For the latter, the best known bounds (which are due to Frankston, Kahn, Narayanan, and Park) exploit the connection between ``spread'' distributions and optimal assignments. Due to this reliance, no efficient algorithm is known.

Joint work with Ashwin Sah and Mehtaab Sawhney.