23 solved out of 71 shown (show only solved or open)
SOLVED
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]. Croot's result allows for $n_k \leq e^{C^k}$ for some constant $C>1$ (simply taking $n_k$ to be the lowest common multiple of some interval $[1,C^k]$). Sawhney has observed that there is also a doubly exponential lower bound, and hence this bound is essentially sharp.

Indeed, we must trivially have $\sum_{d|n_k}1/d \geq k$, or else there is a greedy colouring as a counterexample. Since $\prod_{p}(1+1/p^2)$ is finite we must have $\prod_{p|n_k}(1+1/p)\gg k$. To achieve the minimal $\prod_{p|n_k}p$ we take the product of primes up to $T$ where $\prod_{p\leq T}(1+1/p)\gg k$; by Mertens theorems this implies $T\geq C^{k}$ for some constant $C>1$, and hence $n_k\geq \prod_{p\mid n_k}p\geq \exp(cC^k)$ for some $c>0$.

SOLVED
Does every finite colouring of the integers have a monochromatic solution to $1=\sum \frac{1}{n_i}$ with $2\leq n_1<\cdots <n_k$?
The answer is yes, as proved by Croot [Cr03].
SOLVED - $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$. Burr and Erdős [BuEr85] showed that there exists a constant$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 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]. Resolved by Conlon, Fox, and Pham [CFP21], who constructed a Ramsey$2$-complete$A$such that $\lvert A\cap \{1,\ldots,N\}\rvert \ll (\log N)^2$ for all large$N$. See also [55]. SOLVED -$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.

OPEN
Let $\mathfrak{c}$ be the ordinal of the real numbers, $\beta$ be any countable ordinal, and $2\leq n<\omega$. Is it true that $\mathfrak{c}\to (\beta, n)_2^3$?
Erdős and Rado proved that $\mathfrak{c}\to (\omega+n,4)_2^3$ for any $2\leq n<\omega$.
SOLVED
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].

OPEN - $250 Find the value of$\lim_{k\to \infty}R(k)^{1/k}$. Erdős offered \$100 for just a proof of the existence of this constant, without determining its value. He also offered \$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 [CGMS23]. OPEN -$100
Give a constructive proof that $R(k)>C^k$ for some constant $C>1$.
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$.
Additional thanks to: Jesse Goodman, Mehtaab Sawhney
OPEN
We say $G$ is Ramsey size linear if $R(G,H)\ll m$ for all graphs $H$ with $m$ edges and 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 [EFRS93]. $K_4$ is the only known example of such a graph.
OPEN
Let $c>0$ and let $f_c(n)$ be the maximal $m$ such that every graph $G$ with $n$ vertices and at least $cn^2$ edges, where each edge is contained in at least one triangle, must contain an edge in at least $m$ different triangles. Estimate $f_c(n)$. In particular, is it true that $f_c(n)>n^{\epsilon}$ for some $\epsilon>0$? Or even $f_c(n)\gg \log n$?
A problem of Erdős and Rothschild. Alon and Trotter showed that $f_c(n)\ll_c n^{1/2}$. Szemerédi observed that his regularity lemma implies that $f_c(n)\to \infty$.

OPEN
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$, as Faudree and McKay [FaMc93] showed that $R(W)=17$ for the pentagonal wheel $W$.

Since $R(k)\leq 4^k$ this is trivial for $\epsilon\geq 3/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)$.

SOLVED - $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. Additional thanks to: Zachary Hunter and Mehtaab Sawhney OPEN Let$k=k(n,m)$be minimal such that any directed graph on$k$vertices must contain either an independent set of size$n$or a directed path of size$m$. Determine$k(n,m)$. A problem of Erdős and Rado [ErRa67], who showed $k(n,m) \leq \frac{2^{m-1}(n-1)^m+n-2}{2n-3}.$ Larson and Mitchell [LaMi97] prove that$k(n,m)\leq n^{m-1}$for$m\geq 3$. SOLVED 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$contain either a red$K_\alpha$or a blue$K_n$? Conjectured by Erdős and Hajnal. The answer is no, as independently shown by Schipperus [Sc99] (published in [Sc10]) and Darby [Da99]. For example, Larson [La00] has shown that this is false when$\alpha=\omega^{\omega^2}$and$n=5$. There is more background and proof sketches in Chapter 2.9 of [HST10], by Hajnal and Larson. Additional thanks to: Zachary Chase, Andrés Caicedo OPEN 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. Additional thanks to: Antonio Girao OPEN There exists some constant$c>0$such that $$R(C_4,K_n) \ll n^{2-c}.$$ 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 [EFRS78]), and the lower bound is due to Spencer [Sp77]. OPEN -$500
Let $\alpha\in[0,1/2)$ and $n,t\geq 1$. Let $F^{(t)}(n,\alpha)$ be the largest $m$ such that we can $2$-colour the edges of the complete $t$-uniform hypergraph on $n$ vertices such that if $X\subseteq [n]$ with $\lvert X\rvert \geq m$ then 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, Hajnal, and Rado (see [562]) 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$.

