Logo
All Random Solved Random Open
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$.

Additional thanks to: Mehtaab Sawhney
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.

See also [54].

Additional thanks to: Mehtaab Sawhney
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].

Additional thanks to: Tuan Tran
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].

See also the entry in the graphs problem collection.

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

See also the entry on the graphs problem collection.

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

See also [600] and the entry in the graphs problem collection.

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

See also the entry in the graphs problem collection and this second one.

Additional thanks to: Yuval Wigderson
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$.

See also the entry in the graphs problem collection.

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

See also the entry in the graphs problem collection.

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

See also [563].

See also the entry in the graphs problem collection.

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

See also the entry in the graphs problem collection.

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}.\]

See also the entry in the graphs problem collection.

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

Additional thanks to: Ryan Alweiss
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.)

See also the entry in the graphs problem collection.

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}.\]

See also [483].

See also the entry in the graphs problem collection.

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

Additional thanks to: Mehtaab Sawhney
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}$.

Additional thanks to: Deepak Bal
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.

See also the entry in the graphs problem collection.

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.

See also the entry in the graphs problem collection.

Additional thanks to: Zach Hunter
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].

See also the entry in the graphs problem collection.

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

See also the entry in the graphs problem collection.

Additional thanks to: Zach Hunter
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$.

See also the entry in the graphs problem collection.

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

See also the entry in the graphs problem collection.

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

See also the entry in the graphs problem collection.

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

See also the entry in the graphs problem collection.

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

See also the entry in the graphs problem collection.

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

See also the entry in the graphs problem collection.

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

See also the entry in the graphs problem collection.

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

See also the entry in the graphs problem collection.

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}.\]

See also the entry in the graphs problem collection.

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

See also the entry in the graphs problem collection.

Additional thanks to: Zach Hunter
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$.

See also the entry in the graphs problem collection.

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.

See also the entry in the graphs problem collection.

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

See also the entry in the graphs problem collection.

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.

See also [161].

See also the entry in the graphs problem collection.

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.

See also the entry in the graphs problem collection.

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)}.\]

See also the entry in the graphs problem collection.

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

See also the entry in the graphs problem collection.

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.

See also the entry in the graphs problem collection.

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?

See also the entry in the graphs problem collection.

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

See also the entry in the graphs problem collection.

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

See also the entry in the graphs problem collection.

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

See also the entry in the graphs problem collection.

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

See also [22] and the entry in the graphs problem collection.

Additional thanks to: Mehtaab Sawhney