We prove that any bounded degree regular graph with sufficiently strong spectral expansion contains an induced path of linear length. This is the first such result for expanders, strengthening an analogous result in the random setting by Draganić, Glock, and Krivelevich. More generally, we find long induced paths in sparse graphs that satisfy a mild upper-uniformity edge-distribution condition.

Daisies are a special type of hypergraph introduced by Bollobás, Leader and Malvenuto. An $r$-daisy determined by a pair of disjoint sets $K$ and $M$ is the $(r+|K|)$-uniform hypergraph $\{K\cup P\,{:}\, P\in M^{(r)}\}$. Bollobás, Leader and Malvenuto initiated the study of Turán type density problems for daisies. This paper deals with Ramsey numbers of daisies, which are natural generalisations of classical Ramsey numbers. We discuss upper and lower bounds for the Ramsey number of $r$-daisies and also for special cases where the size of the kernel is bounded.

A $(k+r)$-uniform hypergraph $H$ on $(k+m)$ vertices is an $(r,m,k)$-daisy if there exists a partition of the vertices $V(H)=K\cup M$ with $|K|=k$, $|M|=m$ such that the set of edges of $H$ is all the $(k+r)$-tuples $K\cup P$, where $P$ is an $r$-tuple of $M$. We obtain an $(r-2)$-iterated exponential lower bound to the Ramsey number of an $(r,m,k)$-daisy for $2$-colours. This matches the order of magnitude of the best lower bounds for the Ramsey number of a complete $r$-graph.

We prove that any strongly mixing action of a countable abelian group on a probability space has higher-order mixing properties. This is achieved via the utilization of $\mathcal R$-limits, a notion of convergence which is based on the classical Ramsey theorem. $\mathcal R$-limits are intrinsically connected with a new combinatorial notion of largeness which is similar to but has stronger properties than the classical notions of uniform density one and IP$^*$. While the main goal of this paper is to establish a universal property of strongly mixing actions of countable abelian groups, our results, when applied to ${\mathbb {Z}}$-actions, offer a new way of dealing with strongly mixing transformations. In particular, we obtain several new characterizations of strong mixing for ${\mathbb {Z}}$-actions, including a result which can be viewed as the analogue of the weak mixing of all orders property established by Furstenberg in the course of his proof of Szemerédi’s theorem. We also demonstrate the versatility of $\mathcal R$-limits by obtaining new characterizations of higher-order weak and mild mixing for actions of countable abelian groups.

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 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$ .

We analyze the axiomatic strength of the following theorem due to Rival and Sands [28] in the style of reverse mathematics. Every infinite partial order P of finite width contains an infinite chain C such that every element of P is either comparable with no element of C or with infinitely many elements of C. Our main results are the following. The Rival–Sands theorem for infinite partial orders of arbitrary finite width is equivalent to $\mathsf {I}\Sigma ^0_{2} + \mathsf {ADS}$ over $\mathsf {RCA}_0$. For each fixed $k \geq 3$, the Rival–Sands theorem for infinite partial orders of width $\leq \!k$ is equivalent to $\mathsf {ADS}$ over $\mathsf {RCA}_0$. The Rival–Sands theorem for infinite partial orders that are decomposable into the union of two chains is equivalent to $\mathsf {SADS}$ over $\mathsf {RCA}_0$. Here $\mathsf {RCA}_0$ denotes the recursive comprehension axiomatic system, $\mathsf {I}\Sigma ^0_{2}$ denotes the $\Sigma ^0_2$ induction scheme, $\mathsf {ADS}$ denotes the ascending/descending sequence principle, and $\mathsf {SADS}$ denotes the stable ascending/descending sequence principle. To the best of our knowledge, these versions of the Rival–Sands theorem for partial orders are the first examples of theorems from the general mathematics literature whose strength is exactly characterized by $\mathsf {I}\Sigma ^0_{2} + \mathsf {ADS}$, by $\mathsf {ADS}$, and by $\mathsf {SADS}$. Furthermore, we give a new purely combinatorial result by extending the Rival–Sands theorem to infinite partial orders that do not have infinite antichains, and we show that this extension is equivalent to arithmetical comprehension over $\mathsf {RCA}_0$.

An old conjecture of Erdős and McKay states that if all homogeneous sets in an $n$ -vertex graph are of order $O(\!\log n)$ then the graph contains induced subgraphs of each size from $\{0,1,\ldots, \Omega \big(n^2\big)\}$ . We prove a bipartite analogue of the conjecture: if all balanced homogeneous sets in an $n \times n$ bipartite graph are of order $O(\!\log n)$ , then the graph contains induced subgraphs of each size from $\{0,1,\ldots, \Omega \big(n^2\big)\}$ .

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.