Erdős believed there might be just one jump, occcurring at $\alpha=0$.

OPEN
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.$
SOLVED
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. This is equivalent to showing that if $H$ is the union of $c$ forests then $R(H)\ll_c n$, and also that if every subgraph has average degree at most $d$ then $R(H)\ll_d n$. Solved by Lee [Le16], who proved that $R(H) \leq 2^{2^{O(d)}}n.$
OPEN - $250 Give an asymptotic formula for$R(3,k)$. 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. See also [544]. SOLVED -$250
Prove that $R(4,k) \gg \frac{k^3}{(\log k)^{O(1)}}.$
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}.$
OPEN
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$.

OPEN
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.
OPEN
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].

OPEN
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.)
OPEN - $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}.$

Additional thanks to: Antonio Girao, David Penman
OPEN
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$ (using the fact that $\|\sqrt{2}q\| \gg 1/q$ for all $q$, where $\|x\|$ is the distance to the nearest integer). 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.
OPEN
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').
SOLVED
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.

Additional thanks to: Ryan Alweiss, Vjekoslav Kovac
SOLVED
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.$

SOLVED
Is it true that, in any finite colouring of the integers, there must be two integers $x\neq y$ of the same colour such that $x+y$ is a square? What about a $k$th power?
A question of Roth, Erdős, Sárközy, and Sós. In other words, if $G$ is the infinite graph on $\mathbb{N}$ where we connect $m,n$ by an edge if and only if $n+m$ is a square, then is the chromatic number of $G$ equal to $\aleph_0$?

This is true, as proved by Khalfalah and Szemerédi [KhSz06], who in fact prove the general result with $x+y=z^2$ replaced by $x+y=f(z)$ for any non-constant $f(z)\in \mathbb{Z}[z]$ such that $2\mid f(z)$ for some $z\in \mathbb{Z}$.

OPEN
Let $f(k)$ be the minimal $N$ such that if $\{1,\ldots,N\}$ is $k$-coloured then there is a monochromatic solution to $a+b=c$. Estimate $f(k)$. In particular, is it true that $f(k) < c^k$ for some constant $c>0$?
Schur proved that $f(k)<ek!$. See also [183].
OPEN
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.
OPEN
What is the chromatic number of the plane? That is, what is the smallest number of colours required to colour $\mathbb{R}^2$ such that no two points of the same colour are distance $1$ apart?
The Hadwiger-Nelson problem. Let $\chi$ be the chromatic number of the plane. An equilateral triangle trivially shows that $\chi\geq 3$. There are several small graphs that show $\chi\geq 4$ (in particular the Moser spindle and Golomb graph). The best bounds currently known are $5 \leq \chi \leq 7.$ The lower bound is due to de Grey [dG18]. The upper bound can be seen by colouring the plane by tesselating by hexagons with diameter slightly less than $1$.
OPEN
Let $F(k)$ be the minimal $N$ such that if we two-colour $\{1,\ldots,N\}$ there is a set $A$ of size $k$ such that all subset sums $\sum_{a\in S}a$ (for $\emptyset\neq S\subseteq A$) are monochromatic. Estimate $F(k)$.
The existence of $F(k)$ was established by Sanders and Folkman, and it also follows from Rado's theorem. It is commonly known as Folkman's theorem.

Erdős and Spencer [ErSp89] proved that $F(k) \geq 2^{ck^2/\log k}$ for some constant $c>0$. Balogh, Eberhrad, Narayanan, Treglown, and Wagner [BENTW17] have improved this to $F(k) \geq 2^{2^{k-1}/k}.$

