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

The existence of such an $n_k$ is mentioned in problem B2 of Guy's collection [Gu04].

View the LaTeX source

This page was last edited 28 September 2025.

The answer is yes, as proved by Croot [Cr03] - indeed, there are infinitely many disjoint such monochromatic solutions.

In [ErGr80] they also ask for a monochromatic representation of any $\frac{a}{b}>0$. This follows from the case of $1$ - indeed, consider the induced colouring of $\{\tfrac{n}{b}: b\mid n\}$. By the above there are $a$ solutions to\[1=\sum_i \frac{1}{n_i/b},\]and hence $a$ solutions to $\frac{1}{b}=\sum_i \frac{1}{n_i}$, where all $n_i$ are distinct (across the $a$ many solutions). Summing across all variables then yields $\frac{a}{b}=\sum_j \frac{1}{m_j}$ where all $m_j$ are distinct and the same colour, as required.

See also [298].

View the LaTeX source

This page was last edited 20 December 2025.

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] and [843].

View the LaTeX source

This page was last edited 28 October 2025.

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] and [843].

View the LaTeX source

Erdős and Rado proved that $\mathfrak{c}\to (\omega+n,4)_2^3$ for any $2\leq n<\omega$.

View the LaTeX source

This page was last edited 23 January 2026.

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

In [Er97d] Erdős also asks for a lower bound for the count of edge-disjoint monochromatic triangles in single colour (the colour chosen to maximise this quantity), and speculates that the answer is $\geq cn^2$ for some constant $c>1/24$.

View the LaTeX source

This page was last edited 23 January 2026.

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'. (In [Er88] he raises this prize to \$10000). 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]. This was improved to $3.7992\cdots$ by Gupta, Ndiaye, Norin, and Wei [GNNW24].

A shorter and simpler proof of an upper bound of the strength $4-c$ for some constant $c>0$ (and a generalisation to the case of more than two colours) was given by Balister, Bollobás, Campos, Griffiths, Hurley, Morris, Sahasrabudhe, and Tiba [BBCGHMST24].

In [Er93] Erdős writes 'I have no idea what the value of $\lim R(k)^{1/k}$ should be, perhaps it is $2$ but we have no real evidence for this.'

This problem is #3 in Ramsey Theory in the graphs problem collection.

See also [1029] for a problem concerning a lower bound for $R(k)$ and discussion of lower bounds in general.

A famous quote of Erdős concerns the difficulty of finding exact values for $R(k)$. This is often repeated in the words of Spencer, who phrased it as an alien attacking race. The earliest such quote in a paper of Erdős I have found is in [Er93], where he writes:

'Sometime ago, I made the following joke. If an evil spirit would appear and say "unless you give me the value of $R(5)$ within a year, I will exterminate humanity", then our best bet would be perhaps to get all our computers working on $R(5)$ and we probably would get its value in a year.

If he would ask for $R(6)$, the best strategy probably would be to destroy it before it can destroy us. If we would be so clever that we could give the answer by mathematics, we would just tell him: "if you try to do something you will see what will happent to you...". I think we are strong enugh now and the only evil spirit we have to feel is the one which is in ourselves (quoting somebody: I have seen the enemy and them are us). Now enough of the idle talk and back to Mathematics.'

View the LaTeX source

This page was last edited 23 January 2026.

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

In [Er69b] Erdős asks for even a construction whose largest clique or independent set has size $o(n^{1/2})$, which is now known.

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

This problem is #4 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 23 January 2026.

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

Wigderson [Wi24] has proved that there are infinitely many such graphs (although his proof is not explicit, and an explicit example of such a graph apart from $K_4$ is still unknown).

View the LaTeX source

A problem of Erdős and Rothschild. Alon and Trotter showed that, provided $c<1/4$, $f_c(n)\ll_c n^{1/2}$. Szemerédi observed that his regularity lemma implies that $f_c(n)\to \infty$.

Edwards (unpublished) and Khadziivanov and Nikiforov [KhNi79] proved independently that $f_c(n) \geq n/6$ when $c>1/4$ (see [905]).

Fox and Loh [FoLo12] proved that\[f_c(n) \leq n^{O(1/\log\log n)}\]for all $c<1/4$, disproving the first conjecture of Erdős.

The best known lower bounds for $f_c(n)$ are those from Szemerédi's regularity lemma, and as such remain very poor.

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

View the LaTeX source

The function $f(n)$ is a reformulation of the Ramsey number $R(C_4,K_{1,n})$, in that\[R(C_4,K_{1,n})=\min\{ m : f(m)\leq m-n\}\]and\[f(n)=\min\{ m : m\geq R(C_4, K_{1,n-m})\}.\]The behaviour of this Ramsey number more generally is [552].

A weaker version of the conjecture asks for some constant $c$ such that $f(m)>f(n)-c$ for all $m>n$. This question can be asked for other graphs than $C_4$.

The bounds in [552] imply in particular that $f(n)<\sqrt{n}+1$ and\[f(n)=(1+o(1))\sqrt{n}.\]It is easy to check that $f(4)=2$.

View the LaTeX source

This page was last edited 06 December 2025.

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

This problem is #12 and #13 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 17 January 2026.

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.

View the LaTeX source

