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.
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.
unit distance problem
Does every set of \(n\) distinct points in \(\mathbb{R}^2\) contain at most \(n^{1+O(\frac{1}{\log\log n})}\) many pairs which are distance \(1\) apart? This was…
Suppose \(A\subset \mathbb{R}^2\) has \(\lvert A\rvert=n\) and minimises the number of distinct distances between points in \(A\). Prove that for large \(n\) there are at least two (and probably many) such \(A\) which are non-similar.
If \(n\) distinct points in \(\mathbb{R}^2\) form a convex polygon then they determine at least \(\lfloor \frac{n}{2}\rfloor\) distinct distances. Solved by Altman [Al63].
Suppose \(n\) points in \(\mathbb{R}^2\) determine a convex polygon and the set of distances between them is \(\{u_1,\ldots,u_t\}\). Suppose \(u_i\) appears as the distance between \(f(u_i)\) many pairs of points. Then \[\sum_i f(u_i)^2…
Let \(x_1,\ldots,x_n\in\mathbb{R}^2\) determine the set of distances \(\{u_1,\ldots,u_t\}\). Suppose \(u_i\) appears as the distance between \(f(u_i)\) many pairs of points. Then for all \(\epsilon>0\) \[\sum_i f(u_i)^2 \ll_\epsilon…
If \(n\) points in \(\mathbb{R}^2\) form a convex polygon then there are \(O(n)\) many pairs which are distance \(1\) apart.
Does every convex polygon have a vertex with no other 4 vertices equidistant from it?
Let \(h(n)\) be such that any \(n\) points in \(\mathbb{R}^2\), with no three on a line and no four on a circle, determine at least \(h(n)\) distinct distances. Does \(h(n)/n\to \infty\)?
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?
Is the diameter of \(A\) at least \(Cn\) for some constant \(C > 0\)?
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)\).
Let \(c > 0\) and let \(h_c(n)\) be such that for any \(n\) points in \(\mathbb{R}^2\) with at least \(cn^2\) lines that each contain more than three of the points, some line contains \(h_c(n)\) of the points. Is it true that, for fixed…
Let \(h(n)\) count the number of incongruent sets of \(n\) points in \(\mathbb{R}^2\) which minimise the diameter subject to the constraint that \(d(x,y)\geq 1\) for all points \(x\neq y\). Is it true that \(h(n)\to \infty\)?
Given \(n\) points in \(\mathbb{R}^2\) the number of distinct unit circles containing at least three points is \(o(n^2)\).
Let \(A,B\subset \mathbb{R}^2\) be disjoint sets of size \(n\) and \(n-3\) respectively, with not all of \(A\) contained on a single line. Is there a line which contains at least two points from \(A\) and no points from \(B\)? This has…
'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\).
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…
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 \(S \subseteq \mathbb{Z}^3\) be a finite set and let \(A = \lbrace a_1, a_2, \ldots \rbrace\) be an infinite \(S\)-walk, so that \(a_{i+1} - a_i \in S\) for all \(i\). Must \(A\) contain three collinear points? Cambie and Kalviainen…
Let \(A\) be a finite collection of \(d\geq 4\) non-parallel lines in \(\mathbb{R}^2\) such that there are no points where at least four lines from \(A\) meet. Must there exist a 'Gallai triangle' (or 'ordinary triangle'): three lines from…
Let \(f(n)\) be the sharp guarantee such that, for any \(n\) points in \(\mathbb R^2\), not all on a line, there are at least \(f(n)\) lines which contain exactly two points (called ordinary lines). Does \(f(n)\to\infty\)? That…
Let \(1\leq k<n\). Given \(n\) points in \(\mathbb{R}^2\), at most \(n-k\) on any line, there are \(\gg kn\) many lines which contain at least two points. Solved by Beck [Be83] and Szemerédi and Trotter [SzTr83].
Is there a dense subset of ℝ^2 such that all pairwise distances are rational?
Let \(n \geq 4\). Are there \(n\) points in \(\mathbb{R}^2\), no three on a line and no four on a circle, such that all pairwise distances are integers?
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…
Does there exist \(S\subseteq \mathbb{R}^2\) such that every set congruent to \(S\) (that is, \(S\) after some translation and rotation) contains exactly one point from \(\mathbb{Z}^2\)? An old question of Steinhaus. Erdős was 'almost…
If \(A\subseteq \mathbb{R}^d\) is any set of \(2^d+1\) points then some three points in \(A\) determine an obtuse angle. The general case was proved by Danzer and Gr\"{u}nbaum [DaGr62].
Is there some \(c > 0\) such that every measurable \(A \subseteq \mathbb{R}^2\) of measure \(\geq c\) contains the vertices of a triangle of area 1?
Let \(A\subseteq \mathbb{R}^2\) be a measurable set with infinite measure. Must \(A\) contain the vertices of an isosceles trapezoid of area \(1\)? What about an isosceles triangle, or a right-angled triangle, or a cyclic quadrilateral, or…
What is the size of the largest \(A\subseteq \mathbb{R}^n\) such that there are only two distinct distances between elements of \(A\)? That is, \[\# \{ \lvert x-y\rvert : x\neq y\in A\} = 2.\] Asked to Erdős by Coxeter. Bannai, Bannai, and…
What is the size of the largest \(A \subseteq \mathbb{R}^n\) such that every three points from \(A\) determine an isosceles triangle? That is, for any three points \(x\), \(y\), \(z\) from \(A\), at least two of the distances \(|x - y|\),…
Blumenthal's problem
**Erdős–Szekeres (1960).** For \(n \ge 3\), \(\alpha_{2^n} = \pi\left(1 - \frac{1}{n}\right)\).
Borsuk's problem
**Erdős Problem 505** (disproved). Borsuk's conjecture is false for sufficiently large \(n\): there exists a dimension \(n\) and a bounded set \(S \subseteq \mathbb{R}^n\) with at least two points that cannot be covered by \(n + 1\)…
Heilbronn's triangle problem
Let \(\alpha(n)\) be such that every set of \(n\) points in the unit disk contains three points which determine a triangle of area at most \(\alpha(n)\). Estimate \(\alpha(n)\).
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…
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…
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…
A triangle whose side lengths and angles are integrally independent is cuttable only into a non-zero square number of congruent triangles. This is proved in [So09c].
Let \(x_1,\ldots,x_n\in \mathbb{R}^2\) and let \(R(x_i)=\#\{ \lvert x_j-x_i\rvert : j\neq i\}\), where the points are ordered such that \[R(x_1)\leq \cdots \leq R(x_n).\] Let \(\alpha_k\) be minimal such that, for all large enough \(n\),…
Let \(x_1,\ldots,x_n\in \mathbb{R}^2\) and let \(R(x_i)=\#\{ \lvert x_j-x_i\rvert : j\neq i\}\), where the points are ordered such that \[R(x_1)\leq \cdots \leq R(x_n).\] Let \(g(n)\) be the maximum number of distinct values the \(R(x_i)\)…
ambiguous statement
Let \(x_1,\ldots,x_n\in \mathbb{R}^2\) be such that no circle whose centre is one of the \(x_i\) contains three other points. Are there at least \[(1+c)\frac{n}{2}\] distinct distances determined between the \(x_i\), for some constant…
Is it true that if \(A\subset \mathbb{R}^2\) is a set of \(n\) points such that every subset of \(3\) points determines \(3\) distinct distances (that is, \(A\) has no isosceles triangles, degenerate ones included) then \(A\) determines at…
Is there a set of \(n\) points in \(\mathbb{R}^2\) such that every subset of \(4\) points determines at least \(3\) distances, yet the total number of distinct distances is \(\ll \frac{n}{\sqrt{\log n}}\)? There does exist such a set: a…
ambiguous statement
Let \(x_1, \ldots, x_n \in \mathbb{R}^3\) be the vertices of a convex polyhedron. Are there at least \[(1 - o(1)) \frac{n}{2}\] many distinct distances between the \(x_i\)? The \((1 - o(1)) \frac{n}{2}\) lower bound is formalised as: for…
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…
ambiguous statement
Is it true that the number of incongruent sets of \(n\) points in \(\mathbb{R}^2\) which maximise the number of unit distances tends to infinity as \(n\to\infty\)? The actual maximal number of unit distances is the subject of [Erdős…
orchard problems
Let \(A\subseteq \mathbb{R}^d\) be a set of \(n\) points such that all pairwise distances differ by at least \(1\). Is the diameter of \(A\) at least \((1+o(1))n^2\)? The quantifiers in the source are ambiguous. Following the remarks on…
Does \(\chi(G_n)\) grow exponentially in \(n\)? Yes: Frankl and Wilson [FrWi81] proved an exponential lower bound and Larman and Rogers [LaRo72] proved an exponential upper bound. Here exponential growth means that there are constants…
Erdős asked whether every \(n\)-point set in \(\mathbb{R}^6\) spans at most \((1/27 + o(1)) n^3\) unit equilateral triangles. Clemen, Dumitrescu, and Liu [CDL25b] proved the stronger any-size statement \(T_6(n) = (1/27 + o(1)) n^3\). The…
Let \(A\subset \mathbb{R}^2\) be a set of \(n\) points. Can there be \(\gg n\) many distinct distances each of which occurs for more than \(n\) many pairs from \(A\)? The answer is yes: Bhowmick [Bh24] constructs a set of \(n\) points in…
What is the supremum of the set of admissible numbers?
Let \(c(n)\) be minimal such that if \(k\geq c(n)\) then the \(n\)-dimensional unit cube can be decomposed into \(k\) homothetic \(n\)-dimensional cubes. Give good bounds for \(c(n)\) — in particular, is it true that \(c(n)\gg n^n\)? The…
Let \(t(n)\) be the minimum number of points in \(\{1,\ldots,n\}^2\) such that the \(\binom{t}{2}\) lines determined by these points cover all points in \(\{1,\ldots,n\}^2\). Estimate \(t(n)\). In particular, is it true that \(t(n)=o(n)\)?…
**Erdős Problem 846** Let A ⊂ ℝ² be an infinite set for which there exists some ϵ>0 such that in any subset of A of size n there are always at least ϵn with no three on a line. Is it true that A is the union of a finite number of sets…
Erdős-Mordell inequality
If \(A,B,C\in \mathbb{R}^2\) form a triangle and \(P\) is a point in the interior then, if \(N\) is where the perpendicular from \(P\) to \(AB\) meets the triangle, and similarly for \(M\) and \(L\), \[…
Let \(A\subset \mathbb{R}^2\) be a finite set of size \(n\), and let \(\{d_1,\ldots,d_k\}\) be the set of distances determined by \(A\). Let \(f(d)\) be the multiplicity of \(d\), that is, the number of unordered pairs from \(A\) of…
Let \(A\subseteq \mathbb{R}^2\) be a set of size \(n\) and let \(\{d_1,\ldots,d_k\}\) be the set of distinct distances determined by \(A\). Let \(f(d)\) be the number of times the distance \(d\) is determined, ordered so that…
If \(n\) distinct points in \(\mathbb{R}^2\) form a convex polygon then some vertex has at least \(\lfloor\frac{n}{2}\rfloor\) different distances to other vertices.
Can a finite set of disjoint unit segments in a unit square be maximal? Solved affirmatively by [Da85], who gave an explicit construction. This was formalized in Lean by Alexeev using Aristotle and ChatGPT.
Let \(A\subset \mathbb{R}^2\) be a set of \(n\) points with no three on a line. Does \(A\) determine at least \(\lfloor n/2\rfloor\) distinct distances?
Let \(d\geq 3\), and let \(f_d(n)\) be the minimal \(m\) such that every set of \(n\) points in \(\mathbb{R}^d\) determines at least \(m\) distinct distances. Estimate \(f_d(n)\) - in particular, is it true that…
contact number problem
Let \(f_d(n)\) be the minimal \(m\) such that any set of \(m\) points in \(\mathbb{R}^d\) contains a set of \(n\) points for which any two determined distances are distinct. Erdős Problem 1088 asks to estimate \(f_d(n)\). In particular, is…
Let \(g_d(n)\) be minimal such that every collection of \(g_d(n)\) points in \(\mathbb{R}^d\) determines at least \(n\) many distinct distances. Estimate \(g_d(n)\). In particular, does \[\lim_{d \to \infty} \frac{g_d(n)}{d^{n-1}}\] exist?…
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…
If \(C_1,\ldots,C_n\) are circles in \(\mathbb{R}^2\) with radii \(r_1,\ldots,r_n\) such that no line disjoint from all the circles divides them into two non-empty sets then the circles can be covered by a circle of radius \(r=\sum r_i\).…
Let \(P_d(n)\) be such that in any set of \(n\) points in \(\mathbb{R}^d\) there exist at least \(P_d(n)\) many points which do not contain an isosceles triangle. Estimate \(P_d(n)\) - in particular, is it true that \[P_2(n)<n^{1-c}\] for…