SOLVED
If $\mathbb{N}$ is 2-coloured then is there some infinite set $A\subseteq \mathbb{N}$ such that all finite subset sums $\sum_{n\in S}n$ (as $S$ ranges over all non-empty finite subsets of $A$) are monochromatic?
In other words, must some colour class be an IP set. Asked by Graham and Rothschild. See also [531].

Proved by Hindman [Hi74] (for any number of colours).

OPEN
Show that $R(3,k+1)-R(3,k)\to\infty$ as $k\to \infty$. Similarly, prove or disprove that $R(3,k+1)-R(3,k)=o(k).$
OPEN
Show that if $G$ has $\binom{n}{2}$ edges then $R(G) \leq R(n).$ More generally, if $G$ has $\binom{n}{2}+t$ edges with $t\leq n$ then $R(G)\leq R(H)$ where $H$ is the graph formed by connected a new vertex to $t$ of the vertices of $K_n$.
In other words, are cliques extremal for Ramsey numbers. Asked by Erdős and Graham.
SOLVED
Is it true that if $G$ has $m$ edges then $R(G) \leq 2^{O(m^{1/2})}?$
This is true, and was proved by Sudakov [Su11]. The analogous question for $\geq 3$ colours is still open.
OPEN
If $T$ is a tree on $n$ vertices then $R(T) \leq 2n-2.$
Equality holds when $T$ is a star on $n$ vertices.

Implied by [548].

SOLVED
If $T$ is a tree which is a bipartite graph with $k$ vertices and $2k$ vertices in the other class then show that $R(T)=4k$.
It follows from results in [EFRS82] that $R(T)\geq 4k-1$.

This is false: Norin, Sun, and Zhao [NSZ16] have proved that if $T$ is the union of two stars on $k$ and $2k$ vertices, with an edge joining the centre of the two stars, then $R(T)\geq (4.2-o(1))k$. The best upper bound for the Ramsey number for this tree is $R(T)\leq 4.27492k+1$, obtained by Dubó and Stein [DuSt24].

OPEN
Let $m_1\leq\cdots\leq m_k$ and $n$ be sufficiently large. If $T$ is a tree on $n$ vertices and $G$ is the complete multipartite graph with vertex class sizes $m_1,\ldots,m_k$ then prove that $R(T,G)\leq (\chi(G)-1)(R(T,K_{m_1,m_2})-1)+m_1.$
Chvátal [Ch77] proved that $R(T,K_m)=(m-1)(n-1)+1$.
SOLVED
Prove that $R(C_k,K_n)=(k-1)(n-1)+1$ for $k\geq n\geq 3$ (except when $n=k=3$).
Asked by Erdős, Faudree, Rousseau, and Schelp, who also ask for the smallest value of $k$ such that this identity holds (for fixed $n$). They also ask, for fixed $n$, what is the minimum value of $R(C_k,K_n)$?

This identity was proved for $k>n^2-2$ by Bondy and Erdős [BoEr73]. Nikiforov [Ni05] extended this to $k\geq 4n+2$.

Keevash, Long, and Skokan [KLS21] have proved this identity when $k\geq C\frac{\log n}{\log\log n}$ for some constant $C$, thus establishing the conjecture for sufficiently large $n$.

