Search

For $p$ prime, $A \subseteq \mathbb{Z}/p\mathbb{Z}$ and $\lambda \in \mathbb{Z}$, the sum of dilates $A + \lambda \cdot A$ is defined by \[A + \lambda \cdot A = \{a + \lambda a' : a, a' \in A\}.\] The basic problem on such sums of dilates asks for the minimum size of $|A + \lambda \cdot A|$ for given $\lambda$, $A$ of given density $\alpha$, and $p$ tending to infinity. We investigate this problem for $\alpha$ fixed and $\lambda$ tending to infinity, proving near-optimal bounds in this case., Comment: 9 pages. To appear in The American Mathematical Monthly

We show that for every non-spherical set $X$ in $\mathbb{E}^d$, there exists a natural number $m$ and a red/blue-colouring of $\mathbb{E}^n$ for every $n$ such that there is no red copy of X and no blue progression of length $m$ with each consecutive point at distance $1$. This verifies a conjecture of Wu and the first author.

We show that for every integer $k\geq3$, the set of Tur\'an densities of $k$-uniform hypergraphs has an accumulation point in $[0,1)$. In particular, $1/2$ is an accumulation point for the set of Tur\'an densities of $3$-uniform hypergraphs., Comment: 6 pages

Let $ES_{\ell}(n)$ be the minimum $N$ such that every $N$-element point set in the plane contains either $\ell$ collinear members or $n$ points in convex position. We prove that there is a constant $C>0$ such that, for each $\ell, n \ge 3$, $$ (3\ell - 1) \cdot 2^{n-5} < ES_{\ell}(n) < \ell^2 \cdot 2^{n+ C\sqrt{n\log n}}.$$ A similar extension of the well-known Erd\H os--Szekeres cups-caps theorem is also proved.

A graph $H$ is said to be positive if the homomorphism density $t_H(G)$ is non-negative for all weighted graphs $G$. The positive graph conjecture proposes a characterisation of such graphs, saying that a graph is positive if and only if it is symmetric, in the sense that it is formed by gluing two copies of some subgraph along an independent set. We prove several results relating to this conjecture. First, we make progress towards the conjecture itself by showing that any connected positive graph must have a vertex of even degree. We then make use of this result to identify some new counterexamples to the analogue of Sidorenko's conjecture for hypergraphs. In particular, we show that, for $r$ odd, every $r$-uniform tight cycle is a counterexample, generalising a recent result of Conlon, Lee and Sidorenko that dealt with the case $r=3$. Finally, we relate the positive graph conjecture to the emerging study of graph codes by showing that any positive graph has vanishing graph code density, thereby improving a result of Alon who proved the same result for symmetric graphs. Our proofs make use of a variety of tools and techniques, including the properties of independence polynomials, hypergraph quasirandomness and discrete Fourier analysis., Comment: 14 pages

Answering a question of Erd\H{o}s and Graham, we show that for each fixed positive rational number $x$ the number of ways to write $x$ as a sum of reciprocals of distinct positive integers each at most $n$ is $2^{(c_x + o(1))n}$ for an explicit constant $c_x$ increasing with $x$., Comment: 8 pages

A fundamental problem in Ramsey theory is to determine the growth rate in terms of $n$ of the Ramsey number $r(H, K_n^{(3)})$ of a fixed $3$-uniform hypergraph $H$ versus the complete $3$-uniform hypergraph with $n$ vertices. We study this problem, proving two main results. First, we show that for a broad class of $H$, including links of odd cycles and tight cycles of length not divisible by three, $r(H, K_n^{(3)}) \ge 2^{\Omega_H(n \log n)}$. This significantly generalizes and simplifies an earlier construction of Fox and He which handled the case of links of odd cycles and is sharp both in this case and for all but finitely many tight cycles of length not divisible by three. Second, disproving a folklore conjecture in the area, we show that there exists a linear hypergraph $H$ for which $r(H, K_n^{(3)})$ is superpolynomial in $n$. This provides the first example of a separation between $r(H,K_n^{(3)})$ and $r(H,K_{n,n,n}^{(3)})$, since the latter is known to be polynomial in $n$ when $H$ is linear., Comment: 22 pages

