9 solved out of 34 shown

Let $k\geq 2$. Is there an integer $n_k$ such that, if $D=\{ 1<d<n_k : d\mid n_k\}$, then for any $k$-colouring of $D$ there is a monochromatic subset $D'\subseteq D$ such that $\sum_{d\in D'}\frac{1}{d}=1$?

This follows from the colouring result of Croot [Cr03]. Obtaining better quantitative aspects seems interesting still -- note that Croot's result allows for $n_k \leq e^{C^k}$ for some constant $C>1$. Is there a better bound?

$100

A set of integers $A$ is Ramsey $2$-complete if, whenever $A$ is $2$-coloured, all sufficiently large integers can be written as a monochromatic sum of elements of $A$. It is known that it cannot be true that
\[\lvert A\cap \{1,\ldots,N\}\rvert \ll (\log N)^2\]
for all large $N$ and that there exists a Ramsey $2$-complete $A$ such that for all large $N$
\[\lvert A\cap \{1,\ldots,N\}\rvert < (2\log_2N)^3.\]
Improve either of these bounds.

The stated bounds are due to Burr and Erdős [BuEr85].

$250

A set of integers $A$ is Ramsey $r$-complete if, whenever $A$ is $r$-coloured, all sufficiently large integers can be written as a monochromatic sum of elements of $A$. Prove any non-trivial bounds about the growth rate of such an $A$ for $r>2$.

A paper of Burr and Erdős [BuEr85] proves both upper and lower bounds for $r=2$, showing that there exists some $c>0$ such that it cannot be true that
\[\lvert A\cap \{1,\ldots,N\}\rvert \leq c(\log N)^2\]
for all large $N$, and also constructing a Ramsey $2$-complete $A$ such that for all large $N$
\[\lvert A\cap \{1,\ldots,N\}\rvert \ll (\log N)^3.\]
Burr has shown that the sequence of $k$th powers is Ramsey $r$-complete for every $r,k\geq 1$.

Solved by Conlon, Fox, and Pham [CFP21], who constructed for every $r\geq 2$ an $r$-Ramsey complete $A$ such that for all large $N$ \[\lvert A\cap \{1,\ldots,N\}\rvert \ll r(\log N)^2,\] and showed that this is best possible, in that there exists some constant $c>0$ such that if $A\subset \mathbb{N}$ satisfies \[\lvert A\cap \{1,\ldots,N\}\rvert \leq cr(\log N)^2\] for all large $N$ then $A$ cannot be $r$-Ramsey complete.

Is it true that in any $2$-colouring of the edges of $K_n$ there must exist at least
\[(1+o(1))\frac{n^2}{12}\]
many edge-disjoint monochromatic triangles?

Conjectured by Erdős, Faudreee, and Ordman. This would be best possible, as witnessed by dividing the vertices of $K_n$ into two equal parts and colouring all edges between the parts red and all edges inside the parts blue.

The answer is yes, proved by Gruslys and Letzter [GrLe20].

Erdős offers \$100 for just a proof of the existence of this constant, without determining its value. He also offers \$1000 for a proof that the limit does not exist, but says 'this is really a joke as [it] certainly exists'. Erdős proved
\[\sqrt{2}\leq \liminf_{k\to \infty}R(k)^{1/k}\leq \limsup_{k\to \infty}R(k)^{1/k}\leq 4.\]
The upper bound has been improved to $4-\tfrac{1}{128}$ by Campos, Griffiths, Morris, and Sahasrabudhe [CaGrMoSa23].

Erdős gave a simple probabilistic proof that $R(k) \gg k2^{k/2}$.
Equivalently, this question asks for an explicit construction of a graph on $n$ vertices which does not contain any clique or independent set of size $\geq c\log n$ for some constant $c>0$. Cohen [Co15] (see the introduction for further history) constructed a graph on $n$ vertices which does not contain any clique or independent set of size
\[\geq 2^{(\log\log n)^{C}}\]
for some constant $C>0$. Li [Li23b] has recently improved this to
\[\geq (\log n)^{C}\]
for some constant $C>0$.

We say $G$ is Ramsey size linear if $R(G,H)\ll e(H)$ for all graphs $H$ with no isolated vertices. Are there infinitely many graphs $G$ which are not Ramsey size linear but such that all of its subgraphs are?

Asked by Erdős, Faudree, Rousseau, and Schelp [ErFaRoSc93]. $K_4$ is the only known example of such a graph.

In other words, is $K_{3,3}$ Ramsey size linear? Asked by Erdős, Faudree, Rousseau, and Schelp [ErFaRoSc93].

Let $G$ be a graph on $n$ vertices with no induced cycles of length greater than $3$. Can the edges of $G$ be partitioned into $n^2/6+O(n)$ many cliques?

