We extend the Kechris–Pestov–Todorčević correspondence to weak Fraïssé categories and automorphism groups of generic objects. The new ingredient is the weak Ramsey property. We demonstrate the theory on several examples including monoid categories, the category of almost linear orders and categories of strong embeddings of trees.

A result of Gyárfás [12] exactly determines the size of a largest monochromatic component in an arbitrary $r$-colouring of the complete $k$-uniform hypergraph $K_n^k$ when $k\geq 2$ and $k\in \{r-1,r\}$. We prove a result which says that if one replaces $K_n^k$ in Gyárfás’ theorem by any ‘expansive’ $k$-uniform hypergraph on $n$ vertices (that is, a $k$-uniform hypergraph $G$ on $n$ vertices in which $e(V_1, \ldots, V_k)\gt 0$ for all disjoint sets $V_1, \ldots, V_k\subseteq V(G)$ with $|V_i|\gt \alpha$ for all $i\in [k]$), then one gets a largest monochromatic component of essentially the same size (within a small error term depending on $r$ and $\alpha$). As corollaries we recover a number of known results about large monochromatic components in random hypergraphs and random Steiner triple systems, often with drastically improved bounds on the error terms.

Gyárfás’ result is equivalent to the dual problem of determining the smallest possible maximum degree of an arbitrary $r$-partite $r$-uniform hypergraph $H$ with $n$ edges in which every set of $k$ edges has a common intersection. In this language, our result says that if one replaces the condition that every set of $k$ edges has a common intersection with the condition that for every collection of $k$ disjoint sets $E_1, \ldots, E_k\subseteq E(H)$ with $|E_i|\gt \alpha$, there exists $(e_1, \ldots, e_k)\in E_1\times \cdots \times E_k$ such that $e_1\cap \cdots \cap e_k\neq \emptyset$, then the smallest possible maximum degree of $H$ is essentially the same (within a small error term depending on $r$ and $\alpha$). We prove our results in this dual setting.

Resolving a problem of Conlon, Fox and Rödl, we construct a family of hypergraphs with arbitrarily large tower height separation between their $2$-colour and q-colour Ramsey numbers. The main lemma underlying this construction is a new variant of the Erdős–Hajnal stepping-up lemma for a generalized Ramsey number $r_k(t;q,p)$, which we define as the smallest integer n such that every q-colouring of the k-sets on n vertices contains a set of t vertices spanning fewer than p colours. Our results provide the first tower-type lower bounds on these numbers.

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.

Which patterns must a two-colouring of $K_n$ contain if each vertex has at least $\varepsilon n$ red and $\varepsilon n$ blue neighbours? We show that when $\varepsilon \gt 1/4$, $K_n$ must contain a complete subgraph on $\Omega (\log n)$ vertices where one of the colours forms a balanced complete bipartite graph.

When $\varepsilon \leq 1/4$, this statement is no longer true, as evidenced by the following colouring $\chi$ of $K_n$. Divide the vertex set into $4$ parts nearly equal in size as $V_1,V_2,V_3, V_4$, and let the blue colour class consist of the edges between $(V_1,V_2)$, $(V_2,V_3)$, $(V_3,V_4)$, and the edges contained inside $V_2$ and inside $V_3$. Surprisingly, we find that this obstruction is unique in the following sense. Any two-colouring of $K_n$ in which each vertex has at least $\varepsilon n$ red and $\varepsilon n$ blue neighbours (with $\varepsilon \gt 0$) contains a vertex set $S$ of order $\Omega _{\varepsilon }(\log n)$ on which one colour class forms a balanced complete bipartite graph, or which has the same colouring as $\chi$.

For a fixed infinite graph $H$, we study the largest density of a monochromatic subgraph isomorphic to $H$ that can be found in every two-colouring of the edges of $K_{\mathbb{N}}$. This is called the Ramsey upper density of $H$ and was introduced by Erdős and Galvin in a restricted setting, and by DeBiasio and McKenney in general. Recently [4], the Ramsey upper density of the infinite path was determined. Here, we find the value of this density for all locally finite graphs $H$ up to a factor of 2, answering a question of DeBiasio and McKenney. We also find the exact density for a wide class of bipartite graphs, including all locally finite forests. Our approach relates this problem to the solution of an optimisation problem for continuous functions. We show that, under certain conditions, the density depends only on the chromatic number of $H$, the number of components of $H$ and the expansion ratio $|N(I)|/|I|$ of the independent sets of $H$.

The Ramsey number $R(F,H)$ is the minimum number N such that any N-vertex graph either contains a copy of F or its complement contains H. Burr in 1981 proved a pleasingly general result that, for any graph H, provided n is sufficiently large, a natural lower bound construction gives the correct Ramsey number involving cycles: $R(C_n,H)=(n-1)(\chi (H)-1)+\sigma (H)$ , where $\sigma (H)$ is the minimum possible size of a colour class in a $\chi (H)$ -colouring of H. Allen, Brightwell and Skokan conjectured that the same should be true already when $n\geq \lvert H\rvert \chi (H)$ .

