Combinatorial Theory Seminar

For a family $A$ in $\{0,...,k\}^n$, its deletion shadow is the set obtained from $A$ by deleting from any of its vectors one coordinate. Given the size of $A$, how should we choose $A$ to minimise its deletion shadow? And what happens if instead we may delete only a coordinate that is zero? We discuss these problems, and give an exact solution to the second problem.

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.

Modularity is a function on graphs which is used in algorithms for community detection. For a given graph G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in $G$. The (max) modularity $q^\ast(G)$ of the graph $G$ is defined to be the maximum over all vertex partitions of the modularity score, and satisfies $0 \leq q^\ast(G) \leq 1$.

We analyse when community structure of an underlying graph can be determined from an observed subset of the graph. In a natural model where we suppose edges in an underlying graph $G$ appear with some probability in our observed graph $G'$ we describe how high a sampling probability we need to infer the community structure of the underlying graph.

Joint work with Colin McDiarmid.

In this talk, we consider the random version of some classical extremal problems in the context of long cycles. This type of problems can also be seen as random analogues of the Turán number of long cycles, established by Woodall in 1972.

For a graph $G$ on $n$ vertices and a graph $H$, denote by $\text{ex}(G,H)$ the maximal number of edges in an $H$-free subgraph of $G$. We consider a random graph $G\sim G(n,p)$ where $p>C/n$, and determine the asymptotic value of $\text{ex}(G,C_t)$, for every $A\log(n)< t< (1- \varepsilon)n$. The behaviour of $\text{ex}(G,C_t)$ can depend substantially on the parity of $t$. In particular, our results match the classical result of Woodall, and demonstrate the transference principle in the context of long cycles.

Using similar techniques, we also prove a robustness-type result, showing the likely existence of cycles of prescribed lengths in a random subgraph of a graph with a nearly optimal density (a nearly ''Woodall graph"). If time permits, we will present some connections to size-Ramsey numbers of long cycles.

Based on joint works with Michael Krivelevich and Adva Mond.