David Conlon

A New Bound for the Brown--Erdős--Sós Problem

Let $f(n,v,e)$ denote the maximum number of edges in a $3$ -uniform hypergraph not containing $e$ edges spanned by at most $v$ vertices. One of the most influential open problems in extremal combinatorics then asks, for a given number of edges $e \geq 3$ , what is the smallest integer $d=d(e)$ so that $f(n,e+d,e) = o(n^2)$ ? This question has its origins in work of Brown, Erdős and Sós from the early 70's and the standard conjecture is that $d(e)=3$ for every $e \geq 3$ . The state of the art result regarding this problem was obtained in 2004 by Sárközy and Selkow, who showed that $f(n,e + 2 + \lfloor \log_2 e \rfloor,e) = o(n^2)$ . The only improvement over this result was a recent breakthrough of Solymosi and Solymosi, who improved the bound for $d(10)$ from 5 to 4. We obtain the first asymptotic improvement over the Sárközy--Selkow bound, showing that $f(n, e + O(\log e/ \log\log e), e) = o(n^2).$

Monochromatic components with many edges

Given an $r$ -edge-coloring of the complete graph $K_n$ , what is the largest number of edges in a monochromatic connected component? This natural question has only recently received the attention it deserves, with work by two disjoint subsets of the authors resolving it for the first two special cases, when $r = 2$ or $3$ . Here we introduce a general framework for studying this problem and apply it to fully resolve the $r = 4$ case, showing that any $4$ -edge-coloring of $K_n$ contains a monochromatic component with at least $\frac{1}{12}\binom{n}{2}$ edges, where the constant $\frac{1}{12}$ is optimal only when the coloring matches a certain construction of Gyárfás.

Ramsey numbers of books and quasirandomness

The book graph $B_n^{(k)}$ consists of $n$ copies of $K_{k+1}$ joined along a common $K_k$ . The Ramsey numbers of $B_n^{(k)}$ are known to have strong connections to the classical Ramsey numbers of cliques. Recently, the first author determined the asymptotic order of these Ramsey numbers for fixed $k$ , thus answering an old question of Erdős, Faudree, Rousseau, and Schelp. In this paper, we first provide a simpler proof of this theorem. Next, answering a question of the first author, we present a different proof that avoids the use of Szemerédi's regularity lemma, thus providing much tighter control on the error term. Finally, we prove a conjecture of Nikiforov, Rousseau, and Schelp by showing that all extremal colorings for this Ramsey problem are quasirandom.

Ramsey numbers of trails and circuits

We show that every two-colouring of the edges of the complete graph $K_n$ contains a monochromatic trail or circuit of length at least $2n^2/9 +o(n^2)$ , which is asymptotically best possible.

Set-coloring Ramsey numbers via codes

For positive integers $n,r,s$ with $r > s$ , the set-coloring Ramsey number $R(n;r,s)$ is the minimum $N$ such that if every edge of the complete graph $K_N$ receives a set of $s$ colors from a palette of $r$ colors, then there is guaranteed to be a monochromatic clique on $n$ vertices, that is, a subset of $n$ vertices where all of the edges between them receive a common color. In particular, the case $s=1$ corresponds to the classical multicolor Ramsey number. We prove general upper and lower bounds on $R(n;r,s)$ which imply that $R(n;r,s) = 2^{Θ(nr)}$ if $s/r$ is bounded away from $0$ and $1$ . The upper bound extends an old result of Erdős and Szemerédi, who treated the case $s = r-1$ , while the lower bound exploits a connection to error-correcting codes. We also study the analogous problem for hypergraphs.

Threshold Ramsey multiplicity for paths and even cycles

The Ramsey number $r(H)$ of a graph $H$ is the minimum integer $n$ such that any two-coloring of the edges of the complete graph $K_n$ contains a monochromatic copy of $H$ . While this definition only asks for a single monochromatic copy of $H$ , it is often the case that every two-edge-coloring of the complete graph on $r(H)$ vertices contains many monochromatic copies of $H$ . The minimum number of such copies over all two-colorings of $K_{r(H)}$ will be referred to as the threshold Ramsey multiplicity of $H$ . Addressing a problem of Harary and Prins, who were the first to systematically study this quantity, we show that there is a positive constant $c$ such that the threshold Ramsey multiplicity of a path or an even cycle on $k$ vertices is at least $(ck)^k$ . This bound is tight up to the constant $c$ . We prove a similar result for odd cycles in a companion paper.