We improve this 40-year-old result of Burr by giving quantitative bounds of the form $n\geq C\lvert H\rvert \log ^4\chi (H)$ , which is optimal up to the logarithmic factor. In particular, this proves a strengthening of the Allen–Brightwell–Skokan conjecture for all graphs H with large chromatic number.

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 colourings are close to being $k$ -partite, while, for $c$ bounded away from $0$ , random colourings of an appropriate density are asymptotically optimal and all nearly-extremal colourings are quasirandom. Our investigations also open up a range of questions about what happens for intermediate values of $c$ .

A $(p,q)$ -colouring of a graph $G$ is an edge-colouring of $G$ which assigns at least $q$ colours to each $p$ -clique. The problem of determining the minimum number of colours, $f(n,p,q)$ , needed to give a $(p,q)$ -colouring of the complete graph $K_n$ is a natural generalization of the well-known problem of identifying the diagonal Ramsey numbers $r_k(p)$ . The best-known general upper bound on $f(n,p,q)$ was given by Erdős and Gyárfás in 1997 using a probabilistic argument. Since then, improved bounds in the cases where $p=q$ have been obtained only for $p\in \{4,5\}$ , each of which was proved by giving a deterministic construction which combined a $(p,p-1)$ -colouring using few colours with an algebraic colouring.

In this paper, we provide a framework for proving new upper bounds on $f(n,p,p)$ in the style of these earlier constructions. We characterize all colourings of $p$ -cliques with $p-1$ colours which can appear in our modified version of the $(p,p-1)$ -colouring of Conlon, Fox, Lee, and Sudakov. This allows us to greatly reduce the amount of case-checking required in identifying $(p,p)$ -colourings, which would otherwise make this problem intractable for large values of $p$ . In addition, we generalize our algebraic colouring from the $p=5$ setting and use this to give improved upper bounds on $f(n,6,6)$ and $f(n,8,8)$ .

In this paper, we study asymmetric Ramsey properties of the random graph $G_{n,p}$ . Let $r \in \mathbb{N}$ and $H_1, \ldots, H_r$ be graphs. We write $G_{n,p} \to (H_1, \ldots, H_r)$ to denote the property that whenever we colour the edges of $G_{n,p}$ with colours from the set $[r] \,{:\!=}\, \{1, \ldots, r\}$ there exists $i \in [r]$ and a copy of $H_i$ in $G_{n,p}$ monochromatic in colour $i$ . There has been much interest in determining the asymptotic threshold function for this property. In several papers, Rödl and Ruciński determined a threshold function for the general symmetric case; that is, when $H_1 = \cdots = H_r$ . A conjecture of Kohayakawa and Kreuter from 1997, if true, would fully resolve the asymmetric problem. Recently, the $1$ -statement of this conjecture was confirmed by Mousset, Nenadov and Samotij.

Building on work of Marciniszyn, Skokan, Spöhel and Steger from 2009, we reduce the $0$ -statement of Kohayakawa and Kreuter’s conjecture to a certain deterministic subproblem. To demonstrate the potential of this approach, we show this subproblem can be resolved for almost all pairs of regular graphs. This therefore resolves the $0$ -statement for all such pairs of graphs.

A graph $H$ is common if the number of monochromatic copies of $H$ in a 2-edge-colouring of the complete graph $K_n$ is asymptotically minimised by the random colouring. Burr and Rosta, extending a famous conjecture of Erdős, conjectured that every graph is common. The conjectures of Erdős and of Burr and Rosta were disproved by Thomason and by Sidorenko, respectively, in the late 1980s. Collecting new examples of common graphs had not seen much progress since then, although very recently a few more graphs were verified to be common by the flag algebra method or the recent progress on Sidorenko’s conjecture. Our contribution here is to provide several new classes of tripartite common graphs. The first example is the class of so-called triangle trees, which generalises two theorems by Sidorenko and answers a question of Jagger, Šťovíček, and Thomason from 1996. We also prove that, somewhat surprisingly, given any tree $T$ , there exists a triangle tree such that the graph obtained by adding $T$ as a pendant tree is still common. Furthermore, we show that adding arbitrarily many apex vertices to any connected bipartite graph on at most $5$ vertices yields a common graph.

A graph G arrows a graph H if in every 2-edge-colouring of G there exists a monochromatic copy of H. Schelp had the idea that if the complete graph $K_n$ arrows a small graph H, then every ‘dense’ subgraph of $K_n$ also arrows H, and he outlined some problems in this direction. Our main result is in this spirit. We prove that for every sufficiently large n, if $n = 3t+r$ where $r \in \{0,1,2\}$ and G is an n-vertex graph with $\delta(G) \ge (3n-1)/4$ , then for every 2-edge-colouring of G, either there are cycles of every length $\{3, 4, 5, \dots, 2t+r\}$ of the same colour, or there are cycles of every even length $\{4, 6, 8, \dots, 2t+2\}$ of the samecolour.