A problem of Erdős and Rado [ErRa67], who showed $k(n,m) \ll_m n^{m-1}$, or more precisely,\[k(n,m) \leq \frac{2^{m-1}(n-1)^m+n-2}{2n-3}.\]Larson and Mitchell [LaMi97] improved the dependence on $m$, establishing in particular that $k(n,3)\leq n^{2}$. Zach Hunter has observed that\[R(n,m) \leq k(n,m)\leq R(n,m,m),\]which in particular proves the upper bound $k(n,m)\leq 3^{n+2m}$.


See also the entry in the graphs problem collection - on this site the problem replaces transitive tournament with directed path, but Zach Hunter and Raphael Steiner have a simple argument that proves, for this alternative definition, that $k(n,m)=(n-1)(m-1)$.

View the LaTeX source

Such $\alpha$ are called partition ordinals. Conjectured by Erdős and Hajnal. In arrow notation, this is asking where $\alpha \to (\alpha,3)^2$ implies $\alpha \to (\alpha, n)^2$ for every finite $n$.

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.

See also [590], [591], and [592] for more on partition ordinals.

View the LaTeX source

This page was last edited 17 January 2026.

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. Erdős thought it 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, and indeed $R(n;3,2) \geq C^{n}$:

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), provided $N \leq 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.

View the LaTeX source

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

This problem is #17 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

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) \gg_\alpha (\log n)^{\frac{1}{t-1}}\]for all $\alpha>0$, and a similar upper bound holds for $\alpha$ close to $1/2$.

Erdős said in [Er90b]: 'If I can hazard a guess completely unsupported by evidence, I am afraid that the jump occurs all in one step at $0$. It would be much more interesting if my conjecture would be wrong and perhaps there is some hope for this for $t>3$. I know nothing and offer \$500 to anybody who can clear up this mystery.'

Conlon, Fox, and Sudakov [CFS11] have proved that, for any fixed $\alpha>0$,\[F^{(3)}(n,\alpha) \ll_\alpha \sqrt{\log n}.\]Coupled with the lower bound above, this implies that there is only one jump for fixed $\alpha$ when $t=3$, at $\alpha=0$.

For all $\alpha>0$ it is known that\[F^{(t)}(n,\alpha)\gg_t (\log n)^{c_\alpha}.\]See also [563] for more on the case $t=2$.

This problem is #40 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 16 January 2026.

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

View the LaTeX source

This page was last edited 30 December 2025.

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 [Le17], who proved that\[ R(H) \leq 2^{2^{O(d)}}n.\]More precisely, Lee proved that\[ R(H) \leq 2^{d2^{O(\chi(H))}}n.\]It is conjectured that $R(H) \leq 2^{O(d)}n$.

This problem is #9 in Ramsey Theory in the graphs problem collection. See also [800].

View the LaTeX source

This page was last edited 22 January 2026.

It is known that there exists some constant $c>0$ such that for large $k$\[(c+o(1))\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 [AKS80].

The value of $c$ in the lower bound has seen a number of improvements. Kim's original proof gave $c\geq 1/162$. The bound $c\geq 1/4$ was proved 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.

This was, however, improved by Campos, Jenssen, Michelen, and Sahasrabudhe [CJMS25] to $c\geq 1/3$, and further by Hefty, Horn, King, and Pfender [HHKP25] to $c\geq 1/2$. Both of these papers conjecture that $c=1/2$ is the correct asymptotic.

See also [544], and [986] for the general case. See [1013] for a related function.

View the LaTeX source

This page was last edited 28 December 2025.

Spencer [Sp77] proved\[R(4,k) \gg (k\log k)^{5/2}.\]Ajtai, Komlós, and Szemerédi [AKS80] 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}.\]This problem is #5 in Ramsey Theory in the graphs problem collection.

See also [986] for the general case.

View the LaTeX source

This page was last edited 23 January 2026.

First asked by Hindman. Hindman [Hi80] has proved this is false (with 7 colours) if we ask for an infinite $A$. In [Er77c] Erdős asks about the case for an infinite $A$ with just $2$ colours.

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

View the LaTeX source

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.

View the LaTeX source

This page was last edited 16 October 2025.

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

View the LaTeX source

This page was last edited 16 October 2025.

Conjectured by Burr and Erdős, althouhg in [Er93] Erdős says the behaviour of $R(Q_n)$ was considered by himself and Sós, who could not decide whether $R(Q_n)/2^n\to \infty$ or not.

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

This problem is #20 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

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\[R(3,k)\geq (380)^{k/5}-O(1),\]due to Ageron, Casteras, Pellerin, Portella, Rimmel, and Tomasik [ACPPRT21] (improving previous bounds of Exoo [Ex94] and Fredricksen and Sweet [FrSw00]). Note that $380^{1/5}\approx 3.2806$.

See also [483].

This problem is #21 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

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.

View the LaTeX source

This page was last edited 01 January 2026.

Erdős, Graham, Montgomery, Rothschild, Spencer, and Straus [EGMRSS75] proved $k\geq 5$. Tsaturian [Ts17] improved this to $k\geq 6$. Erdős and Graham claim that $k\leq 10000000$ ('more or less'), but give no proof.