preprint2021arXiv

Extremal numbers of cycles revisited

We give a simple geometric interpretation of an algebraic construction of Wenger that yields $n$ -vertex graphs with no cycle of length $4$ , $6$ or $10$ and close to the maximum number of edges.

preprint2020arXiv

Hypergraph expanders of all uniformities from Cayley graphs

Hypergraph expanders are hypergraphs with surprising, non-intuitive expansion properties. In a recent paper, the first author gave a simple construction, which can be randomized, of $3$ -uniform hypergraph expanders with polylogarithmic degree. We generalize this construction, giving a simple construction of $r$ -uniform hypergraph expanders for all $r \geq 3$ .

preprint2020arXiv

More on the extremal number of subdivisions

Given a graph $H$ , the extremal number $\mathrm{ex}(n,H)$ is the largest number of edges in an $H$ -free graph on $n$ vertices. We make progress on a number of conjectures about the extremal number of bipartite graphs. First, writing $K'_{s,t}$ for the subdivision of the bipartite graph $K_{s,t}$ , we show that $\mathrm{ex}(n, K'_{s,t}) = O(n^{3/2 - \frac{1}{2s}})$ . This proves a conjecture of Kang, Kim and Liu and is tight up to the implied constant for $t$ sufficiently large in terms of $s$ . Second, for any integers $s, k \geq 1$ , we show that $\mathrm{ex}(n, L) = Θ(n^{1 + \frac{s}{sk+1}})$ for a particular graph $L$ depending on $s$ and $k$ , answering another question of Kang, Kim and Liu. This result touches upon an old conjecture of Erdős and Simonovits, which asserts that every rational number $r \in (1,2)$ is realisable in the sense that $\mathrm{ex}(n,H) = Θ(n^r)$ for some appropriate graph $H$ , giving infinitely many new realisable exponents and implying that $1 + 1/k$ is a limit point of realisable exponents for all $k \geq 1$ . Writing $H^k$ for the $k$ -subdivision of a graph $H$ , this result also implies that for any bipartite graph $H$ and any $k$ , there exists $δ> 0$ such that $\mathrm{ex}(n,H^{k-1}) = O(n^{1 + 1/k - δ})$ , partially resolving a question of Conlon and Lee. Third, extending a recent result of Conlon and Lee, we show that any bipartite graph $H$ with maximum degree $r$ on one side which does not contain $C_4$ as a subgraph satisfies $\mathrm{ex}(n, H) = o(n^{2 - 1/r})$ .

preprint2020arXiv

Short proofs of some extremal results III

We prove a selection of results from different areas of extremal combinatorics, including complete or partial solutions to a number of open problems. These results, coming mainly from extremal graph theory and Ramsey theory, have been collected together because in each case the relevant proofs are reasonably short.

A sequence of triangle-free pseudorandom graphs

A construction of Alon yields a sequence of highly pseudorandom triangle-free graphs with edge density significantly higher than one might expect from comparison with random graphs. We give an alternative construction for such graphs.

Almost-spanning universality in random graphs

A graph $G$ is said to be $\mathcal H(n,Δ)$ -universal if it contains every graph on $n$ vertices with maximum degree at most $Δ$ . It is known that for any $\varepsilon > 0$ and any natural number $Δ$ there exists $c > 0$ such that the random graph $G(n,p)$ is asymptotically almost surely $\mathcal H((1-\varepsilon)n,Δ)$ -universal for $p \geq c (\log n/n)^{1/Δ}$ . Bypassing this natural boundary, we show that for $Δ\geq 3$ the same conclusion holds when $p = ω\left(n^{-\frac{1}{Δ-1}}\log^5 n\right)$ .

Hereditary quasirandomness without regularity

A result of Simonovits and Sós states that for any fixed graph $H$ and any $ε> 0$ there exists $δ> 0$ such that if $G$ is an $n$ -vertex graph with the property that every $S \subseteq V(G)$ contains $p^{e(H)} |S|^{v(H)} \pm δn^{v(H)}$ labeled copies of $H$ , then $G$ is quasirandom in the sense that every $S \subseteq V(G)$ contains $\frac{1}{2} p |S|^2 \pm εn^2$ edges. The original proof of this result makes heavy use of the regularity lemma, resulting in a bound on $δ^{-1}$ which is a tower of twos of height polynomial in $ε^{-1}$ . We give an alternative proof of this theorem which avoids the regularity lemma and shows that $δ$ may be taken to be linear in $ε$ when $H$ is a clique and polynomial in $ε$ for general $H$ . This answers a problem raised by Simonovits and Sós.