Asked by Erdős, Ordman, and Zalcstein [ErOrZa93], who proved an upper bound of $(1/4-\epsilon)n^2$ many cliques (for some very small $\epsilon>0$).

Let $\epsilon >0$. Is it true that, if $k$ is sufficiently large, then
\[R(G)>(1-\epsilon)^kR(k)\]
for every graph $G$ with chromatic number $\chi(G)=k$?

Even stronger, is there some $c>0$ such that, for all large $k$, $R(G)>cR(k)$ for every graph $G$ with chromatic number $\chi(G)=k$?

Erdős originally conjectured that $R(G)\geq R(k)$, which is trivial for $k=3$, but fails already for $k=4$.

Since $R(k)\leq 4^k$ this is trivial for $\epsilon\geq 1/4$. Yuval Wigderson points out that $R(G)\gg 2^{k/2}$ for any $G$ with chromatic number $k$ (via a random colouring), which asymptotically matches the best-known lower bounds for $R(k)$.

$100

For any $\epsilon>0$ there exists $\delta=\delta(\epsilon)>0$ such that if $G$ is a graph on $n$ vertices with no independent set or clique of size $\geq \epsilon\log n$ then $G$ contains an induced subgraph with $m$ edges for all $m\leq \delta n^2$.

Conjectured by Erdős and McKay, who proved it with $\delta n^2$ replaced by $\delta (\log n)^2$. Solved by Kwan, Sah, Sauermann, and Sawhney [KSSS22]. Erdős' original formulation also had the condition that $G$ has $\gg n^2$ edges, but an old result of Erdős and Szemerédi says that this follows from the other condition anyway.

Let $\alpha$ be a cardinal or ordinal number or an order type such that every two-colouring of $K_\alpha$ contains either a red $K_\alpha$ or a blue $K_3$. For every $n\geq 3$ must every two-colouring of $K_\alpha$ contains either a red $K_\alpha$ or a blue $K_n$?

Conjectured by Erdős and Hajnal.

Let $R(n;k,r)$ be the smallest $N$ such that if the edges of $K_N$ are $r$-coloured then there is a set of $n$ vertices which does not contain a copy of $K_k$ in at least one of the $r$ colours. Prove that there is a constant $C=C(r)>1$ such that
\[R(n;3,r) < C^{\sqrt{n}}.\]

Conjectured by Erdős and Gyárfás, who proved the existence of some $C>1$ such that $R(n;3,r)>C^{\sqrt{n}}$. Note that when $r=k=2$ we recover the classic Ramsey numbers. It is likely that for all $r,k\geq 2$ there exists some $C_1,C_2>1$ (depending only on $r$) such that
\[ C_1^{n^{1/k-1}}< R(n;k,r) < C_2^{n^{1/k-1}}.\]
Antonio Girao has pointed out that this problem as written is easily disproved: the obvious probabilistic construction (randomly colour the edges red/blue independently uniformly at random) yields a 2-colouring of the edges of $K_N$ such every set on $n$ vertices contains a red triangle and a blue triangle (using that every set of $n$ vertices contains $\gg n^2$ edge-disjoint triangles), as soon as $N \geq C^n$ for some absolute constant $C>1$. This implies $R(n;3,2) \geq C^{n}$, contradicting the conjecture. Perhaps Erdős had a different problem in mind, but it is not clear what that might be. It would presumably be one where the natural probabilistic argument would deliver a bound like $C^{\sqrt{n}}$ as Erdős and Gyárfás claim to have achieved via the probabilistic method.

The current bounds are
\[ \frac{n^{3/2}}{(\log n)^{3/2}}\ll R(C_4,K_n)\ll \frac{n^2}{(\log n)^2}.\]
The upper bound is due to Szemerédi (mentioned in [ErFaRoSc78]), and the lower bound is due to Spencer [Sp77].

$500

Let $\alpha>0$ and $n,t\geq 1$ be integers. Let $F^{(t)}(n,\alpha)$ be the largest $k$ such that the following holds.

Let $\lvert S\rvert=n$ and 2-colour all $t$-subsets of $S$. For every $X\subseteq S$ of size at least $k$ there are at least $\alpha \binom{\lvert X\rvert}{t}$ many $t$-subsets of $X$ of each colour.

For fixed $n,t$ as we change $\alpha$ from $0$ to $1/2$ does $F^{(t)}(n,\alpha)$ increase continuously or are there jumps? Only one jump?

For $\alpha=0$ this is the usual Ramsey function. A conjecture of Erdős, Rado, and Hajnal implies that
\[ F^{(t)}(n,0)\asymp \log_{t-1} n\]
and results of Erdős and Spencer imply that
\[F^{(t)}(n,\alpha) \asymp_\alpha (\log n)^{\frac{1}{t-1}}\]
for $\alpha$ close to $1/2$.