Erdős and Graham asked this with just any $k$-term arithmetic progression in blue (not necessarily with distance $1$), but Alon has pointed out that in fact no such $k$ exists: in any red/blue colouring of the integer points on a line either there are two red points distance $1$ apart, or else the set of blue points and the same set shifted by $1$ cover all integers, and hence by van der Waerden's theorem there are arbitrarily long blue arithmetic progressions.

It seems most likely, from context, that Erdős and Graham intended to restrict the blue arithmetic progression to have distance $1$ (although they do not write this restriction in their papers).

View the LaTeX source

This page was last edited 14 October 2025.

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.

This problem has been formalised in Lean as part of the Google DeepMind Formal Conjectures project.

View the LaTeX source

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

View the LaTeX source

A question of Roth, Erdős, Sárközy, and Sós [ESS89] (according to some reports, although in [Er80c] Erdős claims this arose in a conversation with Silverman in 1977). Erdős, Sárközy, and Sós [ESS89] proved this for $2$ or $3$ colours.

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

See also [438].

View the LaTeX source

A problem of Erdős from 1954. In other words, when is it the case that\[2^{\aleph_0}\not\to (\aleph_1)_3^2?\]Sierpinski and Kurepa independently proved that this is true for $2$-colours. Erdős proved that this is true under the continuum hypothesis that $\mathfrak{c}=\aleph_1$, and offered \$100 for deciding what happens if the continuum hypothesis is not assumed.

Shelah proved that it is consistent that the answer is negative, although with a very large value of $\mathfrak{c}$. It remains open whether it is consistent to have a negative answer assuming $\mathfrak{c}=\aleph_2$. (This specific question is asked in [Va99].)

View the LaTeX source

This page was last edited 25 January 2026.

The values of $f(k)$ are known as Schur numbers. The best-known bounds for large $k$ are\[(380)^{k/5}-O(1)\leq f(k) \leq \lfloor(e-\tfrac{1}{24}) k!\rfloor-1.\]The lower bound is due to Ageron, Casteras, Pellerin, Portella, Rimmel, and Tomasik [ACPPRT21] (improving previous bounds of Exoo [Ex94] and Fredricksen and Sweet [FrSw00]) and the upper bound is due to Whitehead [Wh73]. Note that $380^{1/5}\approx 3.2806$.

The known values of $f$ are $f(1)=2$, $f(2)=5$, $f(3)=14$, $f(4)=45$, and $f(5)=161$ (see A030126). (The equality $f(5)=161$ was established by Heule [He17]).

See also [183] (in particular a folklore observation gives $f(k)\leq R(3;k)-1$).

View the LaTeX source

This page was last edited 14 October 2025.

A conjecture of Roth.

Solved by Erdős, Sárközy, and Sós [ESS89], who in fact prove that there are at least\[\frac{N}{2}-O(N^{1-1/2^{k+1}})\]many even numbers which are of this form. They also prove that if $k=2$ then there are at least\[\frac{N}{2}-O(\log N)\]many even numbers which are of this form, and that $O(\log N)$ is best possible, since there is a $2$-colouring such that no power of $2$ is representable as a monochromatic sum.

A refinement of this problem appears as Problem 25 on the open problems list of Ben Green.

View the LaTeX source

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

Matolcsi, Ruzsa, Varga, and Zsámboki have proved that the fractional chromatic number of the plane is at least $4$. Croft [Cr67] has proved it is at most $4.359\cdots$.

See also [704], [705], and [706]. The independence number of a finite unit distance graph is the topic of [1070].

View the LaTeX source

This page was last edited 22 January 2026.

A problem of Erdős and Gyárfás. Gerencsér and Gyárfás [GeGy67] proved that, if the paths do not need to be of the same colour, then two paths suffice. Erdős and Gyárfás [ErGy95] proved that $2\sqrt{n}$ vertices suffice, and observed that $\sqrt{n}$ would be best possible here.

Solved in the affirmative by Pokrovskiy, Versteegen, and Williams [PVW24].

View the LaTeX source

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

View the LaTeX source

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

See also [948].

View the LaTeX source

A problem of Erdős and Sós.

This problem is #8 in Ramsey Theory in the graphs problem collection.

See also [165] and [1014].

View the LaTeX source

A question of Erdős and Graham. The weaker question of whether\[R(G) \leq 2^{O(m^{1/2})}\]is the subject of [546]. (This is true, and was proved by Sudakov [Su11].)

LouisD in the comments has noted this fails for small $m$ (in particular for $2\leq m\leq 5$ and $7\leq m\leq 9$).

This problem is #10 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 02 December 2025.

This is true, and was proved by Sudakov [Su11]. The analogous question for $\geq 3$ colours is still open.

Alon, Krivelevich, and Sudakov [AKS03] had earlier given a short proof of this when $G$ is bipartite.

A more precise question is [545].

This problem is #11 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 18 November 2025.

This follows directly from the conjecture of Erdős and Sós in [548], and is therefore proved for all large $n$ assuming the announced proof of [548] by Ajtai, Komlós, Simonovits, and Szemerédi, although this proof has not been published. Zhao [Zh11] has proved $R(T)\leq 2n-2$ for all large $n$ via an alternative method.

If $T$ has a partition into two sets of vertices of sizes $t_1\geq t_2$ then Burr [Bu74] showed\[R(T)\geq \max(t_1+2t_2,2t_1)-1,\]and conjectured this is sharp whenever $t_1\geq t_2\geq 2$. This strong conjecture was disproved by Grossman, Harary, and Klawe [GHK79].