Ordered Ramsey numbers

Given a labeled graph $H$ with vertex set $\{1, 2,\ldots,n\}$ , the ordered Ramsey number $r_<(H)$ is the minimum $N$ such that every two-coloring of the edges of the complete graph on $\{1, 2, \ldots,N\}$ contains a copy of $H$ with vertices appearing in the same order as in $H$ . The ordered Ramsey number of a labeled graph $H$ is at least the Ramsey number $r(H)$ and the two coincide for complete graphs. However, we prove that even for matchings there are labelings where the ordered Ramsey number is superpolynomial in the number of vertices. Among other results, we also prove a general upper bound on ordered Ramsey numbers which implies that there exists a constant $c$ such that $r_<(H) \leq r(H)^{c \log^2 n}$ for any labeled graph $H$ on vertex set $\{1,2, \dots, n\}$ .

Short proofs of some extremal results II

We prove several results from different areas of extremal combinatorics, including complete or partial solutions to a number of open problems. These results, coming mainly from extremal graph theory and Ramsey theory, have been collected together because in each case the relevant proofs are quite short.

preprint2015arXiv

Hedgehogs are not colour blind

We exhibit a family of $3$ -uniform hypergraphs with the property that their $2$ -colour Ramsey numbers grow polynomially in the number of vertices, while their $4$ -colour Ramsey numbers grow exponentially. This is the first example of a class of hypergraphs whose Ramsey numbers show a strong dependence on the number of colours.

preprint2015arXiv

Monochromatic cycle partitions in local edge colourings

An edge colouring of a graph is said to be an $r$ -local colouring if the edges incident to any vertex are coloured with at most $r$ colours. Generalising a result of Bessy and Thomassé, we prove that the vertex set of any $2$ -locally coloured complete graph may be partitioned into two disjoint monochromatic cycles of different colours. Moreover, for any natural number $r$ , we show that the vertex set of any $r$ -locally coloured complete graph may be partitioned into $O(r^2 \log r)$ disjoint monochromatic cycles. This generalises a result of Erdős, Gyárfás and Pyber.

preprint2015arXiv

Recent developments in graph Ramsey theory

Given a graph $H$ , the Ramsey number $r(H)$ is the smallest natural number $N$ such that any two-colouring of the edges of $K_N$ contains a monochromatic copy of $H$ . The existence of these numbers has been known since 1930 but their quantitative behaviour is still not well understood. Even so, there has been a great deal of recent progress on the study of Ramsey numbers and their variants, spurred on by the many advances across extremal combinatorics. In this survey, we will describe some of this progress.

A relative Szemerédi theorem

The celebrated Green-Tao theorem states that there are arbitrarily long arithmetic progressions in the primes. One of the main ingredients in their proof is a relative Szemerédi theorem which says that any subset of a pseudorandom set of integers of positive relative density contains long arithmetic progressions. In this paper, we give a simple proof of a strengthening of the relative Szemerédi theorem, showing that a much weaker pseudorandomness condition is sufficient. Our strengthened version can be applied to give the first relative Szemerédi theorem for $k$ -term arithmetic progressions in pseudorandom subsets of $\mathbb{Z}_N$ of density $N^{-c_k}$ . The key component in our proof is an extension of the regularity method to sparse pseudorandom hypergraphs, which we believe to be interesting in its own right. From this we derive a relative extension of the hypergraph removal lemma. This is a strengthening of an earlier theorem used by Tao in his proof that the Gaussian primes contain arbitrarily shaped constellations and, by standard arguments, allows us to deduce the relative Szemerédi theorem.

Combinatorial theorems relative to a random set

We describe recent advances in the study of random analogues of combinatorial theorems.

Cycle packing