OPEN
Determine $R(C_4,S_n),$ where $S_n$ is the star on $n+1$ vertices.
It was shown in [BEFRS89] that $n+\lceil\sqrt{n}\rceil+1\geq R(C_4,S_n)\geq n+\sqrt{n}-6n^{11/40}.$ Füredi (unpublished) has shown that $R(C_4,S_n)=n+\lceil\sqrt{n}\rceil$ for infinitely many $n$.
SOLVED
Let $R(3,3,n)$ denote the smallest integer $m$ such that if we $3$-colour the edges of $K_m$ then there is either a monochromatic triangle in one of the first two colours or a monochromatic $K_n$ in the third colour. Define $R(3,n)$ similarly but with two colours. Show that $\frac{R(3,3,n)}{R(3,n)}\to \infty$ as $n\to \infty$.
A problem of Erdős and Sós. This was solved by Alon and Rödl [AlRo05], who in fact show that $R(3,3,n)\asymp n^3(\log n)^{O(1)}$ (recalling that Shearer [Sh83] showed $R(3,n) \ll n^2/\log n$).
OPEN
Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Show that $\lim_{k\to \infty}\frac{R(C_{2n+1};k)}{R(K_3;k)}=0$ for any $n\geq 2$.
A problem of Erdős and Graham. The problem is open even for $n=2$.
OPEN
Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Determine the value of $R(C_{2n};k).$
A problem of Erdős and Graham. Erdős [Er81c] gives the bounds $k^{1+\frac{1}{2n}}\ll R(C_{2n};k)\ll k^{1+\frac{1}{n-1}}.$ Chung and Graham [ChGr75] showed that $R(C_4;k)>k^2-k+1$ when $k-1$ is a prime power and $R(C_4;k)\leq k^2+k+1$ for all $k$.
SOLVED
Let $R(G;3)$ denote the minimal $m$ such that if the edges of $K_m$ are $3$-coloured then there must be a monochromatic copy of $G$. Show that $R(C_n;3) \leq 4n-3.$
A problem of Bondy and Erdős. This inequality is best possible for odd $n$.

Luczak [Lu99] has shown that $R(C_n;3)\leq (4+o(1))n$ for all $n$, and in fact $R(C_n;3)\leq 3n+o(n)$ for even $n$.

Kohayakawa, Simonovits, and Skokan [KSS05] proved this conjecture when $n$ is sufficiently large and odd. Benevides and Skokan [BeSk09] proved that if $n$ is sufficiently large and even then $R(C_n;3)=2n$.

OPEN
Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Is it true that $R(T;k)=kn+O(1)$ for any tree $T$ on $n$ vertices?
A problem of Erdős and Graham. Implied by [548].
OPEN
Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Determine $R(K_{s,t};k)$ where $K_{s,t}$ is the complete bipartite graph with $s$ vertices in one component and $t$ in the other.
Chung and Graham [ChGr75] prove the bounds $(2\pi\sqrt{st})^{\frac{1}{s+t}}\left(\frac{s+t}{e^2}\right)k^{\frac{st-1}{s+t}}\leq R(K_{s,t};k)\leq (t-1)(k+k^{1/s})^s.$ For example this implies that $R(K_{3,3};k) \ll k^3.$ Using Turán numbers one can show that $R(K_{3,3};k) \gg \frac{k^3}{(\log k)^3}.$
SOLVED
Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges that is Ramsey for $G$.

If $G$ has $n$ vertices and maximum degree $d$ then prove that $\hat{R}(G)\ll_d n.$

A problem of Beck and Erdős. Beck [Be83b] proved this when $G$ is a path. Friedman and Pippenger [FrPi87] proved this when $G$ is a tree. Haxell, Kohayakawa, and Luczak [HKL95] proved this when $G$ is a cycle. An alternative proof when $G$ is a cycle (with better constants) was given by Javadi, Khoeini, Omidi, and Pokrovskiy [JKOP19].

This was disproved for $d=3$ by Rödl and Szemerédi [RoSz00], who constructed a graph on $n$ vertices with maximum degree $3$ such that $\hat{R}(G)\gg n(\log n)^{c}$ for some absolute constant $c>0$. Tikhomirov [Ti22b] has improved this to $\hat{R}(G)\gg n\exp(c\sqrt{\log n}).$ It is an interesting question how large $\hat{R}(G)$ can be if $G$ has maximum degree $3$. Kohayakawa, Rödl, Schacht, and Szemerédi [KRSS11] proved an upper bound of $\leq n^{5/3+o(1)}$ and Conlon, Nenadov, and Trujić [CNT22] proved $\ll n^{8/5}$. The best known upper bound of $\leq n^{3/2+o(1)}$ is due to Draganić and Petrova [DrPe22].

OPEN
Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges such that in any $2$-colouring of the edges of $H$ there is a monochromatic copy of $G$.

Determine $\hat{R}(K_{n,n}),$ where $K_{n,n}$ is the complete bipartite graph with $n$ vertices in each component.

We know that $\frac{1}{60}n^22^n<\hat{R}(K_{n,n})< \frac{3}{2}n^32^n.$ The lower bound (which holds for $n\geq 6$) was proved by Erdős and Rousseau [ErRo93]. The upper bound was proved by Erdős, Faudree, Rousseau, and Schelp [EFRS78b] and Nešetřil and Rödl [NeRo78].

