L6

Given a tournament with $d{n \choose 3}$ cycles of length three, how many cycles of length four must there be? Linial and Morgenstern (2016) conjectured that the minimum is asymptotically attained by "blowing up" a transitive tournament and orienting the edges randomly within the parts. This is reminiscent of the tight examples for the famous Triangle and Clique Density Theorems of Razborov, Nikiforov and Reiher. We prove the conjecture for $d \geq \frac{1}{36}$ using spectral methods. We also show that the family of tight examples is more complex than expected and fully characterise it for $d \geq \frac{1}{16}$. Joint work with Timothy Chan, Andrzej Grzesik and Daniel Král'.

Consider all planar graphs on n vertices. What is the smallest graph that contains them all as induced subgraphs? We provide an explicit construction of such a graph on $n^{4/3+o(1)}$ vertices, which improves upon the previous best upper bound of $n^{2+o(1)}$, obtained in 2007 by Gavoille and Labourel.

In this talk, we will gently introduce the audience to the notion of so-called universal graphs (graphs containing all graphs of a given family as induced subgraphs), and devote some time to a key lemma in the proof. That lemma comes from a recent breakthrough by Dujmovic et al. regarding the structure of planar graphs, and has already many interesting consequences - we hope the audience will be able to derive more. This is based on joint work with Cyril Gavoille and Michal Pilipczuk.

Let us fix a prime $p$. The Erdős-Ginzburg-Ziv problem asks for the minimum integer $s$ such that any collection of $s$ points in the lattice $\mathbb{Z}^n$ contains $p$ points whose centroid is also a lattice point in $\mathbb{Z}^n$. For large $n$, this is essentially equivalent to asking for the maximum size of a subset of $\mathbb{F}_p^n$ without $p$ distinct elements summing to zero.

In this talk, we discuss a new upper bound for this problem for any fixed prime $p\geq 5$ and large $n$. Our proof uses the so-called multi-colored sum-free theorem which is a consequence of the Croot-Lev-Pach polynomial method, as well as some new combinatorial ideas.

A subset $D$ of a finite cyclic group $\mathbb{Z}/m\mathbb{Z}$ is called a "perfect difference set" if every nonzero element of $\mathbb{Z}/m\mathbb{Z}$ can be written uniquely as the difference of two elements of $D$. If such a set exists, then a simple counting argument shows that $m=n^2+n+1$ for some nonnegative integer $n$. Singer constructed examples of perfect difference sets in $\mathbb{Z}/(n^2+n+1)\mathbb{Z}$ whenever $n$ is a prime power, and it is an old conjecture that these are the only such $n$ for which $\mathbb{Z}/(n^2+n+1)\mathbb{Z}$ contains a perfect difference set. In this talk, I will discuss a proof of an asymptotic version of this conjecture.