Let $\mathrm{AP}_k=\{a,a+d,\ldots,a+(k-1)d\}$ be an arithmetic progression. For $\varepsilon>0$ we call a set $\mathrm{AP}_k(\varepsilon)=\{x_0,\ldots,x_{k-1}\}$ an $\varepsilon$ -approximate arithmetic progression if for some a and d, $|x_i-(a+id)|<\varepsilon d$ holds for all $i\in\{0,1\ldots,k-1\}$ . Complementing earlier results of Dumitrescu (2011, J. Comput. Geom.2(1) 16–29), in this paper we study numerical aspects of Van der Waerden, Szemerédi and Furstenberg–Katznelson like results in which arithmetic progressions and their higher dimensional extensions are replaced by their $\varepsilon$ -approximation.

A strong coloring on a cardinal $\kappa $ is a function $f:[\kappa ]^2\to \kappa $ such that for every $A\subseteq \kappa $ of full size $\kappa $ , every color $\unicode{x3b3} <\kappa $ is attained by $f\restriction [A]^2$ . The symbol

$$ \begin{align*} \kappa\nrightarrow[\kappa]^2_{\kappa} \end{align*} $$

$\kappa $

We introduce the symbol

$$ \begin{align*} \kappa\nrightarrow_p[\kappa]^2_{\kappa} \end{align*} $$

$f:[\kappa ]^2\to \kappa $

$p:[\kappa ]^2\to \theta $

$A\in [\kappa ]^{\kappa }$

$i<\theta $

$\unicode{x3b3} <\kappa $

$f\restriction ([A]^2\cap p^{-1}(i))$

We prove that whenever $\kappa \nrightarrow [\kappa ]^2_{\kappa }$ holds, also $\kappa \nrightarrow _p[\kappa ]^2_{\kappa }$ holds for an arbitrary finite partition p. Similarly, arbitrary finite p-s can be added to stronger symbols which hold in any model of ZFC. If $\kappa ^{\theta }=\kappa $ , then $\kappa \nrightarrow _p[\kappa ]^2_{\kappa }$ and stronger symbols, like $\operatorname {Pr}_1(\kappa ,\kappa ,\kappa ,\chi )_p$ or $\operatorname {Pr}_0(\kappa ,\kappa ,\kappa ,\aleph _0)_p$ , also hold for an arbitrary partition p to $\theta $ parts.

The symbols

$$ \begin{gather*} \aleph_1\nrightarrow_p[\aleph_1]^2_{\aleph_1},\;\;\; \aleph_1\nrightarrow_p[\aleph_1\circledast \aleph_1]^2_{\aleph_1},\;\;\; \aleph_0\circledast\aleph_1\nrightarrow_p[1\circledast\aleph_1]^2_{\aleph_1}, \\ \operatorname{Pr}_1(\aleph_1,\aleph_1,\aleph_1,\aleph_0)_p,\;\;\;\text{ and } \;\;\; \operatorname{Pr}_0(\aleph_1,\aleph_1,\aleph_1,\aleph_0)_p \end{gather*} $$

$+ \neg $

We use the model theoretic notion of coheir to give short proofs of old and new theorems in Ramsey Theory. As an illustration we start from Ramsey’s theorem itself. Then we prove Hindman’s theorem and the Hales–Jewett theorem. Finally, we prove two Ramsey theoretic principles that have among their consequences partition theorems due to Carlson and to Gowers.

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.

We investigate the effects of various forcings on several forms of the Halpern– Läuchli theorem. For inaccessible κ, we show they are preserved by forcings of size less than κ. Combining this with work of Zhang in [17] yields that the polarized partition relations associated with finite products of the κ-rationals are preserved by all forcings of size less than κ over models satisfying the Halpern– Läuchli theorem at κ. We also show that the Halpern–Läuchli theorem is preserved by <κ-closed forcings assuming κ is measurable, following some observed reflection properties.

We consider maximal almost disjoint families of block subspaces of countable vector spaces, focusing on questions of their size and definability. We prove that the minimum infinite cardinality of such a family cannot be decided in ZFC and that the “spectrum” of cardinalities of mad families of subspaces can be made arbitrarily large, in analogy to results for mad families on ω. We apply the author’s local Ramsey theory for vector spaces [32] to give partial results concerning their definability.

The classical Halpern–Läuchli theorem states that for any finite coloring of a finite product of finitely branching perfect trees of height ω, there exist strong subtrees sharing the same level set such that tuples in the product of the strong subtrees consisting of elements lying on the same level get the same color. Relative to large cardinals, we establish the consistency of a tail cone version of the Halpern–Läuchli theorem at a large cardinal (see Theorem 3.1), which, roughly speaking, deals with many colorings simultaneously and diagonally. Among other applications, we generalize a polarized partition relation on rational numbers due to Laver and Galvin to one on linear orders of larger saturation.