Conlon, Fox, and Wigderson [CFW23] have proved that, for any $s\leq t$, $\hat{R}(K_{s,t})\gg s^{2-\frac{s}{t}}t2^s,$ and prove that when $t\gg s\log s$ we have $\hat{R}(K_{s,t})\asymp s^2t2^s$. They conjecture that this should hold for all $s\leq t$, and so in particular we should have $\hat{R}(K_{n,n})\asymp n^32^n$.

OPEN
Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges such that in any $2$-colouring of the edges of $H$ there is a monochromatic copy of $G$.

Let $F_1$ and $F_2$ be the union of stars. More precisely, let $F_1=\cup_{i\leq s} K_{1,n_i}$ and $F_2=\cup_{j\leq t} K_{1,m_j}$. Prove that $\hat{R}(F_1,F_2) = \sum_{2\leq k\leq s+2}\max\{n_i+m_j-1 : i+j=k\}.$

Burr, Erdős, Faudree, Rousseau, and Schelp [BEFRS78] proved this when all the $n_i$ are identical and all the $m_i$ are identical.
OPEN
Let $R_r(n)$ denote the $r$-uniform hypergraph Ramsey number: the minimal $m$ such that if we $2$-colour all edges of the complete $r$-uniform hypergraph on $m$ vertices then there must be some monochromatic copy of the complete $r$-uniform hypergraph on $n$ vertices.

Prove that, for $r\geq 3$, $\log_{r-1} R_r(n) \asymp_r n,$ where $\log_{r-1}$ denotes the $(r-1)$-fold iterated logarithm. That is, does $R_r(n)$ grow like $2^{2^{\cdots n}}$ where the tower of exponentials has height $r-1$?

A problem of Erdős, Hajnal, and Rado [EHR65]. A generalisation of [564].
OPEN
Let $F(n,\alpha)$ denote the largest $m$ such that there exists a $2$-colouring of the edges of $K_n$ so that every $X\subseteq [n]$ with $\lvert X\rvert\geq m$ contains more than $\alpha \binom{\lvert X\rvert}{2}$ many edges of each colour.

Prove that, for every $0\leq \alpha\leq 1/2$, $F(n,\alpha)\sim c_\alpha\log n$ for some constant $c_\alpha$ depending only on $\alpha$.

It is easy to show that, for every $0\leq \alpha\leq 1/2$, $F(n,\alpha)\asymp_\alpha \log n.$

Note that when $\alpha=0$ this is just asking for a $2$-colouring of the edges of $K_n$ which contains no monochromatic clique of size $m$, and hence we recover the classical Ramsey numbers.

