Development in Combinatorics 4th workshop 2024

For a $k$-uniform hypergraph (or simply $k$-graph) $F$, the codegree Turán density $\pi_{\mathrm{co}} (F)$ is the supremum over all $\alpha$ such that there exist arbitrarily large $n$-vertex $F$-free $k$-graphs $H$ in which every $(k-1)$-subset of $V(H)$ is contained in at least $\alpha n$ edges. In this talk, I will introduce our recent progress on the problem of what $3$-graphs $F$ satisfy $\pi_{\mathrm{co}} (F)=0$.

Our proof relies on a random geometric construction, graph distributions, Ramsey’s theorem and a new formulation of the characterization of $3$-graphs with vanishing uniform Turán density due to Reiher, Rödl and Schacht. Joint work with Ander Lamaison, Hong Liu, Shuaichao Wang and Haotian Yang.

A zero-one matrix M is said to contain another zero-one matrix A if we can delete some rows and columns of M and replace some 1-entries with 0-entries such that the resulting matrix is A. The extremal number of A, denoted ex(n,A), is the maximum number of 1-entries that an n×n zero-one matrix can have without containing A. We will describe known results and motivations for studying this problem, and give the first asymptotically tight general bound, showing that if A has at most t one-entries in every row, then ex(n,A)≤n^{2−1/t+o(1)}. This verifies a conjecture of Methuku and Tomon, and provides a generalisation to a celebrated result of Füredi and Alon—Krivelevich—Sudakov about the Turán numbers of bipartite graphs. Joint work with Oliver Janzer, Van Magnan and Abhishek Methuku.

Consider a quadratic polynomial $Q(\xi_{1},\dots,\xi_{n})$ of a random binary sequence $\xi_{1},\dots,\xi_{n}$. To what extent can $Q(\xi_{1},\dots,\xi_{n})$ concentrate on a single value? This is a quadratic version of the classical Littlewood-Offord problem; it was was popularised by Costello, Tao and Vu in their study of symmetric random matrices, and has since become a rich source of connections between combinatorics, probability and computer science. In this talk we will discuss a new essentially optimal bound for the quadratic Littlewood-Offord problem, as conjectured by Nguyen and Vu. Joint work with Lisa Sauermann.

A meta-conjecture of Coulson, Keevash, Perarnau and Yepremyan states that above the extremal threshold for a given spanning structure in a (hyper-)graph, one can find a rainbow version of that spanning structure in any suitably bounded colouring of the host (hyper-)graph. We solve one of the most pertinent outstanding cases of this conjecture, by showing that for any $1\leq j\leq k-1$, if $G$ is a $k$-graph above the $j$-degree threshold for a loose Hamilton cycle, then any globally bounded colouring of $G$ contains a rainbow loose Hamilton cycle. This represents joint work with Amarja Kathapurkar and Guillem Perarnau.

The right-angled Coxeter group (or RACG) W=W(Γ) with presentation graph Γ = (V,E) is the group with generators V and relations aa=1 and ab=ba for all a ∈ V and ab ∈ E. By taking Γ to be an instance of the Erdős–Rényi random graph model on n vertices with edge probability p = p(n), one can generate a model for random RACG. In recent years, geometric group theorists have investigated this model with a particular emphasis on the typical geometric properties of the random RACG. In this talk I will explain how one can obtain a rough threshold for relative hyperbolicity in this model and discuss the related problem of square percolation in random graphs. Joint work with R. Altar Çiçeksiz and Jason Berhstock.

A new model of random graphs emerged with the theory of dense graph limits. This model is parametrized by a graphon W, and generalizes Erdős-Renyi random graphs G(n,p) for p constant. While the inhomogeneous random graph G(n,W) is “dense”, on two classical problems from the theory of random graphs (the maximum clique problem and the connectivity problem) I will show that in a sense it can encompass also sparse random graphs. Based on [Dolezal, H., Mathe: Cliques in dense inhomogeneous random graphs] and [H., Viswanathan: Connectivity of inhomogeneous random graphs II].

A fundamental theorem of Nikiforov states that if a graph $G$ contains many copies of a fixed graph $H$, then it contains a large blowup of $H$. In this talk, I will discuss this theorem, some of its applications, as well as a recent result which determines the optimal quantitative dependencies in case $H$ is triangle-free. Joint work with António Girão and Zach Hunter.

The r-colour Ramsey number $R_r(k)$ is the minimum $n\in \mathbb{N}$ such that every r-colouring of the edges of the complete graph $K_n$ on n vertices contains a monochromatic copy of $K_k$. In this talk I will show that for each fixed $r\geq 2$, that

$$R_r(k)\leq \exp(-\delta k)r^{rk}$$

for some constant δ=δ(r)>0 and all sufficiently large $k\in \mathbb{N}$. For each $r\geq 3$, this is the first exponential improvement over the upper bound of Erdős and Szekeres from 1935. The proof uses a new geometric lemma and a new algorithm to find almost optimal monochromatic ‘books’.

This is joint work with Paul Balister, Béla Bollobás, Simon Griffiths, Eoin Hurley, Robert Morris, Julian Sahasrabudhe and Marius Tiba.

We study Turán problems for hypergraphs with an additional uniformity condition on the edge distribution. This kind of Turán problems was introduced by Erdős and Sós in the 1980s but it took more than 30 years until the first non-trivial exact results were obtained. Central to the study of the uniform Turán density of hypergraphs are palette constructions, which were implicitly introduced by Rödl in the 1980s. We prove that palette constructions always yield tight lower bounds, unconditionally confirming present empirical evidence. This results in new and simpler approaches to determining uniform Turán densities, which completely bypass the use of the hypergraph regularity method.