Some results on Ramsey numbers of trees:

• When $T$ is a path on $n$ vertices Gerencsér and Gyárfás [GeGy67] proved $R(T)=\lfloor \frac{3}{2}n\rfloor-1$.
• When $T$ is the star $K_{1,n-1}$ Harary [Ha72] proved $R(T)=2n-2$ if $n$ is even and $2n-3$ if $n$ is odd.
• When $T$ is the double star $S_{t_1,t_2}$, formed by joining the centres of two stars of sizes $t_1$ and $t_2$ by an edge, then when $t_1\geq 3t_2-2$ Grossman, Harary, and Klawe [GHK79] proved $R(T)=2t_1$ (disproving Burr's conjecture).
• Norin, Sun, and Zhao [NSZ16] proved that if $T$ is the double star $S_{2t,t}$ then $R(T)\geq (4.2-o(1))t$.
• Zhao [Zh11] proved $R(T)\leq 2n-2$ for all large even $n$.
• Montgomery, Pavez-Signé, and Yan [MPY25] proved Burr's conjecture, that $R(T)=\max(2t_1,t_1+2t_2)-1$, if $T$ has maximum degree at most $cn$ for some constant $c>0$.

This problem is #14 in Ramsey Theory in the graphs problem collection.

See also [549].

View the LaTeX source

This page was last edited 18 January 2026.

This is a special case of a conjecture of Burr [Bu74] (see [547]).

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$, and conjectured that $R(T)=(4.2+o(1))k$.

The best upper bound for the Ramsey number for this tree is $R(T)\leq (4.21526+o(1))k$, obtained using the flag algebra method by Norin, Sun, and Zhao [NSZ16]. Dubó and Stein [DuSt24] have given a short elementary proof of the weaker bound $R(T)\leq \lceil 4.27492k\rceil+1$

Montgomery, Pavez-Signé, and Yan [MPY25] have proved that $R(T)=4k-1$ if $T$ has maximum degree at most $ck$ for some constant $c>0$.

Erdős, Faudree, Rousseau, and Schelp [EFRS82] proved that $R(T)=4k-1$ if $T$ is a 'broom', formed by identifying the centre of a star on $k+1$ vertices with an endpoint of a path on $2k$ vertices. Burr and Erdős [BuEr76] proved that $R(T)=4k-1$ if $T$ is formed by identifying one end of a path on $4$ vertices with the centre of a star on $k-1$ vertices, and the other endpoint with the centre of a star on $2k-1$ vertices.

This problem is #15 in Ramsey Theory in the graphs problem collection.

See also [547].

View the LaTeX source

This page was last edited 28 December 2025.

Chvátal [Ch77] proved that $R(T,K_m)=(m-1)(n-1)+1$.

This problem is #16 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

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


This problem is #18 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

A problem of Burr, Erdős, Faudree, Rousseau, and Schelp [BEFRS89]. Erdős often asked about $R(C_4,S_n)$ in the equivalent formulation of asking for a bound on the minimum degree of a graph which would guarantee the existence of a $C_4$ (see [85]).

It is known that\[ n+\sqrt{n}-6n^{11/40} \leq R(C_4,S_n)\leq n+\lceil\sqrt{n}\rceil+1.\]The lower bound is due to [BEFRS89], the upper bound is due to Parsons [Pa75]. The lower bound of [BEFRS89] is related to gaps between primes, and assuming e.g. Cramer's conjecture on gaps between primes their lower bound would be $n+\sqrt{n}-n^{o(1)}$.

Erdős offered \$100 for a proof or disproof of the second question in [BEFRS89]. In [Er96] Erdős asks (an equivalent formulation of) whether $R(C_4,S_n)\geq n+\sqrt{n}-O(1)$, but says this is probably 'too optimistic'.

They also ask, if $f(n)=R(C_4,S_n)$, whether $f(n+1)=f(n)$ infinitely often, and is the density of such $n$ $0$? Also, is it true that $f(n+1)\leq f(n)+2$ for all $n$? A similar question about an equivalent function is the subject of [85].

Parsons [Pa75] proved that\[R(C_4,S_n)=n+\lceil\sqrt{n}\rceil\]whenever $n=q^2+1$ for a prime power $q$ and\[R(C_4,S_n)=n+\lceil\sqrt{n}\rceil+1\]whenever $n=q^2$ for a prime power $q$ (in particular both equalities occur infinitely often).

This has been extended in various works, all in the cases $n=q^2\pm t$ for some $0\leq t\leq q$ and prime power $q$. We refer to the work of Parsons [Pa76], Wu, Sun, Zhang, and Radziszowski [WSZR15], and Zhang, Chen, and Cheng ([ZCC17] and [ZCC17b]) for a precise description. In every known case\[R(C_4,S_n)=n+\lceil\sqrt{n}\rceil+\{0,1\},\]and Zhang, Chen, and Cheng [ZCC17] speculate whether this is in fact true for all $n\geq 2$ (whence the answer to the question above would be no).

This problem is #19 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 28 October 2025.

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

This problem is #22 in Ramsey Theory in the graphs problem collection. See also [925].

View the LaTeX source

A problem of Erdős and Graham. The problem is open even for $n=2$.

This problem is #23 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

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

This problem is #24 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

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

This problem is #25 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

A problem of Erdős and Graham. Implied by [548].

This would be best possible since, for example, $R(S_n,k)\geq kn-O(k)$ if $S_n=K_{1,n-1}$ is a star on $n$ vertices.

This problem is #26 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 28 December 2025.

Chung and Graham [ChGr75] prove the general 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\]and determined\[R(K_{2,2},k)=(1+o(1))k^2.\]Alon, Rónyai, and Szabó [ARS99] have proved that\[R(K_{3,3},k)=(1+o(1))k^3\]and that if $s\geq (t-1)!+1$ then\[R(K_{s,t},k)\asymp k^t.\]This problem is #27 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