We show that for every positive integer $k$ there are positive constants $C$ and $c$ such that if $A$ is a subset of $\{1, 2, \dots, n\}$ of size at least $C n^{1/k}$, then, for some $d \leq k-1$, the set of subset sums of $A$ contains a homogeneous $d$-dimensional generalized arithmetic progression of size at least $c|A|^{d+1}$. This strengthens a result of Szemer\'edi and Vu, who proved a similar statement without the homogeneity condition. As an application, we make progress on the Erd\H{o}s--Straus non-averaging sets problem, showing that every subset $A$ of $\{1, 2, \dots, n\}$ of size at least $n^{\sqrt{2} - 1 + o(1)}$ contains an element which is the average of two or more other elements of $A$. This gives the first polynomial improvement on a result of Erd\H{o}s and S\'ark\"ozy from 1990., Comment: 34 pages

A simplicial complex $H$ consists of a pair of sets $(V,E)$ where $V$ is a set of vertices and $E\subseteq\mathscr{P}(V)$ is a collection of subsets of $V$ closed under taking subsets. Given a simplicial complex $F$ and $n\in \mathbb N$, the extremal number $\text{ex}(n,F)$ is the maximum number of edges that a simplicial complex on $n$ vertices can have without containing a copy of $F$. We initiate the systematic study of extremal numbers in this context by asymptotically determining the extremal numbers of several natural simplicial complexes. In particular, we asymptotically determine the extremal number of a simplicial complex for which the extremal example has more than one incomplete layer., Comment: 22 pages

An old problem in discrete geometry, originating with Kupitz, asks whether there is a fixed natural number $k$ such that every finite set of points in the plane has a line through at least two of its points where the number of points on either side of this line differ by at most $k$. We give a negative answer to a natural variant of this problem, showing that for every natural number $k$ there exists a finite set of points in the plane together with a pseudoline arrangement such that each pseudoline contains at least two points and there is a pseudoline through any pair of points where the number of points on either side of each pseudoline differ by at least $k$., Comment: 27 pages, 24 figures

Building on recent work of Mattheus and Verstra\"ete, we establish a general connection between Ramsey numbers of the form $r(F,t)$ for $F$ a fixed graph and a variant of the Zarankiewicz problem asking for the maximum number of 1s in an $m$ by $n$ $0/1$-matrix that does not have any matrix from a fixed finite family $\mathcal{L}(F)$ derived from $F$ as a submatrix. As an application, we give new lower bounds for the Ramsey numbers $r(C_5,t)$ and $r(C_7,t)$, namely, $r(C_5,t) = \tilde\Omega(t^{\frac{10}{7}})$ and $r(C_7,t) = \tilde\Omega(t^{\frac{5}{4}})$. We also show how the truth of a plausible conjecture about Zarankiewicz numbers would allow an approximate determination of $r(C_{2\ell+1}, t)$ for any fixed integer $\ell \geq 2$., Comment: 9 pages

Sidorenko's conjecture states that, for all bipartite graphs $H$, quasirandom graphs contain asymptotically the minimum number of copies of $H$ taken over all graphs with the same order and edge density. While still open for graphs, the analogous statement is known to be false for hypergraphs. We show that there is some advantage in this, in that if Sidorenko's conjecture does not hold for a particular $r$-partite $r$-uniform hypergraph $H$, then it is possible to improve the standard lower bound, coming from the probabilistic deletion method, for its extremal number $\mathrm{ex}(n,H)$, the maximum number of edges in an $n$-vertex $H$-free $r$-uniform hypergraph. With this application in mind, we find a range of new counterexamples to the conjecture for hypergraphs, including all linear hypergraphs containing a loose triangle and all $3$-partite $3$-uniform tight cycles., Comment: 15 pages, to appear in Int. Math. Res. Not

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 a subset of $n$ vertices where all of the edges between them receive a common color. If $n$ is fixed and $\frac{s}{r}$ is less than and bounded away from $1-\frac{1}{n-1}$, then $R(n;r,s)$ is known to grow exponentially in $r$, while if $\frac{s}{r}$ is greater than and bounded away from $1-\frac{1}{n-1}$, then $R(n;r,s)$ is bounded. Here we prove bounds for $R(n;r,s)$ in the intermediate range where $\frac{s}{r}$ is close to $1 - \frac{1}{n-1}$ by establishing a connection to the maximum size of error-correcting codes near the zero-rate threshold.

