Erdős · problems
OEIS index →← the campaignThe Erdős problems.
104 of 1217 · 34 sealed
#188What 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$?geometry · 2 Vela attempts (improved bound) · AI tried (unverified) · N/A#100Let $A$ be a set of $n$ points in $\mathbb{R}^2$ such that all pairwise distances are at least $1$ and if two distinct distances differ then they differ by at least $1$. Is the diameter of $A$ $\gg n$…geometry · 1 Vela attempt (honest null) · AI tried (unverified) · N/A#213Let $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?geometry · 1 Vela attempt (honest null) · AI tried (unverified) · N/A#89Does every set of $n$ distinct points in $\mathbb{R}^2$ determine $\gg n/\sqrt{\log n}$ many distinct distances?Erdős distance problem · geometry · AI tried (unverified) · A186704,A131628#90Does every set of $n$ distinct points in $\mathbb{R}^2$ contain at most $n^{1+O(1/\log\log n)}$ many pairs which are distance 1 apart?unit distance problem · geometry · solved · AI tried (unverified) · A186705#91Let $n$ be a sufficiently large integer. Suppose $A\subset \mathbb{R}^2$ has $\lvert A\rvert=n$ and minimises the number of distinct distances between points in $A$. Prove that there are at least two …geometry · AI tried (unverified) · A186704,possible#92Let $f(n)$ be maximal such that there exists a set $A$ of $n$ points in $\mathbb{R}^2$ in which every $x\in A$ has at least $f(n)$ points in $A$ equidistant from $x$.Is it true that $f(n)\leq n^{o(1)}…geometry · solved · AI tried (unverified) · possible#96If $n$ points in $\mathbb{R}^2$ form a convex polygon then there are $O(n)$ many pairs which are distance $1$ apart.geometry · AI tried (unverified) · possible#97Does every convex polygon have a vertex with no other $4$ vertices equidistant from it?geometry · AI tried (unverified) · N/A#98Let $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$?geometry · AI tried (unverified) · possible#99Let $A\subseteq\mathbb{R}^2$ be a set of $n$ points with minimum distance equal to 1, chosen to minimise the diameter of $A$. If $n$ is sufficiently large then must there be three points in $A$ which …geometry · AI tried (unverified) · N/A#101Given $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)$.geometry · AI tried (unverified) · A006065,possible#107Let $f(n)$ be minimal such that any $f(n)$ points in $\mathbb{R}^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$.'Happy Ending' problem · geometry · AI tried (unverified) · A000051#193Let $S\subseteq \mathbb{Z}^3$ be a finite set and let $A=\{a_1,a_2,\ldots,\}\subset \mathbb{Z}^3$ be an infinite $S$-walk, so that $a_{i+1}-a_i\in S$ for all $i$. Must $A$ contain three collinear poin…geometry · AI tried (unverified) · A231255#212Is there a dense subset of $\mathbb{R}^2$ such that all pairwise distances are rational?geometry · AI tried (unverified) · N/A#352Is 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?geometry · AI tried (unverified) · N/A#503What is the size of the largest $A\subseteq \mathbb{R}^d$ 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 dis…geometry · AI tried (unverified) · A175769#507Let $\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)$.Heilbronn's triangle problem · geometry · AI tried (unverified) · N/A#508What is the chromatic number of the plane? That is, what is the smallest number of colours required to colour $\mathbb{R}^2$ such that no two points of the same colour are distance $1$ apart?Hadwiger-Nelson problem · geometry · AI tried (unverified) · N/A#633Classify those triangles which can only be cut into a square number of congruent triangles.geometry · solved · AI tried (unverified) · N/A#653Let $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…geometry · AI tried (unverified) · possible#655Let $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 th…ambiguous statement · geometry · AI tried (unverified) · possible#659Is 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}}?\]geometry · solved · AI tried (unverified) · possible#757Let $A\subset \mathbb{R}$ be a set of size $n$ such that every subset $B\subseteq A$ with $\lvert B\rvert =4$ has $\lvert B-B\rvert\geq 11$. Find the best constant $c>0$ such that $A$ must always …geometry · AI tried (unverified) · possible#982If $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.geometry · AI tried (unverified) · A004526#1071Is there a finite set of unit line segments (rotated and translated copies of $(0,1)$) in the unit square, no two of which intersect, which are maximal with respect to this property?Is there a region …geometry · solved · AI tried (unverified) · N/A#1082Let $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? In fact, must there exist a single point from which the…geometry · AI tried (unverified) · possible#1084Let $f_d(n)$ be minimal such that in any collection of $n$ points in $\mathbb{R}^d$, all of distance at least $1$ apart, there are at most $f_d(n)$ many pairs of points which are distance $1$ apart. E…contact number problem · geometry · AI tried (unverified) · A045945,possible#1085Let $f_d(n)$ be minimal such that, in any set of $n$ points in $\mathbb{R}^d$, there exist at most $f_d(n)$ pairs of points which distance $1$ apart. Estimate $f_d(n)$.geometry · AI tried (unverified) · A186705,possible#1092Let $f_r(n)$ be maximal such that, if a graph $G$ has the property that every subgraph $H$ on $m$ vertices is the union of a graph with chromatic number $\leq r$ and a graph with $\leq f_r(m)$ edges, …geometry · solved · AI tried (unverified) · N/A#102Let $c>0$ and $h_c(n)$ be such that for any $n$ points in $\mathbb{R}^2$ such that there are $\geq cn^2$ lines each containing more than three points, there must be some line containing $h_c(n)$ m…geometry · AI tried (unverified) · N/A#103Let $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…geometry · AI tried (unverified) · possible#104Given $n$ points in $\mathbb{R}^2$ the number of distinct unit circles containing at least three points is $o(n^2)$.geometry · AI tried (unverified) · A003829#106Draw $n$ squares inside the unit square with no common interior point. Let $f(n)$ be the maximum possible sum of the side-lengths of the squares. Is $f(k^2+1)=k$?geometry · AI tried (unverified) · N/A#173In any $2$-colouring of $\mathbb{R}^2$, for all but at most one triangle $T$, there is a monochromatic congruent copy of $T$.geometry · AI tried (unverified) · N/A#174A 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$. Cha…geometry · AI tried (unverified) · N/A#217For which $n$ are there $n$ points in $\mathbb{R}^2$, no three on a line and no four on a circle, which determine $n-1$ distinct distances and so that (in some ordering of the distances) the $i$th dis…geometry · AI tried (unverified) · possible#528Let $f(n,k)$ count the number of self-avoiding walks of $n$ steps (beginning at the origin) in $\mathbb{Z}^k$ (i.e. those walks which do not intersect themselves). Determine\[C_k=\lim_{n\to\infty}f(n,…geometry · AI tried (unverified) · A387897,A156816#529Let $d_k(n)$ be the expected distance from the origin after taking $n$ random steps from the origin in $\mathbb{Z}^k$ (conditional on no self intersections) - that is, a self-avoiding walk. Is it true…geometry · AI tried (unverified) · N/A#588Let $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)=…geometry · AI tried (unverified) · A006065,A008997#589Let $g(n)$ be maximal such that in any set of $n$ points in $\mathbb{R}^2$ with no four points on a line there exists a subset on $g(n)$ points with no three points on a line. Estimate $g(n)$.geometry · AI tried (unverified) · possible#604Given $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)}?\]Or even $\gg n/\sqrt{\log n}$?pinned distance problem · geometry · AI tried (unverified) · possible#634Find all $n$ such that there is at least one triangle which can be cut into $n$ congruent triangles.geometry · AI tried (unverified) · possible#652Let $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…geometry · solved · AI tried (unverified) · N/A#654Let $f(n)$ be such that, given any $x_1,\ldots,x_n\in \mathbb{R}^2$ with no four points on a circle, there exists some $x_i$ with at least $f(n)$ many distinct distances to other $x_j$. Estimate $f(n)…geometry · AI tried (unverified) · possible#657Is 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 (i.e. $A$ has no isosceles triangles) then $A$ must determine a…geometry · AI tried (unverified) · possible#660Let $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$?ambiguous statement · geometry · AI tried (unverified) · possible#661Are 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)?\]geometry · AI tried (unverified) · possible#662Consider the triangular lattice with minimal distance between two points $1$. Denote by $f(t)$ the number of distances from any points $\leq t$. For example $f(1)=6$, $f(\sqrt{3})=12$, and $f(3)=18$.L…ambiguous statement · geometry · AI tried (unverified) · N/A#668Is 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$? Is it always $>1$ for $n>3$?geometry · AI tried (unverified) · A385657#669Let $F_k(n)$ be minimal such that for any $n$ points in $\mathbb{R}^2$ there exist at most $F_k(n)$ many distinct lines passing through at least $k$ of the points, and $f_k(n)$ similarly but with line…orchard problems · geometry · AI tried (unverified) · A003035,A006065,A008997,possible#670Let $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$?geometry · AI tried (unverified) · N/A#827Let $n_k$ be minimal such that if $n_k$ points in $\mathbb{R}^2$ are in general position then there exists a subset of $k$ points such that all $\binom{k}{3}$ triples determine circles of different ra…geometry · AI tried (unverified) · possible#831Let $h(n)$ be maximal such that in any $n$ points in $\mathbb{R}^2$ (with no three on a line and no four on a circle) there are at least $h(n)$ many circles of different radii passing through three po…geometry · AI tried (unverified) · possible#838Let $f(n)$ be maximal such that any $n$ points in $\mathbb{R}^2$, with no three on a line, determine at least $f(n)$ different convex subsets. Estimate $f(n)$ - in particular, does there exist a const…geometry · AI tried (unverified) · possible#953Let $A\subset \{ x\in \mathbb{R}^2 : \lvert x\rvert <r\}$ be a measurable set with no integer distances, that is, such that $\lvert a-b\rvert \not\in \mathbb{Z}$ for any distinct $a,b\in A$. How l…geometry · AI tried (unverified) · N/A#956If $C,D\subseteq \mathbb{R}^2$ then the distance between $C$ and $D$ is defined by\[\delta(C,D)=\inf_{\substack{c\in C\\ d\in D}}\| c-d\|.\]Let $h(n)$ be the maximal number of unit distances between d…geometry · AI tried (unverified) · possible#959Let $A\subset \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, and …geometry · AI tried (unverified) · N/A#960Let $r,k\geq 2$ be fixed. Let $A\subset \mathbb{R}^2$ be a set of $n$ points with no $k$ points on a line. Determine the threshold $f_{r,k}(n)$ such that if there are at least $f_{r,k}(n)$ many ordina…geometry · solved · AI tried (unverified) · possible#1070Let $f(n)$ be maximal such that, given any $n$ points in $\mathbb{R}^2$, there exist $f(n)$ points such that no two are distance $1$ apart. Estimate $f(n)$. In particular, is it true that $f(n)\geq n/…geometry · AI tried (unverified) · possible#1083Let $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\[f…geometry · AI tried (unverified) · A186704,possible#1086Let $g(n)$ be minimal such that any set of $n$ points in $\mathbb{R}^2$ contains the vertices of at most $g(n)$ many triangles with the same area. Estimate $g(n)$.geometry · AI tried (unverified) · possible#1087Let $f(n)$ be minimal such that every set of $n$ points in $\mathbb{R}^2$ contains at most $f(n)$ many sets of four points which are 'degenerate' in the sense that some pair are the same distance apar…geometry · AI tried (unverified) · possible#1088Let $f_d(n)$ be the minimal $m$ such that any set of $m$ points in $\mathbb{R}^d$ contains a set of $n$ points such that any two determined distances are distinct. Estimate $f_d(n)$. In particular, is…geometry · AI tried (unverified) · possible#1089Let $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…geometry · solved · AI tried (unverified) · possible#1091Let $G$ be a $K_4$-free graph with chromatic number $4$. Must $G$ contain an odd cycle with at least two diagonals?More generally, is there some $f(r)\to \infty$ such that every graph with chromatic n…geometry · solved · AI tried (unverified) · N/A#1127Can $\mathbb{R}^n$ be decomposed into countably many sets, such that within each set all the pairwise distances are distinct?geometry · solved · AI tried (unverified) · N/A#189If $\mathbb{R}^2$ is finitely coloured then must there exist some colour class which contains the vertices of a rectangle of every area?geometry · solved · N/A#505Is every set of diameter $1$ in $\mathbb{R}^n$ the union of at most $n+1$ sets of diameter $<1$?Borsuk's problem · geometry · solved · possible#846Let $A\subset \mathbb{R}^2$ be an infinite set for which there exists some $\epsilon>0$ such that in any subset of $A$ of size $n$ there are always at least $\epsilon n$ with no three on a line.Is…geometry · solved · AI machine-verified · N/A#93If $n$ distinct points in $\mathbb{R}^2$ form a convex polygon then they determine at least $\lfloor \frac{n}{2}\rfloor$ distinct distances.geometry · solved · N/A#94Suppose $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 poin…geometry · solved · A387858#95Let $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$\[\su…geometry · solved · possible#105Let $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 po…geometry · solved · N/A#209Let $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 'ordina…geometry · solved · N/A#210Let $f(n)$ be minimal such that the following holds. For any $n$ points in $\mathbb{R}^2$, not all on a line, there must be at least $f(n)$ many lines which contain exactly 2 points (called 'ordinary …geometry · solved · A003034#211Let $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.geometry · solved · N/A#214Let $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?geometry · solved · N/A#215Does 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$?geometry · solved · N/A#216Let $g(k)$ be the smallest integer (if any such exists) such that any $g(k)$ points in $\mathbb{R}^2$ contains an empty convex $k$-gon (i.e. with no point in the interior). Does $g(k)$ exist? If so, e…geometry · solved · A381776#223Let $d\geq 2$ and $n\geq 2$. Let $f_d(n)$ be maximal such that there exists some set of $n$ points $A\subseteq \mathbb{R}^d$, with diameter $1$, in which the distance 1 occurs between $f_d(n)$ many pa…geometry · solved · possible#224If $A\subseteq \mathbb{R}^d$ is any set of $2^d+1$ points then some three points in $A$ determine an obtuse angle.geometry · solved · N/A#232For $A\subset \mathbb{R}^2$ we define the upper density as\[\overline{\delta}(A)=\limsup_{R\to \infty}\frac{\lambda(A \cap B_R)}{\lambda(B_R)},\]where $\lambda$ is the Lebesgue measure and $B_R$ is th…geometry · solved · N/A#353Let $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 triang…geometry · solved · N/A#502What 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.\]geometry · solved · A027627#504Let $\alpha_n$ be the supremum of all $0\leq \alpha\leq \pi$ such that in every set $A\subset \mathbb{R}^2$ of size $n$ there exist three distinct points $x,y,z\in A$ such that the angle determined by…Blumenthal's problem · geometry · solved · N/A#506What is the minimum number of circles determined by any $n$ points in $\mathbb{R}^2$, not all on a circle?geometry · possible#605Is there some function $f(n)\to \infty$ as $n\to\infty$ such that there exist $n$ distinct points on the surface of a two-dimensional sphere with at least $f(n)n$ many pairs of points whose distances …geometry · solved · possible#606Given any $n$ distinct points in $\mathbb{R}^2$ let $f(n)$ count the number of distinct lines determined by these points. What are the possible values of $f(n)$?geometry · solved · N/A#607For a set of $n$ points $P\subset \mathbb{R}^2$ let $\ell_1,\ldots,\ell_m$ be the lines determined by $P$, and let $A=\{\lvert \ell_1\cap P\rvert,\ldots,\lvert \ell_m\cap P\rvert\}$.Let $F(n)$ count t…geometry · solved · possible#651Let $f_k(n)$ denote the smallest integer such that any $f_k(n)$ points in general position in $\mathbb{R}^k$ contain $n$ which determine a convex polyhedron. Is it true that\[f_k(n) > (1+c_k)^n\]f…geometry · solved · possible#735Given any $n$ points in $\mathbb{R}^2$ when can one give positive weights to the points such that the sum of the weights of the points along every line containing at least two points is the same?geometry · solved · N/A#754Let $f(n)$ be maximal such that there exists a set $A$ of $n$ points in $\mathbb{R}^4$ in which every $x\in A$ has at least $f(n)$ points in $A$ equidistant from $x$.Is it true that $f(n)\leq \frac{n}…geometry · solved · possible#755The number of equilateral triangles of size $1$ formed by any set of $n$ points in $\mathbb{R}^6$ is at most $(\frac{1}{27}+o(1))n^3$.geometry · solved · possible#756Let $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$?geometry · solved · possible#798Let $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…geometry · solved · A116446#898If $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$,\[\overline{PA}…Erdős-Mordell inequality · geometry · solved · N/A#957Let $A\subset \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 determin…geometry · solved · N/A#1069Given any $n$ points in $\mathbb{R}^2$, the number of $k$-rich lines (lines which contain $\geq k$ of the points) is, provided $k\leq n^{1/2}$,\[\ll \frac{n^2}{k^3}.\]geometry · solved · possible#1090Let $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$ …geometry · solved · N/A#1121If $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 …geometry · solved · N/A#1124Can a square and a circle of the same area be decomposed into a finite number of congruent parts?geometry · solved · N/A#1207Let $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…geometry · possible#1208For $d\geq 2$ let $F_d(n)$ be minimal such that every set of $n$ points in $\mathbb{R}^d$ contains a set of $F_d(n)$ points with distinct distances. Estimate $F_d(n)$ for fixed $d$ as $n\to \infty$.geometry · possible