A problem of Beck, and perhaps also Erdős, although I cannot now find a reference in which Erdős himself discusses this problem - it is asked by Beck in [Be83b], a paper which answers a related question of Erdős [720].

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

This problem is #28 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 18 January 2026.

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

This problem is #29 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 18 January 2026.

Burr, Erdős, Faudree, Rousseau, and Schelp [BEFRS78] proved this when all the $n_i$ are identical and all the $m_i$ are identical.

This problem is #30 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 18 January 2026.

A problem of Erdős, Hajnal, and Rado [EHR65]. A generalisation of [564].

This problem is #38 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 18 January 2026.

It is easy to show via the probabilistic method that, for every $0\leq \alpha<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] for a generalisation to hypergraphs.

This problem is #39 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 18 January 2026.

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.

This problem is #37 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 18 January 2026.

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)}.\]This is true, and an upper bound of\[R^*(G) < 2^{O(n)}\]was proved by Aragão, Campos, Dahia, Filipe, and Marciano [ACDFM25].

This problem is #36 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 18 January 2026.

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

This problem is #31 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 18 January 2026.

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.

This problem is #32 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 18 January 2026.

In other words, is $G$ Ramsey size linear?

This problem is #33 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 18 January 2026.

This problem is #34 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 18 January 2026.

This is Question 5 of [EFRS93]. This was proved for even $k$ by Erdős, Faudree, Rousseau, and Schelp [EFRS93].

This was proved for $k=3$ independently by Goddard and Kleitman [GoKl94] and Sidorenko [Si91]. This was proved for $k=5$ by Jayawardene [Ja99]. Finally it was proved for all odd $k\geq 7$ by Cambie, Freschi, Morawski, Petrova, and Pokrovskiy [CFMPP26].

This problem is #35 in Ramsey Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 16 January 2026.

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 challenge of Erdős [Er75d] to find such a graph with less than $10^{10}$ vertices.

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 and [924] for the general case.

View the LaTeX source

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$ (a question of Erdős for which he offered \$20).

This is true, and was proved by Chang [Ch72]. Milner modified Chang's 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].

View the LaTeX source

In other words, is it true that\[\alpha \to (\alpha, 3)^2?\]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]).

This is true and was proved independently by Schipperus [Sc10] and Darby.

See also [118], and [592] for the general case.

View the LaTeX source

This page was last edited 23 January 2026.

Such $\alpha$ (in other words, those such that $\alpha \to (\alpha,3)^2$) are called partition ordinals.

• Specker [Sp57] proved this holds for $\beta=2$ and not for $3\leq \beta <\omega$.
• Chang [Ch72] proved this holds for $\beta=\omega$.
• 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 countable ordinal $\gamma$. Galvin and Larson conjecture that every $\beta\geq 3$ of this form has this property.
• Schipperus [Sc10] have proved this is holds if $\beta=\omega^\gamma$ in which $\gamma$ is a countable ordinal which is the sum of one or two indecomposable ordinals, and this fails to hold if $\gamma$ is the sum of four or more indecomposable ordinals.

The remaining open case appears to be when $\gamma$ is the sum of three indecomposable ordinals.

The case $\beta=\omega$ is the subject of [590], and $\beta=\omega^2$ is the subject of [591]. See also [118], and [1169] for the case $\alpha=\omega_1^2$.

View the LaTeX source

This page was last edited 23 January 2026.

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

View the LaTeX source

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

View the LaTeX source

This page was last edited 23 January 2026.

View the LaTeX source

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

Chung [Ch97] asked whether $f(n)\to \infty$ as $n\to \infty$. Day and Johnson [DaJo17] proved this is true, and that\[f(n)\geq 2^{c\sqrt{\log n}}\]for some constant $c>0$. The trivial upper bound is $2^n$.

Girão and Hunter [GiHu24] have proved that\[f(n) \ll \frac{2^n}{n^{1-o(1)}}.\]Janzer and Yip [JaYi25] have improved this to\[f(n) \ll n^{3/2}2^{n/2}.\]See also the entry in the graphs problem collection.

View the LaTeX source

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.

View the LaTeX source

A problem of Erdős, Faudree, and Sós, who proved there exist $\gg n^{3/2}$ many such subgraphs, and note that $n^{5/2}$ would be best possible. (Although in [Er93] Erdős credits this question to Alon and Bollobás.)

This was proved by Kwan and Sudakov [KwSu21].

View the LaTeX source

A problem of Erdős, Faudree, and Sós.

This was proved by Bukh and Sudakov [BuSu07].