We say that a graph $H$ dominates another graph $H'$ if the number of homomorphisms from $H'$ to any graph $G$ is dominated, in an appropriate sense, by the number of homomorphisms from $H$ to $G$. We study the family of dominating graphs, those graphs with the property that they dominate all of their subgraphs. It has long been known that even-length paths are dominating in this sense and a result of Hatami implies that all weakly norming graphs are dominating. In a previous paper, we showed that every finite reflection group gives rise to a family of weakly norming, and hence dominating, graphs. Here we revisit this connection to show that there is a much broader class of dominating graphs., Comment: 16 pages, to appear in Math. Proc. Cambridge Philos. Soc

We show that there is an absolute constant $c>0$ such that $|A+\lambda\cdot A|\geq e^{c\sqrt{\log |A|}}|A|$ for any finite subset $A$ of $\mathbb{R}$ and any transcendental number $\lambda\in\mathbb{R}$. By a construction of Konyagin and Laba, this is best possible up to the constant $c$., Comment: 7 pages

Let $K_m^{(3)}$ denote the complete $3$-uniform hypergraph on $m$ vertices and $S_n^{(3)}$ the $3$-uniform hypergraph on $n+1$ vertices consisting of all $\binom{n}{2}$ edges incident to a given vertex. Whereas many hypergraph Ramsey numbers grow either at most polynomially or at least exponentially, we show that the off-diagonal Ramsey number $r(K_{4}^{(3)},S_n^{(3)})$ exhibits an unusual intermediate growth rate, namely, \[ 2^{c \log^2 n} \le r(K_{4}^{(3)},S_n^{(3)}) \le 2^{c' n^{2/3}\log n} \] for some positive constants $c$ and $c'$. The proof of these bounds brings in a novel Ramsey problem on grid graphs which may be of independent interest: what is the minimum $N$ such that any $2$-edge-coloring of the Cartesian product $K_N \square K_N$ contains either a red rectangle or a blue $K_n$?, Comment: 13 pages

Let $\ell_m$ be a sequence of $m$ points on a line with consecutive points at distance one. Answering a question raised by Fox and the first author and independently by Arman and Tsaturian, we show that there is a natural number $m$ and a red/blue-colouring of $\mathbb{E}^n$ for every $n$ that contains no red copy of $\ell_3$ and no blue copy of $\ell_m$., Comment: 4 pages

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^{\Theta(nr)}$ if $s/r$ is bounded away from $0$ and $1$. The upper bound extends an old result of Erd\H{o}s and Szemer\'edi, 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., Comment: 11 pages

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\'arf\'as., Comment: 12 pages, 4 figures. Replaced with revised version

We show that if $\mathcal{L}_1$ and $\mathcal{L}_2$ are linear transformations from $\mathbb{Z}^d$ to $\mathbb{Z}^d$ satisfying certain mild conditions, then, for any finite subset $A$ of $\mathbb{Z}^d$, $$|\mathcal{L}_1 A+\mathcal{L}_2 A|\geq \left(|\det(\mathcal{L}_1)|^{1/d}+|\det(\mathcal{L}_2)|^{1/d}\right)^d|A|- o(|A|).$$ This result corrects and confirms the two-summand case of a conjecture of Bukh and is best possible up to the lower-order term for many choices of $\mathcal{L}_1$ and $\mathcal{L}_2$. As an application, we prove a lower bound for $|A + \lambda \cdot A|$ when $A$ is a finite set of real numbers and $\lambda$ is an algebraic number. In particular, when $\lambda$ is of the form $(p/q)^{1/d}$ for some $p, q, d \in \mathbb{N}$, each taken as small as possible for such a representation, we show that $$|A + \lambda \cdot A| \geq (p^{1/d} + q^{1/d})^d |A| - o(|A|).$$ This is again best possible up to the lower-order term and extends a recent result of Krachun and Petrov which treated the case $\lambda = \sqrt{2}$., Comment: 24 pages

A longstanding conjecture of Erd\H{o}s and Simonovits states that for every rational $r$ between $1$ and $2$ there is a graph $H$ such that the largest number of edges in an $H$-free graph on $n$ vertices is $\Theta(n^r)$. Answering a question raised by Jiang, Jiang and Ma, we show that the conjecture holds for all rationals of the form $2 - a/b$ with $b$ sufficiently large in terms of $a$., Comment: 10 pages

We show that the size-Ramsey number of the $\sqrt{n} \times \sqrt{n}$ grid graph is $O(n^{5/4})$, improving a previous bound of $n^{3/2 + o(1)}$ by Clemens, Miralaei, Reding, Schacht, and Taraz., Comment: 8 pages, 1 figure

The size Ramsey number of a graph $H$ is defined as the minimum number of edges in a graph $G$ such that there is a monochromatic copy of $H$ in every two-coloring of $E(G)$. The size Ramsey number was introduced by Erd\H{o}s, Faudree, Rousseau, and Schelp in 1978 and they ended their foundational paper by asking whether one can determine up to a constant factor the size Ramsey numbers of three families of graphs: complete bipartite graphs, book graphs (obtained by adding many common neighbors to the vertices of a clique), and starburst graphs (obtained by adding many pendant edges to each vertex of a clique). In this paper, we completely resolve the latter two questions and make substantial progress on the first by determining the size Ramsey number of $K_{s,t}$ up to a constant factor for all $t = \Omega(s\log s)$., Comment: 23 pages

The book graph $B_n^{(k)}$ consists of $n$ copies of $K_{k+1}$ joined along a common $K_k$. In the prequel to this paper, we studied the diagonal Ramsey number $r(B_n^{(k)}, B_n^{(k)})$. Here we consider the natural off-diagonal variant $r(B_{cn}^{(k)}, B_n^{(k)})$ for fixed $c \in (0,1]$. In this more general setting, we show that an interesting dichotomy emerges: for very small $c$, a simple $k$-partite construction dictates the Ramsey function and all nearly-extremal colorings are close to being $k$-partite, while, for $c$ bounded away from $0$, random colorings of an appropriate density are asymptotically optimal and all nearly-extremal colorings are quasirandom. Our investigations also open up a range of questions about what happens for intermediate values of $c$., Comment: 36 pages

Let $d \geq 2$ be a natural number. We show that $$|A-A| \geq \left(2d-2 + \frac{1}{d-1}\right)|A|-(2d^2-4d+3)$$ for any sufficiently large finite subset $A$ of $\mathbb{R}^d$ that is not contained in a translate of a hyperplane. By a construction of Stanchescu, this is best possible and thus resolves an old question first raised by Uhrin., Comment: 15 pages

We show that the size-Ramsey number of any cubic graph with $n$ vertices is $O(n^{8/5})$, improving a bound of $n^{5/3 + o(1)}$ due to Kohayakawa, R\"{o}dl, Schacht, and Szemer\'{e}di. The heart of the argument is to show that there is a constant $C$ such that a random graph with $C n$ vertices where every edge is chosen independently with probability $p \geq C n^{-2/5}$ is with high probability Ramsey for any cubic graph with $n$ vertices. This latter result is best possible up to the constant., Comment: 15 pages

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., Comment: 3 pages

We show that any finite $S \subset \mathbb{R}^d$ in general position has arbitrarily large supersets $T \supseteq S$ in general position with the property that $T$ contains no empty convex polygon, or hole, with $C_d$ points, where $C_d$ is an integer that depends only on the dimension $d$. This generalises results of Horton and Valtr which treat the case $S = \emptyset$. The key step in our proof, which may be of independent interest, is to show that there are arbitrarily small perturbations of the set of lattice points $[n]^d$ with no large holes., Comment: 17 pages

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., Comment: 28 pages

The Ramsey number $r(H)$ of a graph $H$ is the minimum $n$ such that any two-coloring of the edges of the complete graph $K_n$ contains a monochromatic copy of $H$. The threshold Ramsey multiplicity $m(H)$ is then the minimum number of monochromatic copies of $H$ taken over all two-edge-colorings of $K_{r(H)}$. The study of this concept was first proposed by Harary and Prins almost fifty years ago. In a companion paper, the authors have shown that there is a positive constant $c$ such that the threshold Ramsey multiplicity for a path or even cycle with $k$ vertices is at least $(ck)^k$, which is tight up to the value of $c$. Here, using different methods, we show that the same result also holds for odd cycles with $k$ vertices., Comment: 17 pages

For which graphs $F$ is there a sparse $F$-counting lemma in $C_4$-free graphs? We are interested in identifying graphs $F$ with the property that, roughly speaking, if $G$ is an $n$-vertex $C_4$-free graph with on the order of $n^{3/2}$ edges, then the density of $F$ in $G$, after a suitable normalization, is approximately at least the density of $F$ in an $\epsilon$-regular approximation of $G$. In recent work, motivated by applications in extremal and additive combinatorics, we showed that $C_5$ has this property. Here we construct a family of graphs with the property., Comment: 13 pages

We show that in any two-coloring of the positive integers there is a color for which the set of positive integers that can be represented as a sum of distinct elements with this color has upper logarithmic density at least $(2+\sqrt{3})/4$ and this is best possible. This answers a forty-year-old question of Erd\H{o}s., Comment: 9 pages

We develop novel techniques which allow us to prove a diverse range of results relating to subset sums and complete sequences of positive integers, including solutions to several longstanding open problems. These include: solutions to the three problems of Burr and Erd\H{o}s on Ramsey complete sequences, for which Erd\H{o}s later offered a combined total of \$350; analogous results for the new notion of density complete sequences; the solution to a conjecture of Alon and Erd\H{o}s on the minimum number of colors needed to color the positive integers less than $n$ so that $n$ cannot be written as a monochromatic sum; the exact determination of an extremal function introduced by Erd\H{o}s and Graham on sets of integers avoiding a given subset sum; and, answering a question reiterated by several authors, a homogeneous strengthening of a seminal result of Szemer\'edi and Vu on long arithmetic progressions in subset sums., Comment: 75 pages

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., Comment: 4 pages, to appear in Amer. Math. Monthly

By using random multilinear maps, we provide new lower bounds for the Erd\H{o}s box problem, the problem of estimating the extremal number of the complete $d$-partite $d$-uniform hypergraph with two vertices in each part, thereby improving on work of Gunderson, R\"{o}dl and Sidorenko., Comment: Reformatted for Discrete Analysis

We give an exponential improvement to the lower bound on diagonal Ramsey numbers for any fixed number of colors greater than two., Comment: 4 pages

The Zarankiewicz problem asks for an estimate on $z(m, n; s, t)$, the largest number of $1$'s in an $m \times n$ matrix with all entries $0$ or $1$ containing no $s \times t$ submatrix consisting entirely of $1$'s. We show that a classical upper bound for $z(m, n; s, t)$ due to K\H{o}v\'ari, S\'os and Tur\'an is tight up to the constant for a broad range of parameters. The proof relies on a new quantitative variant of the random algebraic method., Comment: 6 pages

We develop a sparse graph regularity method that applies to graphs with few 4-cycles, including new counting and removal lemmas for 5-cycles in such graphs. Some applications include: * Every $n$-vertex graph with no 5-cycle can be made triangle-free by deleting $o(n^{3/2})$ edges. * For $r \geq 3$, every $n$-vertex $r$-graph with girth greater than $5$ has $o(n^{3/2})$ edges. * Every subset of $[n]$ without a nontrivial solution to the equation $x_1 + x_2 + 2x_3 = x_4 + 3x_5$ has size $o(\sqrt{n})$., Comment: 23 pages

For a fixed graph $H$, what is the smallest number of colours $C$ such that there is a proper edge-colouring of the complete graph $K_n$ with $C$ colours containing no two vertex-disjoint colour-isomorphic copies, or repeats, of $H$? We study this function and its generalisation to more than two copies using a variety of combinatorial, probabilistic and algebraic techniques. For example, we show that for any tree $T$ there exists a constant $c$ such that any proper edge-colouring of $K_n$ with at most $c n^2$ colours contains two repeats of $T$, while there are colourings with at most $c' n^{3/2}$ colours for some absolute constant $c'$ containing no three repeats of any tree with at least two edges. We also show that for any graph $H$ containing a cycle there exist $k$ and $c$ such that there is a proper edge-colouring of $K_n$ with at most $c n$ colours containing no $k$ repeats of $H$, while, for a tree $T$ with $m$ edges, a colouring with $o(n^{(m+1)/m})$ colours contains $\omega(1)$ repeats of $T$.

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\H{o}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\'edi'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., Comment: 42 pages

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\H{o}s and S\'os 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\'{a}rk\"{o}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\'{a}rk\"{o}zy--Selkow bound, showing that $$ f(n, e + O(\log e/ \log\log e), e) = o(n^2). $$

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., Comment: 27 pages, subsumes arXiv:1901.05084

A well-known result of R\"odl and Ruci\'nski states that for any graph $H$ there exists a constant $C$ such that if $p \geq C n^{- 1/m_2(H)}$, then the random graph $G_{n,p}$ is a.a.s. $H$-Ramsey, that is, any $2$-colouring of its edges contains a monochromatic copy of $H$. Aside from a few simple exceptions, the corresponding $0$-statement also holds, that is, there exists $c>0$ such that whenever $p\leq cn^{-1/m_2(H)}$ the random graph $G_{n,p}$ is a.a.s. not $H$-Ramsey. We show that near this threshold, even when $G_{n,p}$ is not $H$-Ramsey, it is often extremely close to being $H$-Ramsey. More precisely, we prove that for any constant $c > 0$ and any strictly $2$-balanced graph $H$, if $p \geq c n^{-1/m_2(H)}$, then the random graph $G_{n,p}$ a.a.s. has the property that every $2$-edge-colouring without monochromatic copies of $H$ cannot be extended to an $H$-free colouring after $\omega(1)$ extra random edges are added. This generalises a result by Friedgut, Kohayakawa, R\"odl, Ruci\'nski and Tetali, who in 2002 proved the same statement for triangles, and addresses a question raised by those authors. We also extend a result of theirs on the three-colour case and show that these theorems need not hold when $H$ is not strictly $2$-balanced., Comment: 18 pages, 6 figures; to appear in Random Structures & Algorithms

A celebrated result of Mantel shows that every graph on $n$ vertices with $\lfloor n^2/4 \rfloor + 1$ edges must contain a triangle. A robust version of this result, due to Rademacher, says that there must in fact be at least $\lfloor n/2 \rfloor$ triangles in any such graph. Another strengthening, due to the combined efforts of many authors starting with Erd\H{o}s, says that any such graph must have an edge which is contained in at least $n/6$ triangles. Following Mubayi, we study the interplay between these two results, that is, between the number of triangles in such graphs and their book number, the largest number of triangles sharing an edge. Among other results, Mubayi showed that for any $1/6 \leq \beta < 1/4$ there is $\gamma > 0$ such that any graph on $n$ vertices with at least $\lfloor n^2/4\rfloor + 1$ edges and book number at most $\beta n$ contains at least $(\gamma -o(1))n^3$ triangles. He also asked for a more precise estimate for $\gamma$ in terms of $\beta$. We make a conjecture about this dependency and prove this conjecture for $\beta = 1/6$ and for $0.2495 \leq \beta < 1/4$, thereby answering Mubayi's question in these ranges., Comment: 15 pages

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) = \Theta(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\H{o}s and Simonovits, which asserts that every rational number $r \in (1,2)$ is realisable in the sense that $\mathrm{ex}(n,H) = \Theta(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 $\delta > 0$ such that $\mathrm{ex}(n,H^{k-1}) = O(n^{1 + 1/k - \delta})$, 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})$., Comment: 21 pages

We show that there is a positive constant $c$ such that any graph on vertex set $[n]$ with at most $c n^2/k^2 \log k$ edges contains an independent set of order $k$ whose vertices form an arithmetic progression. We also present applications of this result to several questions in Ramsey theory., Comment: 4 pages