Let $\alpha>0$ and $n\geq 1$. Let $F(n,\alpha)$ be the largest $k$ such that in any 2-colouring of the edges of $K_n$ any subgraph $H$ on at least $k$ vertices contains more than $\alpha\binom{\lvert H\rvert}{2}$ many edges of each colour.

Prove that for every fixed $0\leq \alpha \leq 1/2$, as $n\to\infty$, \[F(n,\alpha)\sim c_\alpha \log n\] for some constant $c_\alpha$.

It is easy to show with the probabilistic method that there exist $c_1(\alpha),c_2(\alpha)$ such that
\[c_1(\alpha)\log n < F(n,\alpha) < c_2(\alpha)\log n.\]

For any $d\geq 1$ if $H$ is a graph such that every subgraph contains a vertex of degree at most $d$ then $R(H)\ll_d n$.

The Burr-Erdős conjecture. Solved by Lee [Le16], who proved that
\[ R(H) \leq 2^{2^{O(d)}}n.\]

It is known that there exists some constant $c>0$ such that for large $k$
\[c\frac{k^2}{\log k}\leq R(3,k) \leq (1+o(1))\frac{k^2}{\log k}.\]
The lower bound is due to Kim [Ki95], the upper bound is due to Shearer [Sh83], improving an earlier bound of Ajtai, Komlós, and Szemerédi [AjKoSz80]. The lower bound has been improved to
\[\left(\frac{1}{4}-o(1)\right)\frac{k^2}{\log k}\]
independently by Bohman and Keevash [BoKe21] and Pontiveros, Griffiths and Morris [PGM20]. The latter collection of authors conjecture that this lower bound is the true order of magnitude.

Spencer [Sp77] proved
\[R(4,k) \gg (k\log k)^{5/2}.\]
Ajtai, Komlós, and Szemerédi [AjKoSz80] proved
\[R(4,k) \ll \frac{k^3}{(\log k)^2}.\]
This is true, and was proved by Mattheus and Verstraete [MaVe23], who showed that
\[R(4,k) \gg \frac{k^3}{(\log k)^4}.\]

Estimate the hypergraph Ramsey number $R_r(k)$. Does it grow like
\[2^{2^{\cdots k}}\]
where the tower of exponentials has height $r-1$?

Erdős, Hajnal, and Rado proved that $R_r(k)$ grows like a tower of exponentials of height at least $r-2$ and at most $r-1$. Hajnal has proved that $r-1$ is the correct height if we consider the corresponding hypergraph Ramsey number for $4$ colours.

Is it true that in any finite colouring of $\mathbb{N}$ there exist arbitrarily large finite $A$ such that all sums and products of distinct elements in $A$ are the same colour?

First asked by Hindman. Hindman [Hi80] has proved this is false (with 7 colours) if we ask for an infinite $A$.

Moreira [Mo17] has proved that in any finite colouring of $\mathbb{N}$ there exist $x,y$ such that $\{x,x+y,xy\}$ are all the same colour.

Alweiss [Al23] has proved that, in any finite colouring of $\mathbb{Q}\backslash \{0\}$ there exist arbitrarily large finite $A$ such that all sums and products of distinct elements in $A$ are the same colour. Bowen and Sabok [BoSa22] had proved this earlier for the first non-trivial case of $\lvert A\rvert=2$.

In any $2$-colouring of $\mathbb{R}^2$, for all but at most one triangle $T$, there is a monochromatic congruent copy of $T$.

For some colourings a single equilateral triangle has to be excluded, considering the colouring by alternating strips. Shader [Sh76] has proved this is true if we just consider a single right-angled triangle.

A finite set $A\subset \mathbb{R}^n$ is called Ramsey if, for any $k\geq 1$, there exists some $d=d(A,k)$ such that in any $k$-colouring of $\mathbb{R}^d$ there exists a monochromatic copy of $A$. Characterise the Ramsey sets in $\mathbb{R}^n$.

Erdős, Graham, Montgomery, Rothschild, Spencer, and Straus [EGMRSS73] proved that every Ramsey set is 'spherical': it lies on the surface of some sphere. Graham has conjectured that every spherical set is Ramsey. Leader, Russell, and Walters [LRW12] have alternatively conjectured that a set is Ramsey if and only if it is 'subtransitive': it can be embedded in some higher-dimensional set on which rotations act transitively.

Sets known to be Ramsey include vertices of $k$-dimensional rectangles [EGMRSS73], non-degenerate simplices [FrRo90], trapezoids [Kr92], and regular polygons/polyhedra [Kr91].

Let $Q_n$ be the $n$-dimensional hypercube graph (so that $Q_n$ has $2^n$ vertices and $n2^{n-1}$ edges). Prove that
\[R(Q_n) \ll 2^n.\]