OPEN - $500 Let$R_3(n)$be the minimal$m$such that if the edges of the$3$-uniform hypergraph on$m$vertices are$2$-coloured then there is a monochromatic copy of the$3$-uniform hypergraph on$n$vertices. Is there some constant$c>0$such that $R_3(n) \geq 2^{2^{cn}}?$ A special case of [562]. A problem of Erdős, Hajnal, and Rado [EHR65], who prove the bounds $2^{cn^2}< R_3(n)< 2^{2^{n}}$ for some constant$c>0$. Erdős, Hajnal, Máté, and Rado [EHMR84] have proved a doubly exponential lower bound for the corresponding problem with$4$colours. OPEN Let$R^*(G)$be the induced Ramsey number: the minimal$m$such that there is a graph$H$on$m$vertices such that any$2$-colouring of the edges of$H$contains an induced monochromatic copy of$G$. Is it true that $R^*(G) \leq 2^{O(n)}$ for any graph$G$on$n$vertices? A problem of Erdős and Rödl. Even the existence of$R^*(G)$is not obvious, but was proved independently by Deuber [De75], Erdős, Hajnal, and Pósa [EHP75], and Rödl [Ro73]. Rödl [Ro73] proved this when$G$is bipartite. Kohayakawa, Prömel, and Rödl [KPR98] have proved that $R^*(G) < 2^{O(n(\log n)^2)}.$ An alternative (and more explicit) proof was given by Fox and Sudakov [FoSu08]. Conlon, Fox, and Sudakov [CFS12] have improved this to $R^*(G) < 2^{O(n\log n)}.$ Additional thanks to: Zach Hunter OPEN Let$G$be such that any subgraph on$k$vertices has at most$2k-3$edges. Is it true that, if$H$has$m$edges and no isolated vertices, then $R(G,H)\ll m?$ In other words, is$G$Ramsey size linear? This fails for a graph$G$with$n$vertices and$2n-2$edges (for example with$H=K_n$). Erdős, Faudree, Rousseau, and Schelp [EFRS93] have shown that any graph$G$with$n$vertices and at most$n+1$edges is Ramsey size linear. Implies [567]. OPEN Let$G$be either$Q_3$or$K_{3,3}$or$H_5$(the last formed by adding two vertex-disjoint chords to$C_5$). Is it true that, if$H$has$m$edges and no isolated vertices, then $R(G,H)\ll m?$ In other words, is$G$Ramsey size linear? A special case of [566]. In [Er95] Erdős specifically asks about the case$G=K_{3,3}$. The graph$H_5$can also be described as$K_4^*$, obtained from$K_4$by subdividing one edge. ($K_4$itself is not Ramsey size linear, since$R(4,n)\gg n^{3-o(1)}$, see [166].) Bradać, Gishboliner, and Sudakov [BGS23] have shown that every subdivision of$K_4$on at least$6$vertices is Ramsey size linear, and also that$R(H_5,H) \ll m$whenever$H$is a bipartite graph with$m$edges and no isolated vertices. OPEN Let$G$be a graph such that$R(G,T_n)\ll n$for any tree$T_n$on$n$vertices and$R(G,K_n)\ll n^2$. Is it true that, for any$H$with$m$edges and no isolated vertices, $R(G,H)\ll m?$ In other words, is$G$Ramsey size linear? OPEN Let$k\geq 1$. What is the best possible$c_k$such that $R(C_{2k+1},H)\leq c_k m$ for any graph$H$on$m$edges without isolated vertices? OPEN Let$k\geq 3$. Is it true that, for any graph$H$on$m$edges without isolated vertices, $R(C_k,H) \leq 2m+\left\lceil\frac{k-1}{2}\right\rceil?$ This was proved for even$k$by Erdős, Faudree, Rousseau, and Schelp [EFRS93]. It was proved for$k=3$by Sidorenko [Si93]. SOLVED -$100
Does there exist a graph $G$ with at most $10^{10}$ many vertices which contains no $K_4$, and yet any $2$-colouring of the edges produces a monochromatic $K_3$?
Erdős and Hajnal [ErHa67] first asked for the existence of any such graph. Existence was proved by Folkman [Fo70], but with very poor quantitative bounds. (As a result these quantities are often called Folkman numbers.) Let this particular Folkman number be denoted by $N$.

Frankl and Rödl [FrRo86] proved $N\leq 7\times 10^{11}$, which Spencer [Sp88] improved to $\leq 3\times 10^{9}$. This resolved the initial challenge of Erdős [Er75d] to beat $10^{10}$.

Lu [Lu07] proved $N\leq 9697$ vertices. The current record is due to Dudek and Rödl [DuRo08] who proved $N\leq 941$ vertices. For further information we refer to a paper of Radziszowski and Xu [RaXu07], who prove that $N\geq 19$ and speculate that $N\leq 127$.

SOLVED - $250 Let$\alpha$be the infinite ordinal$\omega^\omega$. Is it true that in any red/blue colouring of the edges of$K_\alpha$there is either a red$K_\alpha$or a blue$K_3$? A problem of Erdős and Rado. For comparison, Specker [Sp57] proved this property holds when$\alpha=\omega^2$and false when$\alpha=\omega^n$for$3\leq n<\omega$. This is true, and was proved by Chang [Ch72]. Milner modified his proof to prove that this remains true if we replace$K_3$by$K_m$for all finite$m<\omega$(a shorter proof was found by Larson [La73]). See also [591] and [592]. OPEN -$250
Let $\alpha$ be the infinite ordinal $\omega^{\omega^2}$. Is it true that in any red/blue colouring of the edges of $K_\alpha$ there is either a red $K_\alpha$ or a blue $K_3$?
For comparison, Specker [Sp57] proved this property holds when $\alpha=\omega^2$ and false when $\alpha=\omega^n$ for $3\leq n<\omega$. Chang proved this property holds when $\alpha=\omega^\omega$ (see [590]).

