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.
Prove an asymptotic formula for \(r_k(N)\), the largest possible size of a subset of \(\{1, \dots, N\}\) that does not contain any non-trivial \(k\)-term arithmetic progression. That is, find \(f_k\) with \(r_k(N) / f_k(N) \to 1\) as…
If \(A \subset \mathbb{N}\) has \(\sum_{n \in A}\frac 1 n = \infty\), then must \(A\) contain arbitrarily long arithmetic progressions? Yes. This was proved by an internal OpenAI model in September 2026 [OAI26]; see the linked Lean proof.
sunflower conjecture
Is it true that \(f(n,k) < c_k^n\) for some constant \(c_k>0\) and for all \(n > 0\)?
Is it true that, for every \(\varepsilon > 0\), \(h(N) = \sqrt N + O_{\varepsilon}(N^\varepsilon)\)
Does every finite graph with minimum degree at least \(3\) contain a cycle of length \(2^k\) for some \(k \geq 2\)?
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\).
Let \(Y(x)\) be the maximal \(y\) such that there exists a choice of congruence classes \(a_p\) for all primes \(p\leq x\) such that every integer in \([1,y]\) is congruent to at least one of the \(a_p\pmod{p}\). Give good estimates for…
Let \(A\subset\mathbb{N}\) be an infinite Sidon set. Is it true that \[\liminf_{x\to \infty} \frac{\lvert A\cap [1,x]\rvert}{x^{1/2}}(\log x)^{1/2}=0?\] Here \(x\) runs over \(\mathbb{N}\) and the \(\liminf\) is taken in ℝ≥0∞, so that it…
If \(G\) is an edge-disjoint union of \(n\) copies of \(K_n\), then is \(\chi(G) = n\)?
If \(A ⊆ \mathbb{N}\) is such that \(A + A\) contains all but finitely many integers then \(\limsup 1_A ∗ 1_A(n) = \infty\).
Is there an infinite Sidon set \(A\subset \mathbb{N}\) such that \(\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}\) for all \(\varepsilon > 0\)?
For what functions \(g(N) → \infty\) is it true that \[\lvert A\cap \{1,\ldots,N\}\rvert \gg \frac{N^{1/2}}{g(N)}\] implies \(\limsup 1_A\ast 1_A(n)=\infty\)?
Let \(A \subset \mathbb{N}\) be an infinite set such that the triple sums \(a+b+c\) are all distinct for \(a,b,c \in A\) (aside from the trivial coincidences). Is it true that \[\liminf_{N \to \infty} \frac{\lvert A \cap…
Is there and \(A \subset \mathbb{N}\) is such that \[\lim_{n\to \infty}\frac{1_A\ast 1_A(n)}{\log n}\] exists and is \(\ne 0\)?
Erdős distance problem
Erdős [Er46] asked whether every set of \(n\) distinct points in \(\mathbb{R}^2\) determines \(\gg \frac{n}{\sqrt{\log n}}\) many distinct distances.
'Happy Ending' problem
Let \(f(n)\) be minimal such that any \(f(n)\) points in \(ℝ^2\), no three on a line, contain \(n\) points which form the vertices of a convex \(n\)-gon. Prove that \(f(n) = 2^{n-2} + 1\).
Asserts that for any number of colors r and any progression length k, there always exists some number N large enough to guarantee a monochromatic arithmetic progression. In other words, the set monoAP_guarantee_set is non-empty. This is…
Does this imply that \[ \liminf \frac{|A \cap [1,x]|}{x} = 0? \]
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…
What is \(\mathrm{ex}_3(n,K_4^3)\)? That is, the largest number of \(3\)-edges which can placed on \(n\) vertices so that there exists no \(K_4^3\), a set of 4 vertices which is covered by all 4 possible \(3\)-edges. See also…
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…
**Erdős Problem 593 (\\(500)**: Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number \)> \aleph_0…
pinned distance problem
Given \(n\) distinct points \(A\subset\mathbb{R}^2\), must there be a point \(x\in A\) such that \[\#\{ d(x,y) : y \in A\} \gg n^{1-o(1)}?\] This is the pinned distance problem, a stronger form of Problem 89. Here \(n^{1-o(1)}\) means: for…
Determine, for any \(k>r>2\), the limiting value as \(n\to\infty\) of \[\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}},\] where \(\mathrm{ex}_r(n,K_k^r)\) is the largest number of \(r\)-edges which can placed on \(n\) vertices so that there…
Is it true that, for every bipartite graph \(G\), there exists some \(\alpha\in [1,2)\) and \(c>0\) such that \[\mathrm{ex}(n;G)\sim cn^\alpha?\] The condition that \(G\) have at least two edges excludes degenerate forbidden graphs whose…
Collatz conjecture
The Collatz conjecture states that for any positive integer \(n\), there exists a natural number \(m\) such that the \(m\)-th term of the sequence is 1.
Schoenberg [Sch38] proved that the asymptotic distribution function of \(\varphi(n)/n\) exists. That is, for any \(c \in [0, 1]\), the proportion of integers \(n \le N\) satisfying \(\varphi(n)/n < c\) approaches a limit as…
sum-product problem
Let \(A\) be a finite set of integers. Is it true that for every \(\epsilon>0\) \(\max( \lvert A+A\rvert,\lvert AA\rvert)\gg_\epsilon \lvert A\rvert^{2-\epsilon}?\)
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…
If \(p(z) \in \mathbb{C}[z]\) is a monic polynomial of degree \(n\), is the length of the curve \(\{z \in \mathbb{C} : \lvert p(z)\rvert = 1\}\) maximised when \(p(z) = z^n - 1\)? We require \(n \geq 1\). For \(n = 0\) the only monic…
Let G be a graph with n vertices such that every induced subgraph on ≥ \(n/2\) vertices has more than \(n^2/50\) edges. Must G contain a triangle?
**Erdős Problem 595 (\\(250)**: Is there an infinite graph \)G\( which contains no \)K_4$ and is not the union of countably many triangle-free graphs? A problem of Erdős and Hajnal [Er87].
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…
Let \(Q_n\) be the \(n\)-dimensional hypercube graph (so that \(Q_n\) has \(2^n\) vertices and \(n2^{n-1}\) edges). Is it true that every subgraph of \(Q_n\) with \[\geq \left(\frac{1}{2}+o(1)\right)n2^{n-1}\] many edges contains a \(C_4\)?
Does every convex polygon have a vertex with no other 4 vertices equidistant from it?
For sufficiently large n, is it the case that any set of n points with minimum distance \(1\) that minimizes diameter must contain an equilateral triangle of side length 1?
Given \(n\) points in \(\mathbb{R}^2\), no five of which are on a line, the number of lines containing four points is \(o(n^2)\).
Given \(n\) points in \(\mathbb{R}^2\) the number of distinct unit circles containing at least three points is \(o(n^2)\).
Erdős similarity problem
Let \(A \subseteq \mathbb{R}\) be an infinite set. Must there be a set \(E \subseteq \mathbb{R}\) of positive measure which does not contain any set of the shape \(a * A + b\) for some \(a,b \in \mathbb{R}\) and \(a \neq 0\)?
Is it true that \(f(N)\sim N^{1/3}\)? Originally asked to Erdős by Bose. This is discussed in problem C11 of Guy's collection [Gu04].
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 \(f_k(n)\) be minimal such that if \(n\) points in \(\mathbb{R}^2\) have no \(k+1\) points on a line then there must be at most \(f_k(n)\) many lines containing at least \(k\) points. Is it true that \[f_k(n) = o(n^2)\] for…
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…
Are there, for all large \(n\), some points \(x_1,\ldots,x_n,y_1,\ldots,y_n\in \mathbb{R}^2\) such that the number of distinct distances \(d(x_i,y_j)\) is \[o\left(\frac{n}{\sqrt{\log n}}\right)?\] We require all \(2n\) points to be…
Let \(\tau(n)\) count the number of divisors of \(n\). Is there some \(n > 24\) such that \[ \max_{m < n}(m + \tau(m)) \leq n + 2? \]
Let \(f(n)\) be minimal such that in \((n,n+f(n))\) there exist distinct integers \(a_1,\ldots,a_n\) such that \(k\mid a_k\) for all \(1\leq k\leq n\). Obtain an asymptotic formula for \(f(n)\).
Let \(f(n,m)\) be minimal such that \((m,m+f(n,m))\) contains distinct integers \(a_1,\ldots,a_n\) with \(k \mid a_k\) for \(1 \leq k \leq n\). Prove that \(\max_m f(n,m) \leq n^{1+o(1)}\).
Are there any odd weird numbers?
unitary perfect numbers
Are there only finitely many unitary perfect numbers?