Jenssen, Keevash, Long, and Yepremyan [JKLY20] have proved that there must exist an induced subgraph which contains $\gg n^{2/3}$ distinct degrees (with no restriction on the number of vertices).

View the LaTeX source

Erdős writes 'if the answer is affirmative many extensions and generalisations will be possible'.

View the LaTeX source

Solved by Erdős, Rousseau, and Schelp for large $n$, but unpublished. Alon has observed that this also follows from a result of Pyber [Py86], which states that (for large enough $n$) at most $\lfloor n^2/4\rfloor+2$ monochromatic cliques cover all edges of a $2$-coloured $K_n$.

This problem was solved completely by Keevash and Sudakov [KeSu04], who proved that the correct threshold is $\lfloor n^2/4\rfloor$ for all $n\geq 7$, is $\binom{n}{2}$ for $n\leq 5$, and is $10$ for $n=6$.

View the LaTeX source

Erdös writes 'perhaps this is easy or false'. It is not true for four-term arithmetic progressions: colour the integers in $[3^{2k},3^{2k+1})$ red and all others blue.

Ryan Alweiss has provided the following simple argument showing that the answer is yes: suppose we have some red/blue colouring without this property. Without loss of generality, suppose $1$ is coloured red, and then either $3$ or $5$ must be blue.

Suppose first that $3$ is blue. If $n\geq 6$ is red then (considering $1,n,2n-1$) we deduce $2n-1$ is blue, and then (considering $3,n+1,2n-1$) we deduce that $n+1$ is red. In particular the colouring must be eventually constant, and we are done.

Now suppose that $5$ is blue. Arguing similarly (considering $1,n,2n-1$ and $5,n+2,2n-1$) we deduce that if $n\geq 8$ is red then $n+2$ is also red, and we are similarly done, since the colouring must be eventually constant on some congruence class modulo $2$.

This was first proved by Brown and Landman [BrLa99], who in fact show that this is always possible with $d>f(x)$ for any increasing function $f$.

View the LaTeX source

This page was last edited 24 October 2025.

A problem of Erdős, Faudree, Rousseau, and Schelp.

When $q=1$ this corresponds exactly to the classical Ramsey problem, and hence for example\[\frac{1}{p-1}\leq c(p,1) \leq \frac{2}{p+1}.\]It is easy to see that if $q=\binom{p-1}{2}+1$ then $c(p,q)=1$. Erdős, Faudree, Rousseau, and Schelp have shown that $c(p,\binom{p-1}{2})\leq 1/2$.

View the LaTeX source

A problem of Erdős, Faudree, Rousseau, and Schelp [EFRS78b].

Answered by Beck [Be83b], who proved that in fact $\hat{R}(P_n)\ll n$ and $\hat{R}(C_n)\ll n$.

A more general problem concerning the size Ramsey number of graphs with bounded maximum degree is [559].

View the LaTeX source

This page was last edited 26 October 2025.

While we do not have a full understanding of the growth of $W(3,k)$, both of the specific challenges of Erdős have been met.
Green [Gr22] established the superpolynomial lower bound\[W(3,k) \geq \exp\left( c\frac{(\log k)^{4/3}}{(\log\log k)
^{1/3}}\right)\]for some constant $c>0$ (in particular disproving a conjecture of Graham that $W(3,k)\ll k^2$). Hunter [Hu22] improved this to\[W(3,k) \geq \exp\left( c\frac{(\log k)^{2}}{\log\log k}\right).\]The first to show that $W(3,k) < \exp(k^c)$ for some $c<1$ was Schoen [Sc21]. The best upper bound currently known is\[W(3,k) \ll \exp\left( O((\log k)^9)\right),\]which follows from the best bounds known for sets without three-term arithmetic progressions (see [BlSi23] which improves slightly on the bounds due to Kelley and Meka [KeMe23]).

View the LaTeX source

A problem of Burr and Erdős. Solved in the affirmative by Alon [Al94]. This is a special case of [163].

View the LaTeX source

Proved by Alon [Al96b].

View the LaTeX source

A problem of Burr, Erdős, Graham, and Sós, who proved that\[F_k(n)\gg n^2.\]See also [810].

View the LaTeX source

A problem of Burr, Erdős, Graham, and Sós.

See also [809].

View the LaTeX source

In [Er91] Erdős credits this problem to himself, Pyber, and Tuza. This problem was explored in a paper of Erdős and Tuza [ErTu93]. In [Er96] Erdős seems to suggest that this might be true for every graph $G$, and specifically asks specific challenge posed in [Er91] and [Er96] is whether, in any balanced edge-colouring of $K_{6n+1}$ by $6$ colours there must exist a rainbow $C_6$ and $K_4$.

In general, one can ask for a quantitative version, defining $d_G(n)$ to be minimal (if it exists) such that if $n$ is sufficiently large and the edges of $K_n$ are coloured with $e(G)$ many colours such that the minimum degree of each colour class is $\geq d_G(n)$ then there is a rainbow copy of $G$. Erdős and Tuza [ErTu93] proved that\[\lfloor n/6\rfloor \leq d_{C_4}(n) \leq \left(\frac{1}{4}-c\right)n\]for some constant $c>0$.