In the 1960s, Erdős and Gallai conjectured that the edge set of every graph on n vertices can be partitioned into O(n) cycles and edges. They observed that one can easily get an O(n log n) upper bound by repeatedly removing the edges of the longest cycle. We make the first progress on this problem, showing that O(n log log n) cycles and edges suffice. We also prove the Erdős-Gallai conjecture for random graphs and for graphs with linear minimum degree.

Large subgraphs without complete bipartite graphs

In this note, we answer the following question of Foucaud, Krivelevich and Perarnau. What is the size of the largest $K_{r,s}$ -free subgraph one can guarantee in every graph $G$ with $m$ edges? We also discuss the analogous problem for hypergraphs.

On the grid Ramsey problem and related questions

The Hales--Jewett theorem is one of the pillars of Ramsey theory, from which many other results follow. A celebrated theorem of Shelah says that Hales--Jewett numbers are primitive recursive. A key tool used in his proof, now known as the cube lemma, has become famous in its own right. In its simplest form, this lemma says that if we color the edges of the Cartesian product $K_n \times K_n$ in $r$ colors then, for $n$ sufficiently large, there is a rectangle with both pairs of opposite edges receiving the same color. Shelah's proof shows that $n = r^{\binom{r+1}{2}} + 1$ suffices. More than twenty years ago, Graham, Rothschild and Spencer asked whether this bound can be improved to a polynomial in $r$ . We show that this is not possible by providing a superpolynomial lower bound in $r$ . We also discuss a number of related problems.

Extremal results in sparse pseudorandom graphs

Szemerédi's regularity lemma is a fundamental tool in extremal combinatorics. However, the original version is only helpful in studying dense graphs. In the 1990s, Kohayakawa and Rödl proved an analogue of Szemerédi's regularity lemma for sparse graphs as part of a general program toward extending extremal results to sparse graphs. Many of the key applications of Szemerédi's regularity lemma use an associated counting lemma. In order to prove extensions of these results which also apply to sparse graphs, it remained a well-known open problem to prove a counting lemma in sparse graphs. The main advance of this paper lies in a new counting lemma, proved following the functional approach of Gowers, which complements the sparse regularity lemma of Kohayakawa and Rödl, allowing us to count small graphs in regular subgraphs of a sufficiently pseudorandom graph. We use this to prove sparse extensions of several well-known combinatorial theorems, including the removal lemmas for graphs and groups, the Erdős-Stone-Simonovits theorem and Ramsey's theorem. These results extend and improve upon a substantial body of previous work.

Linear forms from the Gowers uniformity norm

This is a companion note to our paper 'A relative Szemerédi theorem', elaborating on a concluding remark. In that paper, we showed how to prove a relative Szemerédi theorem for $(r+1)$ -term arithmetic progressions assuming a linear forms condition. Here we show how to replace this condition with an assumption about the Gowers uniformity norm $U^r$ .

Ramsey numbers of cubes versus cliques

The cube graph Q_n is the skeleton of the n-dimensional cube. It is an n-regular graph on 2^n vertices. The Ramsey number r(Q_n, K_s) is the minimum N such that every graph of order N contains the cube graph Q_n or an independent set of order s. Burr and Erdos in 1983 asked whether the simple lower bound r(Q_n, K_s) >= (s-1)(2^n - 1)+1 is tight for s fixed and n sufficiently large. We make progress on this problem, obtaining the first upper bound which is within a constant factor of the lower bound.

Ramsey-type results for semi-algebraic relations

A k-ary semi-algebraic relation E on R^d is a subset of R^{kd}, the set of k-tuples of points in R^d, which is determined by a finite number of polynomial equations and inequalities in kd real variables. The description complexity of such a relation is at most t if the number of polynomials and their degrees are all bounded by t. A subset A of R^d is called homogeneous if all or none of the k-tuples from A satisfy E. A large number of geometric Ramsey-type problems and results can be formulated as questions about finding large homogeneous subsets of sets in R^d equipped with semi-algebraic relations. In this paper we study Ramsey numbers for k-ary semi-algebraic relations of bounded complexity and give matching upper and lower bounds, showing that they grow as a tower of height k-1. This improves on a direct application of Ramsey's theorem by one exponential and extends a result of Alon, Pach, Pinchasi, Radoičić, and Sharir, who proved this for k=2. We apply our results to obtain new estimates for some geometric Ramsey-type problems relating to order types and one-sided sets of hyperplanes. We also study the off-diagonal case, achieving some partial results.