See [592] for the general case.

OPEN - $1000 Determine which countable ordinals$\beta$have the property that, if$\alpha=\omega^{^\beta}$, then in any red/blue colouring of the edges of$K_\alpha$there is either a red$K_\alpha$or a blue$K_3$. This property holds for$\beta=2$and not for$3\leq \beta <\omega$(Specker [Sp57]) and for$\beta=\omega$(Chang [Ch72]). The first open case is$\beta=\omega^2$(see [591]). Galvin and Larson [GaLa74] have shown that if$\beta\geq 3$has this property then$\beta$must be 'additively indecomposable', so that in particular$\beta=\omega^\gamma$for some$\gamma<\omega_1$. Galvin and Larson conjecture that every$\beta\geq 3$of this form has this property. See also [590]. OPEN For which graphs$G_1,G_2$is it true that • for every$n\geq 1$there is a graph$H$without a$G_1$but if the edges of$H$are$n$-coloured then there is a monochromatic copy of$G_2$, and yet • for every graph$H$without a$G_1$there is an$\aleph_0$-colouring of the edges of$H$without a monochromatic$G_2$. Erdős and Hajnal originally conjectured that there are no such$G_1,G_2$, but in fact$G_1=C_4$and$G_2=C_6$is an example. Indeed, for this pair Nešetřil and Rödl established the first property and Erdős and Hajnal the second (in fact every$C_4$-free graph is a countable union of trees). Whether this is true for$G_1=K_4$and$G_2=K_3$is the content of [595]. OPEN Let$G$be a graph on at most$\aleph_1$vertices which contains no$K_4$and no$K_{\aleph_0,\aleph_0}$(the complete bipartite graph with$\aleph_0$vertices in each class). Is it true that $\omega_1^2 \to (\omega_1\omega, G)^2?$ What about finite$G$? Erdős and Hajnal proved that$\omega_1^2 \to (\omega_1\omega,3)^2$. Erdős originally asked this with just the assumption that$G$is$K_4$-free, but Baumgartner proved that$\omega_1^2 \not\to (\omega_1\omega, K_{\aleph_0,\aleph_0})^2$. OPEN Let$m$be an infinite cardinal and$\kappa$be the successor cardinal of$2^{\aleph_0}$. Can one colour the countable subsets of$m$using$\kappa$many colours so that every$X\subseteq m$with$\lvert X\rvert=\kappa$contains subsets of all possible colours? SOLVED Let$f(n)$be minimal such that if the edges of$K_{2^n+1}$are coloured with$n$colours then there must be a monochromatic odd cycle of length at most$m$. Estimate$f(n)$. Does$f(n)\to \infty$as$n\to \infty$? A problem of Erdős and Graham. The edges of$K_{2^n}$can be$n$-coloured to avoid odd cycles of any length. It can be shown that$C_5$and$C_7$can be avoided for large$n$. Day and Johnson [DaJo17] have shown that $f(n)\geq 2^{c\sqrt{\log n}}$ for some constant$c>0$. Additional thanks to: Zach Hunter SOLVED Does there exist some constant$c>0$such that if$G$is a graph with$n$vertices and$\geq (1/8-c)n^2$edges then$G$must contain either a$K_4$or an independent set on at least$n/\log n$vertices? A problem of Erdős, Hajnal, Simonovits, Sós, and Szemerédi [EHSSS93]. In other words, if$\mathrm{rt}(n;k,\ell)$is the Ramsey-Turán number then is it true that $\mathrm{rt}(n; 4,n/\log n)< (1/8-c)n^2?$ Erdős, Hajnal, Sós, and Szemerédi [EHSS83] proved that for any fixed$\epsilon>0$$\mathrm{rt}(n; 4,\epsilon n)< (1/8+o(1))n^2.$ Sudakov [Su03] proved that $\mathrm{rt}(n; 4,ne^{-f(n)})=o(n^2)$ whenever$f(n)/\sqrt{\log n}\to \infty$. Resolved by Fox, Loh, and Zhao [FLZ15] who showed that the answer is no; in fact they prove that $\mathrm{rt}(n; 4, ne^{-f(n)})\geq (1/8-o(1))n^2$ whenever$f(n) =o(\sqrt{\log n/\log\log n})\$.