Our result is tight in the sense that no longer cycles (of length $>2t+r$ ) can be guaranteed and the minimum degree condition cannot be reduced. It also implies the conjecture of Schelp that for every sufficiently large n, every $(3t-1)$ -vertex graph G with minimum degree larger than $3|V(G)|/4$ arrows the path $P_{2n}$ with 2n vertices. Moreover, it implies for sufficiently large n the conjecture by Benevides, Łuczak, Scott, Skokan and White that for $n=3t+r$ where $r \in \{0,1,2\}$ and every n-vertex graph G with $\delta(G) \ge 3n/4$ , in each 2-edge-colouring of G there exists a monochromatic cycle of length at least $2t+r$ .

Erdős asked if, for every pair of positive integers g and k, there exists a graph H having girth (H) = k and the property that every r-colouring of the edges of H yields a monochromatic cycle Ck. The existence of such graphs H was confirmed by the third author and Ruciński.

We consider the related numerical problem of estimating the order of the smallest graph H with this property for given integers r and k. We show that there exists a graph H on R10k2; k15k3 vertices (where R = R(Ck; r) is the r-colour Ramsey number for the cycle Ck) having girth (H) = k and the Ramsey property that every r-colouring of the edges of H yields a monochromatic Ck Two related numerical problems regarding arithmetic progressions in subsets of the integers and cliques in graphs are also considered.

We prove that if an $\omega $ -categorical structure has an $\omega $ -categorical homogeneous Ramsey expansion, then so does its model-complete core.

We investigate the uniform computational content of the open and clopen Ramsey theorems in the Weihrauch lattice. While they are known to be equivalent to $\mathrm {ATR_0}$ from the point of view of reverse mathematics, there is not a canonical way to phrase them as multivalued functions. We identify eight different multivalued functions (five corresponding to the open Ramsey theorem and three corresponding to the clopen Ramsey theorem) and study their degree from the point of view of Weihrauch, strong Weihrauch, and arithmetic Weihrauch reducibility. In particular one of our functions turns out to be strictly stronger than any previously studied multivalued functions arising from statements around $\mathrm {ATR}_0$ .

We prove that if the set of unordered pairs of real numbers is coloured by finitely many colours, there is a set of reals homeomorphic to the rationals whose pairs have at most two colours. Our proof uses large cardinals and verifies a conjecture of Galvin from the 1970s. We extend this result to an essentially optimal class of topological spaces in place of the reals.

We give an example of two ordered structures $\mathcal {M},\mathcal {N}$ in the same language $\mathcal {L}$ with the same universe, the same order and admitting the same one-variable definable subsets such that $\mathcal {M}$ is a model of the common theory of o-minimal $\mathcal {L}$ -structures and $\mathcal {N}$ admits a definable, closed, bounded, and discrete subset and a definable injective self-mapping of that subset which is not surjective. This answers negatively two question by Schoutens; the first being whether there is an axiomatization of the common theory of o-minimal structures in a given language by conditions on one-variable definable sets alone. The second being whether definable completeness and type completeness imply the pigeonhole principle. It also partially answers a question by Fornasiero asking whether definable completeness of an expansion of a real closed field implies the pigeonhole principle.

Henle, Mathias, and Woodin proved in [21] that, provided that ${\omega }{\rightarrow }({\omega })^{{\omega }}$ holds in a model M of ZF, then forcing with $([{\omega }]^{{\omega }},{\subseteq }^*)$ over M adds no new sets of ordinals, thus earning the name a “barren” extension. Moreover, under an additional assumption, they proved that this generic extension preserves all strong partition cardinals. This forcing thus produces a model $M[\mathcal {U}]$ , where $\mathcal {U}$ is a Ramsey ultrafilter, with many properties of the original model M. This begged the question of how important the Ramseyness of $\mathcal {U}$ is for these results. In this paper, we show that several classes of $\sigma $ -closed forcings which generate non-Ramsey ultrafilters have the same properties. Such ultrafilters include Milliken–Taylor ultrafilters, a class of rapid p-points of Laflamme, k-arrow p-points of Baumgartner and Taylor, and extensions to a class of ultrafilters constructed by Dobrinen, Mijares, and Trujillo. Furthermore, the class of Boolean algebras $\mathcal {P}({\omega }^{{\alpha }})/{\mathrm {Fin}}^{\otimes {\alpha }}$ , $2\le {\alpha }<{\omega }_1$ , forcing non-p-points also produce barren extensions.

Several discrete geometry problems are equivalent to estimating the size of the largest homogeneous sets in graphs that happen to be the union of few comparability graphs. An important observation for such results is that if G is an n-vertex graph that is the union of r comparability (or more generally, perfect) graphs, then either G or its complement contains a clique of size $n^{1/(r+1)}$ .

This bound is known to be tight for $r=1$ . The question whether it is optimal for $r\ge 2$ was studied by Dumitrescu and Tóth. We prove that it is essentially best possible for $r=2$ , as well: we introduce a probabilistic construction of two comparability graphs on n vertices, whose union contains no clique or independent set of size $n^{1/3+o(1)}$ .

Using similar ideas, we can also construct a graph G that is the union of r comparability graphs, and neither G nor its complement contain a complete bipartite graph with parts of size $cn/{(log n)^r}$ . With this, we improve a result of Fox and Pach.