Axenovich and Clemen [AxCl24] have proved that there exist infinitely many graphs without this property. In particular, they show that for any odd $\ell \geq 3$ and $m=\lfloor \sqrt{\ell}+3.5\rfloor$ there exist arbitrarily large $n$ such that $K_n$ has a balanced edge-colouring using $\ell$ colours which contains no rainbow $K_m$. They conjecture that $K_m$ lacks this property for all $m\geq 4$.

Clemen and Wagner [ClWa23] proved that $K_4$ does lack this property.

View the LaTeX source

This page was last edited 14 October 2025.

Burr, Erdős, Faudree, and Schelp [BEFS89] proved that\[R(n+1)-R(n) \geq 4n-8\]for all $n\geq 2$. The lower bound of [165] implies that\[R(n+2)-R(n) \gg n^{2-o(1)}.\]

View the LaTeX source

Asked by Erdős in 1987, according to Katznelson [Ka01]. In other words, does the Cayley graph defined on $\mathbb{Z}$ by a lacunary sequence have a finite chromatic number?

Katznelson observed that a positive solution to the problem follows from the answer to [464], which yields an irrational $\theta$ and $\delta>0$ such that $\inf_k \| \theta n_k\|>\delta$.

Indeed, given such a $\theta$ a colouring of $\mathbb{N}$ using $\ll \delta^{-1}$ colours lacking any solution to $a-b\in A$ can be produced by dividing $\mathbb{R}/\mathbb{Z}$ into disjoint intervals of length $\leq \delta$ and then colouring $n$ according to which interval $\| \theta n\|$ belongs to.

In particular, the solution to [464] implies the answer to this question is yes, with the best known quantitative bound, due to Peres and Schlag [PeSc10], being that there is a colouring with no solutions using at most\[\ll \epsilon^{-1}\log(1/\epsilon)\]colours.

View the LaTeX source

View the LaTeX source

A question of Erdős and Hajnal. Folkman [Fo70] proved this when $k=2$. The case for general $k$ was proved by Nešetřil and Rödl [NeRo76].

See [582] for a special case and [966] for an arithmetic analogue.

View the LaTeX source

It is easy to show that there exists an independent set of size $\gg n^{1/3}$.

In other words, this question asks whether $R(3,3,m) \ll m^{3-c}$ for some $c>0$. This was disproved by Alon and Rödl [AlRo05], who proved that\[\frac{1}{(\log m)^{4+o(1)}}m^3 \ll R(3,3,m) \ll \frac{\log\log m}{(\log m)^2}m^3.\]As reported in [AlRo05] Sudakov has observed that the $\log\log m$ in the upper bound can be removed.

See also [553].

View the LaTeX source

Erdős initially asked whether this is possible with the set being monochromatic, but Galvin showed that this is not always possible, considering the two colouring where, writing $n=2^km$ with $m$ odd, we colour $n$ red if $m\geq F(k)$ and blue if $m<F(k)$ (for some sufficiently quickly growing $F$).

This is open even in the case of $\aleph_0$-many colours.

This is asking about a variant of Hindman's theorem (see [532]).

View the LaTeX source

This page was last edited 22 September 2025.

Erdős suggests that if the answer is no one could consider the variant where we assume that $S$ is Sidon (i.e. all $a+b$ with $a,b\in S$ are distinct, aside from the trivial coincidences).

In the comments Dillies gives a positive proof of this, found by AlphaProof: in other words, if $S\subset \mathbb{R}$ is a Sidon set then there exists $A\subseteq \mathbb{R}\backslash S$ of cardinality continuum such that $A+A\subseteq \mathbb{R}\backslash S$.

View the LaTeX source

This page was last edited 11 January 2026.

In [Er75b] Erdős reports that 'using the methods of our paper with Hajnal and Rado' he could prove that this is false assuming the continuum hypothesis.

A published proof of this is by Hindman, Leader, and Strauss [HLS17] - in fact they prove, assuming the continuum hypothesis, that for any $k\geq 1$ there is a $2$-colouring of $\mathbb{R}$ such that for any uncountable $A\subseteq \mathbb{R}$ the set of $a_1+\cdots+a_k$ with $a_1,\ldots,a_k$ distinct elements of $A$ cannot be monochromatic.

This latter result (and hence a disproof of the original question) was proved without assuming the continuum hypothesis independently by Komjáth [Ko16] and Soukup and Weiss.

View the LaTeX source

This page was last edited 16 January 2026.

Erdős [Er75b] reported that 'Spencer has recently shown that such a sequence exists', but gives no reference.

This is an arithmetic analogue of the graph theory version [924].

View the LaTeX source

Spencer [Sp77] proved this for $k=3$ and Mattheus and Verstraete [MaVe23] proved this for $k=4$.

The best general bounds available are\[\frac{n^{\frac{k+1}{2}}}{(\log n)^{\frac{1}{k-2}-\frac{k+1}{2}}}\ll_k R(k,n) \ll_k \frac{n^{k-1}}{(\log n)^{k-2}}.\]The lower bound was proved by Bohman and Keevash [BoKe10]. The upper bound was proved by Ajtai, Komlós, and Szemerédi [AKS80]. Li, Rousseau, and Zang [LRZ01] have shown that $\ll_k$ in the upper bound can be improved to $\leq (1+o(1))$.

The special case $k=3$ is the topic of [165] and $k=4$ is the topic of [166].

