Regenerated from the community database (Apache-2.0), dated, and linked back to it from every problem. erdosproblems.com no longer shows statuses (Bloom's reasons); this is the database's record, not our verdict.
908 of 1221 statements are formalized in Lean (Formal Conjectures) · 107 carry an Erdős prize · 3 are independent of ZFC and 9 more can't be proved, or can't be disproved, from ZFC alone · “open” counts the computable and Lean-checked ones too.
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…
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] - indeed, there are infinitely many disjoint such…
**Erdős Problem 70**: Let \(\mathfrak{c}\) be the order type of the real numbers, let \(\beta\) be a countable ordinal, and let \(2 \le n < \omega\). Is it true that \(\mathfrak{c} \to (\beta, n)^3_2\)? Note: The cases \(n \le 3\) are…
If \(R(k)\) is the Ramsey number for \(K_k\), the minimal \(n\) such that every \(2\)-colouring of the edges of \(K_n\) contains a monochromatic copy of \(K_k\), then find the value of \[\lim_{k\to \infty}R(k)^{1/k}.\] This problem is #3…
Let \(R(k)\) be the Ramsey number for \(K_k\). Give a constructive proof that \(R(k) > C^k\) for some constant \(C > 1\). Equivalently, give an explicit construction of graphs on \(n\) vertices which contain no clique and no independent…
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 proper subgraphs are?…
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 a book of size \(m\), that is, an edge…
Is it true that, for all large \(n\), \(f(n + 1) \ge f(n)\)?
Let \(0 < \epsilon < 1\). Is it true that, if \(k\) is sufficiently large, then \[R(G) > (1-\epsilon)^k R(k)\] for every graph \(G\) with chromatic number \(\chi(G)=k\)? The restriction \(\epsilon < 1\) excludes negative bases in…
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…
ambiguous statement
There exists some constant \(c>0\) such that \[R(C_4,K_n) \ll n^{2-c}.\] The prize of $100 is offered in [Er78] for a proof or disproof. This problem is #17 in Ramsey Theory in the graphs problem collection.
Let \(\alpha\in[0,1/2)\) and \(n,t\geq 1\). Let \(F^{(t)}(n,\alpha)\) be the smallest \(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…
Let \(\alpha > 0\) and \(n \geq 1\). Let \(F(n,\alpha)\) be the largest \(k\) such that there exists some 2-colouring of the edges of \(K_n\) in which any induced subgraph \(H\) on at least \(k\) vertices contains more than…
Burr-Erdős conjecture
The Burr-Erdős conjecture: 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.\] Solved by Lee [Le17], who proved that \(R(H) \leq 2^{2^{O(d)}}n\). This problem is…
Prove that \[R(4,k) \gg \frac{k^3}{(\log k)^{O(1)}}.\] This is true, and was proved by Mattheus and Verstraëte [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…
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?
In any \(2\)-colouring of \(\mathbb{R}^2\), for all but at most one triangle \(T\) (up to congruence), there is a monochromatic congruent copy of \(T\). The colouring is arbitrary. No measurability is assumed. ≅ compares vertices with the…
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…
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.\]
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}.\] There is no finite limit:…
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 with distance 1?
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, "On Partitions of 𝔼ⁿ", Journal of Combinatorial Theory, Series A 28, 89-91 (1980). (See…
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\subseteq \{2,\ldots,n\}\) such that \(\binom{X}{2}\) is…
Let \(S\subset \mathbb{R}^2\) be such that no two points in \(S\) are distance \(1\) apart. Must the complement of \(S\) contain four points which form a unit square? The answer is yes, proved by Juhász [Ju79], who proved more generally…
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\)? The…
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…
Hadwiger-Nelson problem
The Hadwiger–Nelson problem asks: How many colors are required to color the plane such that no two points at distance 1 from each other have the same color? It is known that \(6 \leq \chi(\mathbb{R}^2) \leq 7\); see…
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? Asked by Graham…
Show that \[R(3,k+1)-R(3,k)\to\infty\] as \(k\to \infty\). A problem of Erdős and Sós. This problem is #8 in Ramsey Theory in the graphs problem collection.
Let \(m\) be sufficiently large and let \(G\) be a graph with \(m\) edges and no isolated vertices. Is the Ramsey number \(R(G)\) maximised when \(G\) is 'as complete as possible'? That is, if \(m=\binom{n}{2}+t\) edges with…
Let \(G\) be a graph with no isolated vertices and \(m\) edges. Is it true that \[R(G) \leq 2^{O(m^{1/2})}?\] This is true, and was proved by Sudakov [Su11]. This problem is #11 in Ramsey Theory in the graphs problem collection.
If \(T\) is a tree on \(n\) vertices then \[R(T) \leq 2n-2.\] This problem is #14 in Ramsey Theory in the graphs problem collection. Solved: the bound follows from the Erdős–Sós theorem (Erdős problem 548) by the pigeonhole principle, as…
If \(T\) is a tree which is a bipartite graph with \(k\) vertices in one class and \(2k\) vertices in the other class then \[R(T)=4k-1.\] This is false: Norin, Sun, and Zhao [NSZ16] have proved that if \(T\) is the union of two stars on…
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…
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. This problem is #18 in Ramsey Theory in the graphs problem collection.
Determine the Ramsey number \[R(C_4, S_n),\] where \(S_n=K_{1,n}\) is the star on \(n+1\) vertices. A problem of Burr, Erdős, Faudree, Rousseau, and Schelp [BEFRS89]. This problem is #19 in Ramsey Theory in the graphs problem collection.
Let \(R_k(G)\) be the least \(m\) such that every \(k\)-colouring of the edges of \(K_m\) contains a monochromatic copy of \(G\). Determine \(R_k(C_{2n})\).
Erdős Problem 556 (Bondy–Erdős): for all \(n \ge 4\), \[R(C_n; 3) \le 4n - 3.\] The case \(n = 3\) is excluded since \(R(K_3; 3) = 17\).
Let \(R_k(G)\) 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_k(T)\leq kn+O(1)\] for any tree \(T\) on \(n\) vertices? The answer is yes, with…
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…
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…
F(s,n) is the disjoint union of the stars \(K_{1,n_i}\). The vertex \((i,0)\) is the center of component \(i\); its other \(n_i\) vertices are leaves. -/ local notation "F(" s ", " n ")" => fromRel (fun (u v : Σ i : Fin s, Fin (n i + 1)) ↦…
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…
Let \(F(n,\alpha)\) denote the smallest \(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…
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 complete \(3\)-uniform hypergraph on \(n\) vertices. Is there some…
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: if \(G\) is sparse (every induced subgraph on…
**Erdős Problem 567 (Q3)** Is \(Q_3\) (the 3-dimensional hypercube) Ramsey size linear?
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…
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? This problem is #34 in Ramsey Theory in the graphs problem collection.
Let \(k\geq 3\). Is it true that, if \(m\) is sufficiently large, for any graph \(H\) on \(m\) edges without isolated vertices, \[R(C_k,H) \leq 2m+\left\lfloor\frac{k-1}{2}\right\rfloor?\] This was proved for even \(k\) by Erdős, Faudree,…
Does there exist a graph \(G\) 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…
Let \(α\) be the infinite ordinal \(\omega^{\omega}\). It was proved by Chang [Ch72] that any red/blue colouring of the edges of \(K_α\) there is either a red \(K_α\) or a blue \(K_3\).
Let \(α\) be the infinite ordinal \(\omega^{\omega^2}\). Is it true that any red/blue colouring of the edges of \(K_α\) there is either a red \(K_α\) or a blue \(K_3\)? This is true and was proved independently by Schipperus [Sc10] and…
Determine which countable ordinals \(β\) have the property that, if \(α = \omega^β\), then in any red/blue colouring of the edges of \(K_α\) there is either a red \(K_α\) or a blue \(K_3\).
**Erdős Problem 596** (Erdős–Hajnal, [Er87]). For which graph pairs \((G_1, G_2)\) is it true that (1) for every \(n \geq 1\) there is a graph \(H\) without a \(G_1\) such that any \(n\)-colouring of \(H\)'s edges contains a monochromatic…
**Erdős Problem 598:** 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…
Let \(f(n)\) be the minimal \(m\) 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 there exist some constant \(c > 0\) such that for all sufficiently large \(n\), if \(G\) is a graph with \(n\) vertices and at least \((1/8 - c)n^2\) edges then \(G\) must contain either a \(K_4\) or an independent set on at least…
Suppose \(G\) is a graph on \(n\) vertices which contains no complete graph or independent set on \(\gg \log n\) many vertices. Must \(G\) contain \(\gg n^{5/2}\) induced subgraphs which pairwise differ in either the number of vertices or…
Is it true that if the edges of \(K_n\) are 2-coloured then there are at most \(n^2/4\) many edges which do not occur in a monochromatic triangle? Solved by Erdős, Rousseau, and Schelp for large \(n\), but unpublished. Alon has observed…
If ℕ is \(2\)-coloured then there must exist a monochromatic three-term arithmetic progression \(x,x+d,x+2d\) such that \(d>x\). This was first proved by Brown and Landman [BrLa99], who in fact show that this is always possible with…
Let \(p, q \geq 1\) be fixed integers. Define \(H(n) = H(n; p, q)\) to be the largest \(m\) such that any graph on \(n\) vertices where every set of \(p\) vertices spans at least \(q\) edges must contain a complete graph on \(m\) vertices.…
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\). Is it true…
If \(G\) is a graph on \(n\) vertices which has no two adjacent vertices of degree \(\geq 3\) then \[R(G)\ll n,\] where the implied constant is absolute. A problem of Burr and Erdős. Solved in the affirmative by Alon [Al94].
If \(G\) is a graph on \(n\) vertices containing no independent set on \(>n^{1/2}\) vertices then there is a set of \(\leq n^{1/2}\) vertices containing \(\gg n^{1/2}\log n\) edges. Proved by Alon [Al96b].
Does there exist some \(\epsilon>0\) such that, for all sufficiently large \(n\), there exists a graph \(G\) on \(n\) vertices with at least \(\epsilon n^2\) edges whose edges can be coloured with \(n\) colours so that every \(C_4\)…
\(R(n)\) denotes the diagonal Ramsey number \(R(n,n)\), i.e., hypergraphRamsey 2 n. -/ local notation "R" => hypergraphRamsey 2 /-- Is it true that \(\frac{R(n+1)}{R(n)}\geq 1+c\) for some constant \(c>0\), for all large \(n\)?
Let \(A=\{n_1<n_2<\cdots\}\subset \mathbb{N}\) be a lacunary sequence (so there exists some \(\epsilon>0\) with \(n_{k+1}\geq (1+\epsilon)n_k\) for all \(k\)). Is it true that there must exist a finite colouring of \(\mathbb{N}\) with no…
Is there a function \(f(n)\) and a \(k\) such that in any \(k\)-colouring of the integers there exists a sequence \(a_1 < a_2 < \cdots\) such that \(a_n < f(n)\) for infinitely many \(n\) and the set \[\left\{ \sum_{i \in S} a_i :…
Let \(S \subseteq \mathbb{R}\) be a set containing no solutions to \(a + b = c\). Must there be a set \(A \subseteq \mathbb{R} \setminus S\) of cardinality continuum such that \(A + A \subseteq \mathbb{R}\setminus S\)?
Erdős asks in [Er75b] if for every 2-coloring of ℝ, there is an uncountable set \(A ⊆ ℝ\) such that all sums \(a + b\) for \(a, b ∈ A, a ≠ b\) have the same colour. In [Ko16] Péter Komjáth constructed a counterexample. The same result was…
Let \(k,r\geq 2\). Does there exist a set \(A\subseteq \mathbb{N}\) that contains no non-trivial arithmetic progression of length \(k+1\), yet in any \(r\)-colouring of \(A\) there must exist a monochromatic non-trivial arithmetic…
For any fixed \(s\geq 3\), \[R(s,k) \gg \frac{k^{s-1}}{(\log k)^c}\] for some constant \(c=c(s)>0\). According to Chung and Graham [ChGr98] this was first conjectured by Erdős in 1947. Proved by Bradač [Br26], with \(c=2s-4\). The linked…
Let \(R(k,l)\) be the Ramsey number, so the minimal \(n\) such that every graph on at least \(n\) vertices contains either a \(K_k\) or an independent set on \(l\) vertices. Prove, for fixed \(k\geq 3\), that \[\lim_{l\to…
If \(R(k)\) is the Ramsey number for \(K_k\), the minimal \(n\) such that every \(2\)-colouring of the edges of \(K_n\) contains a monochromatic copy of \(K_k\), then \[\frac{R(k)}{k2^{k/2}}\to \infty.\] In [Er93] Erdős offers…
Let \(R(k,l)\) be the usual Ramsey number: the smallest \(n\) such that if the edges of \(K_n\) are coloured red and blue then there exists either a red \(K_k\) or a blue \(K_l\). Prove the existence of some \(c>0\) such that \[\lim_{k\to…
Let \(k\geq 3\). Does there exist a finite set \(A\subset \mathbb{R}^2\) such that, in any \(2\)-colouring of \(A\), there exists a line which contains at least \(k\) points from \(A\), and all the points of \(A\) on the line have the same…
The anti-Ramsey number \(\mathrm{AR}(n,G)\) is the maximum possible number of colours in which the edges of \(K_n\) can be coloured without creating a rainbow copy of \(G\) (i.e. one in which all edges have different colours). Let \(C_k\)…
**Prikry–Mills counterexample** (key lemma): There exists a 2-colouring \(f\) of a set of cardinality \(\aleph_1\) cubed such that no countable box \(A_1 \times B_1 \times C_1\) is monochromatic. This is the unpublished result of Prikry…
**Erdős Problem 1167.** Let \(r \geq 2\) be finite, \(\gamma \geq 2\), and \(\lambda\) be an infinite cardinal. Let \(\kappa_\alpha > r\) be cardinals for all \(\alpha < \gamma\). Is it true that \[2^\lambda \to (\kappa_\alpha + 1)_{\alpha…
Let \(G\) be a graph with chromatic number \(\aleph_1\). Is it true that there is a colouring of the edges with \(\aleph_1\) many colours such that, in any countable colouring of the vertices, there exists a vertex colour containing all…
If \(\mathbb{N}\) is \(2\)-coloured, must there exist an infinite set \(A=\{a_1<a_2<\cdots\}\) such that all expressions of the shape \[\sum_{j=1}^{k}\prod_{i\in S_j}a_i,\] for \(k\geq 1\) and pairwise disjoint nonempty finite sets of…
Is it true that in any 2-colouring of \(\mathbb{N}\) there exists an infinite set \(A\) such that all elements of \(A+A\) are the same colour? A conjecture of Owings [Ow74].
Let \((n_k)\) be an increasing sequence of integers such that \(2^{\aleph_{n_k}}\) is strictly increasing, and \(2^{\aleph_{n_0}} > \aleph_\omega\). Is it true that \[\sum_k 2^{\aleph_{n_k}} \to (\aleph_\omega)^2?\] Here…