Conjectured by Burr and Erdős. The trivial bound is
\[R(Q_n) \leq R(K_{2^n})\leq C^{2^n}\]
for some constant $C>1$. This was improved a number of times; the current best bound due to Tikhomirov [Ti22] is
\[R(Q_n)\ll 2^{(2-c)n}\]
for some small constant $c>0$. (In fact $c\approx 0.03656$ is permissible.)

$250

Let $R(3;k)$ be the minimal $n$ such that if the edges of $K_n$ are coloured with $k$ colours then there must exist a monochromatic triangle. Determine
\[\lim_{k\to \infty}R(3;k)^{1/k}.\]

Erdős offers \$100 for showing that this limit is finite. An easy pigeonhole argument shows that
\[R(3;k)\leq 2+k(R(3;k-1)-1),\]
from which $R(3;k)\leq \lceil e k!\rceil$ immediately follows. The best-known upper bounds are all of the form $ck!+O(1)$, and arise from this type of inductive relationship and computational bounds for $R(3;k)$ for small $k$. The best-known lower bound (coming from lower bounds for Schur numbers) is due to Exoo [Ex94],
\[R(3;k) \gg (321)^{k/5}.\]

See also [483].

Find the best function $f(d)$ such that, in any 2-colouring of the integers, at least one colour class contains an arithmetic progression with common difference $d$ of length $f(d)$ for infinitely many $d$.

Originally asked by Cohen. Erdős observed that colouring according to whether $\{ \sqrt{2}n\}<1/2$ or not implies $f(d) \ll d$. Beck [Be80] has improved this using the probabilistic method, constructing a colouring that shows $f(d)\leq (1+o(1))\log_2 d$. Van der Waerden's theorem implies $f(d)\to \infty$ is necessary.

What is the smallest $k$ such that $\mathbb{R}^2$ can be red/blue coloured with no pair of red points unit distance apart, and no $k$-term arithmetic progression of blue points?

Juhász [Ju79] has shown that $k\geq 5$. It is also known that $k\leq 10000000$ (as Erdős writes, 'more or less').

If $\mathbb{R}^2$ is finitely coloured then must there exist some colour class which contains the vertices of a rectangle of every area?

Graham [Gr80] has shown that this is true if we replace rectangle by right-angled triangle. The same question can be asked for parallelograms. It is not true for rhombuses.

This is false; Kovač [Ko23] provides an explicit (and elegantly simple) colouring using 25 colours such that no colour class contains the vertices of a rectangle of area $1$. The question for parallelograms remains open.

Let $C>0$ be arbitrary. Is it true that, if $n$ is sufficiently large depending on $C$, then in any $2$-colouring of $\binom{\{2,\ldots,n\}}{2}$ there exists some $X\subset \{2,\ldots,n\}$ such that $\binom{X}{2}$ is monochromatic and
\[\sum_{x\in X}\frac{1}{\log x}\geq C?\]

The answer is yes, which was proved by Rödl [Ro03].

In the same article Rödl also proved a lower bound for this problem, constructing, for all $n$, a $2$-colouring of $\binom{\{2,\ldots,n\}}{2}$ such that if $X\subseteq \{2,\ldots,n\}$ is such that $\binom{X}{2}$ is monochromatic then \[\sum_{x\in X}\frac{1}{\log x}\ll \log\log\log n.\]

This bound is best possible, as proved by Conlon, Fox, and Sudakov [CFS13], who proved that, if $n$ is sufficiently large, then in any $2$-colouring of $\binom{\{2,\ldots,n\}}{2}$ there exists some $X\subset \{2,\ldots,n\}$ such that $\binom{X}{2}$ is monochromatic and \[\sum_{x\in X}\frac{1}{\log x}\geq 2^{-8}\log\log\log n.\]

Is there some $c>0$ such that every measurable $A\subseteq \mathbb{R}^2$ of measure $\geq c$ contains the vertices of a triangle of area 1?

Erdős (unpublished) proved that this is true if $A$ has infinite measure, or if $A$ is an unbounded set of positive measure.

Let $A\subseteq \mathbb{R}^2$ be a measurable set with infinite measure. Must $A$ contain the vertices of an isosceles trapezoid of area $1$?

Erdős and Mauldin (unpublished) claim that this is true for trapezoids in general, but fails for parallelograms.

Prove that there exists an absolute constant $c>0$ such that, whenever $\{1,\ldots,N\}$ is $k$-coloured (and $N$ is large enough depending on $k$) then there are at least $cN$ many integers in $\{1,\ldots,N\}$ which are representable as a monochromatic sum (that is, $a+b$ where $a,b\in \{1,\ldots,N\}$ are in the same colour class).

A conjecture of Roth.