This problem is #6 in Ramsey Theory in the graphs problem collection.

See also [920].

View the LaTeX source

This is open even for $k=3$.

See also [544] for other behaviour of $R(3,k)$, and [1030] for the diagonal version of this question.

View the LaTeX source

A question of Moon [Mo66b], who proved that $f(3)=4$, at least for $n\geq 8$.

Presumably Erdős intended to only ask this question for $n$ sufficiently large depending on $t$. Erdős notes that $f(t)\ll 4^t$, by comparing to the Ramsey number $R(t)$.

Burr, Erdős, and Spencer [BES75] proved that, for $n$ sufficiently large depending on $t$,\[f(t)=R(t,t-1)+x(t,n),\]where $0\leq x(t,n)<t$ is such that $n+1\equiv R(t,t-1)+x\pmod{t}$.

View the LaTeX source

In [Er93] Erdős offers \$100 for a proof of this and \$1000 for a disproof, but says 'this last offer is to some extent phoney: I am sure that [this] is true (but I have been wrong before).'

Erdős and Szekeres [ErSz35] proved\[k2^{k/2} \ll R(k) \leq \binom{2k-1}{k-1}.\]One of the first applications of the probabilistic method pioneered by Erdős gives\[R(k) \geq (1+o(1))\frac{1}{\sqrt{2}e}k2^{k/2},\]which Spencer [Sp75] improved by a factor of $2$ to\[R(k) \geq (1+o(1))\frac{\sqrt{2}}{e}k2^{k/2}.\]See also [77] for a more general problem concerning $\lim R(k)^{1/k}$, and discussion of upper bounds for $R(k)$.

View the LaTeX source

A problem of Erdős and Sós, who could not even prove whether $R(k+1,k)-R(k,k)>k^c$ for any $c>1$.

It is trivial that $R(k+1,k)-R(k,k)\geq k-2$. Burr, Erdős, Faudree, and Schelp [BEFS89] proved\[R(k+1,k)-R(k,k)\geq 2k-5.\]See also [544] for a similar question concerning $R(3,k)$, and [1014] for the general off-diagonal case.

View the LaTeX source

This page was last edited 03 December 2025.

Erdős [Er75f] says Graham and Selfridge proved the answer is yes when $k=3$.

Hunter has observed that, for sufficiently large $n$, a generic projection of $[k]^n$ into $\mathbb{R}^2$ has this property, by the Hales-Jewett theorem.

View the LaTeX source

This page was last edited 19 October 2025.

A conjecture of Erdős, Simonovits, and Sós [ESS75], who gave a simple proof that $\mathrm{AR}(n,C_3)=n-1$. In this paper they announced proofs of the claimed formula for $\mathrm{AR}(n,P_k)$ for $n\geq \frac{5}{4}k+C$ for some large constant $C$, and also for all $n\geq k$ if $k$ is sufficiently large, but these never appeared.

Simonovits and Sós [SiSo84] published a proof that the claimed formula for $\mathrm{AR}(n,P_k)$ is true for $n\geq ck^2$ for some constant $c>0$.

A proof of the formula for $\mathrm{AR}(n,P_k)$ for all $n\geq k\geq 5$ has been announced by Yuan [Yu21]

View the LaTeX source

This page was last edited 31 October 2025.

A problem of Erdős and Hajnal.

This was disproved by Prikry and Mills in 1978 but this seems to have been unpublished. This is reported by Todorčević [To94] and Komjáth [Ko25b].

View the LaTeX source

This page was last edited 30 December 2025.

A problem of Erdős, Hajnal, and Rado.

View the LaTeX source

This page was last edited 23 January 2026.

A problem of Erdős, Hajnal, and Rado.

View the LaTeX source

This page was last edited 23 January 2026.

A problem of Erdős and Hajnal. Hajnal [Ha71] proved this is true assuming the continuum hypothesis.

See also [592] for a similar problem concerning countable ordinals.

View the LaTeX source

This page was last edited 25 January 2026.

Laver [La82] proved the consistency of $\omega_2\to (\omega_12+1,\alpha)^2$ for all $\alpha<\omega_2$. Foreman and Hajnal [FoHa03] proved the consistency of $\omega_2\to (\omega_1^2+1,\alpha)^2$ for all $\alpha<\omega_2$.

View the LaTeX source

This page was last edited 23 January 2026.

Baumgartner [Ba89b] proved that, assuming a form of Martin's axiom, that $\omega_1\omega\to (\omega_1\omega, 3)^2$.

View the LaTeX source

This page was last edited 26 January 2026.

A problem of Erdős and Hajnal. The Erdős-Rado partition theorem [ErRa56] states that\[(2^{\kappa})^+ \to (\kappa^++1)_\kappa^2\]for every infinite cardinal $\kappa$.

(The right-hand side of the first and final statements are missing from the truncated photocopy available of [Va99], and it is possible they have been filled in incorrectly.)

View the LaTeX source

This page was last edited 23 January 2026.

A problem of Erdős and Hajnal. Shelah proved that a graph with either property can consistently exist.

View the LaTeX source

A problem of Erdős, Galvin, and Hajnal. The consistency of this was proved by Hajnal and Komjáth.

View the LaTeX source

This page was last edited 24 January 2026.