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.
Is it true that, for any \(C > 0\), there 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 \]
If \(G\) is a graph which contains odd cycles of \(\leq k\) different lengths then \(\chi(G)\leq 2k+2\), with equality if and only if \(G\) contains \(K_{2k+2}\). Conjectured by Bollobás and Erdős. Proved by Gyárfás [Gy92].
Erdős discrepancy problem
**The Erdős discrepancy problem** If \(f\colon \mathbb N \rightarrow \{-1, +1\}\) then is it true that for every \(C>0\) there exist \(d, m \ge 1\) such that \[\left\lvert \sum_{1\leq k\leq m}f(kd)\right\rvert > C?\] This is true, and was…
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\)? Bollobás [Bo77] proved that such a…
Let \(k\ge 0\). Let \(G\) be a graph such that every subgraph \(H\) contains an independent set of size \(\ge (n-k)/2\), where \(n\) is the number of vertices of \(H\). Must \(G\) be the union of a bipartite graph and \(O_k(1)\) many…
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?…
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…
Does there exist an infinite Sidon set which is an asymptotic basis of order \(3\)? Yes, as shown by Pilatte [Pi23].
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…
For any \(g\geq 2\), if \(n\) is sufficiently large and \(\equiv 1,3\pmod{6}\) then there exists a 3-uniform hypergraph on \(n\) vertices such that - every pair of vertices is contained in exactly one edge (i.e. the graph is a Steiner…
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].
Let \[ f(\theta) = \sum_{0\leq k\leq n}c_k e^{ik\theta}\] be a trigonometric polynomial all of whose roots are real, such that \(\max_{\theta\in [0,2\pi]}\lvert f(\theta)\rvert=1\). Then \[\int_0^{2\pi}\lvert f(\theta)\rvert…
Let \(N_k=2\cdot 3\cdots p_k\) and \(\{a_1<a_2<\cdots <a_{\phi(N_k)}\}\) be the integers \(<N_k\) which are relatively prime to \(N_k\). Then, for any \(c\geq 0\), the limit \[\frac{\#\{ a_i-a_{i-1}\leq c \frac{N_k}{\phi(N_k)} : 2\leq…
Let \(A\subseteq\mathbb{N}\) be an infinite set such that \(|A\cap \{1, ..., N\}| = o(N)\). Is it true that \[ \limsup_{N\to\infty}\frac{|(A + A)\cap \{1, ..., N\}|}{|A \cap \{1, ..., N\}|} \geq 3? \] The answer is yes, proved by Freiman…
Let \(k\geq 2\). Is it true that there exists an interval \(I\) of width \((e-1+o(1))k\) and integers \(n_1<\cdots<n_k\in I\) such that \[1=\frac{1}{n_1}+\cdots+\frac{1}{n_k}?\] The answer is yes, proved by Croot [Cr01].
Let \(A\) be the set of \(n\in \mathbb{N}\) such that there exist \(1\leq m_1<\cdots <m_k=n\) with \(\sum\tfrac{1}{m_i}=1\). Explore \(A\). In particular, does \(A\) have density \(1\)? Straus observed that \(A\) is closed under…
For integers \(1\leq a<b\) let \(D(a,b)\) be the minimal value of \(n_k\) such that there exist integers \(1\leq n_1<\cdots <n_k\) with \[\frac{a}{b}=\frac{1}{n_1}+\cdots+\frac{1}{n_k}.\] Estimate \(D(b)=\max_{1\leq a<b}D(a,b)\). Is it…
Let \(N\geq 1\). What is the smallest integer not representable as the sum of distinct unit fractions with denominators from \(\{1,\ldots,N\}\)? This was essentially solved by Croot [Cr99] (see erdos_308.variants.croot); in particular, for…
Let \(P(n)\) denote the largest prime factor of \(n\). There are infinitely many \(n\) such that \(P(n)>P(n+1)>P(n+2)\).
Prove that, for any finite set \(A\subset\mathbb{N}\), there exist \(a, b\in A\) such that \[ \gcd(a, b)\leq a/|A|. \]
Let \(w(n)\) count the number of solutions to \[n=2^a+3^b+2^c3^d\] with \(a,b,c,d\geq 0\) integers. Is it true that \(w(n)\) is bounded by some absolute constant? A conjecture originally due to Newman. This is true, and was proved by…
Let \(1\leq a_1<\cdots<a_k\leq x\). How many of the partial products \(a_1,a_1a_2,\ldots,a_1\cdots a_k\) can be squares? Is it true that, for any \(\epsilon>0\), there can be more than \(x^{1-\epsilon}\) squares? The answer is yes, which…
Let \(A\subseteq\mathbb{N}\) be infinite and \(d_A(n)\) count the number of \(a\in A\) which divide \(n\). Is it true that, for every \(k\), \[\limsup_{x\to \infty} \frac{\max_{n<x}d_A(n)}{\left(\sum_{n\in A\cap[1,x)}\frac{1}{n}\right)^k}…
Let \(N(X,\delta)\) denote the maximum number of points \(P_1,\ldots,P_n\) which can be chosen in a circle of radius \(X\) such that \[\| \lvert P_i-P_j\rvert \| \geq \delta\] for all \(1\leq i<j\leq n\). (Here \(\|x\|\) is the distance…
Is there a permutation \(a_1, a_2, \ldots\) of the positive integers such that \(a_k + a_{k+1}\) is always prime? A question of Segal [ErGr80, p.94]. The answer is yes, as shown by Odlyzko. The linked formal proof (Codex and GPT-5.6 Sol)…
Let \(f(k)\) be the minimum number of terms in \(P(x)^2\), where \(P \in \mathbb{Q}[x]\) ranges over all polynomials with exactly \(k\) non-zero terms. Is it true that \(f(k) \to \infty\) as \(k \to \infty\)? A conjecture of Erdős and…
Let \(f : \mathbb{N} \to \mathbb{R}\) be an additive function (so that \(f(ab) = f(a) + f(b)\) whenever \((a, b) = 1\)). If \(|f(n+1) - f(n)| < c\) for some constant \(c\) and all \(n\), then must there exist some \(c'\) such that…
Is it true that all except at most \(o(2^n)\) many degree \(n\) polynomials with \(\pm 1\)-valued coefficients \(f(z)\) have \(\lvert f(z)\rvert <1\) for some \(\lvert z\rvert=1\)? The answer is yes: Littlewood [Li66] conjectured the…
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…
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,…
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…
Erdős-Menger conjecture
**Erdős Problem 599** (the Erdős–Menger conjecture). Let \(G\) be a (possibly infinite) graph and let \(A, B\) be disjoint independent sets of vertices. Must there exist a family \(P\) of pairwise vertex-disjoint paths from \(A\) to \(B\),…
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…
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 \(1=d_1<\cdots <d_{\tau(n)}=n\) be the divisors of \(n\) and \[G(n) = \sum_{1\leq i<\tau(n)}\frac{d_i}{d_{i+1}}.\] Is it true that \(G(n)\to \infty\) for almost all \(n\)? The answer is yes: Tao observed that…
Is it true that for almost all \(n\) there exists some \(m\in (p_n,p_{n+1})\) such that \[p(m) \geq p_{n+1}-p_n,\] where \(p(m)\) denotes the least prime factor of \(m\)? This was solved in the affirmative by Gafni and Tao [GaTa25]. This…
For each \(m\) and \(\alpha\), the density of the set of integers which are divisible by some \(d \equiv 1 \pmod{m}\) with \(1 < d < \exp (m ^ \alpha)\) exists.
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…
Let \(k>r\) and \(n\) be sufficiently large in terms of \(k\) and \(r\). Does there always exist a block \(r-(n,k,1)\) design (or Steiner system with parameters \((n,k,r)\)), provided the trivial necessary divisibility conditions…
Call a sequence \(1< X_1\leq \cdots \leq X_m\leq n\) block-compatible if there is a pairwise balanced block design \(A_1,\ldots,A_m\subseteq \{1,\ldots,n\}\) such that \(\lvert A_i\rvert=X_i\) for \(1\leq i\leq m\). (A pairwise block…
Cameron-Erdős conjecture
Let \(f(n)\) count the number of sum-free \(A\subseteq \{1,\ldots,n\}\), i.e. \(A\) contains no solutions to \(a=b+c\) with \(a,b,c\in A\). Is it true that \[f(n)=2^{(1+o(1))\frac{n}{2}}?\] The Cameron–Erdős conjecture. This is true, and…
Let \(g_k(n)\) be the maximal number of edges possible on a graph with \(n\) vertices which does not contain a cycle with \(k\) chords incident to a vertex on the cycle. Is it true that \[g_k(n)=(k+1)n-(k+1)^2\] for \(n\) sufficiently…
Let \(k\geq 1\) and \(H_k(n)\) be the maximal \(r\) such that if \(A\subset\mathbb{N}\) has \(\lvert A\rvert=n\) and \(\| 1_A\ast 1_A\|_\infty \leq k\) then \(A\) contains a Sidon set of size at least \(r\). Is it true that…
Suppose \(n\geq kr+(t-1)(k-1)\) and the edges of the complete \(r\)-uniform hypergraph on \(n\) vertices are \(t\)-coloured. Prove that some colour class must contain \(k\) pairwise disjoint edges. In other words, this problem asks to…
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].
Let \(A\subseteq \{1,\ldots,n\}\) with \(\lvert A\rvert \leq n^{1/2}\). Must there exist some \(B\subset\mathbb{Z}\) with \(\lvert B\rvert=o(n^{1/2})\) such that \(A\subseteq B+B\)? A problem of Erdős and Newman [ErNe77], who proved that…
Let \(k\geq 2\) and \(G\) be a graph with \(n\geq k-1\) vertices and \[(k-1)(n-k+2)+\binom{k-2}{2}+1\] edges. Does there exist some \(c_k>0\) such that \(G\) must contain an induced subgraph on at most \((1-c_k)n\) vertices with minimum…
Let \(G\) be a graph with \(2n+1\) vertices and \(n^2+n+1\) edges. Must \(G\) contain two vertices of the same degree which are joined by a path of length \(3\)? A problem of Erdős and Hajnal. The example of \(K_{n,n+1}\) shows that this…
Does the set of integers of the form \(n + \varphi(n)\) have positive (lower) density? [GIL24] proved this was true.
Does there exist an absolute constant \(c>0\) such that, for all \(r\geq 2\), in any \(r\)-uniform hypergraph with chromatic number \(3\) there is a vertex contained in at least \((1+c)^r\) many edges? This was solved by Erdős and Lovász…
Let \(G\) be a graph on \(3n\) vertices formed by taking \(n\) vertex disjoint triangles and adding a Hamiltonian cycle (with all new edges) between these vertices. Does \(G\) have chromatic number at most \(3\)? The answer is yes, proved…
Let \(\epsilon > 0\). Is there some \(r \ll_\epsilon 1\) such that the density of integers of the form \(2^k+n\), where \(k \geq 0\) and \(n\) has at most \(r\) prime divisors, is at least \(1-\epsilon\)? This was proved affirmatively by…
Let \(f_m(n)\) count the number of maximal sum-free subsets \(A\subseteq\{1,\ldots,n\}\) - that is, there are no solutions to \(a=b+c\) in \(A\) and \(A\) is maximal with this property. Estimate \(f(n)\) - is it true that…
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 it true that, for all sufficiently large \(n\), if \(G\) is a triangle-free graph on \(\{1,\ldots,n\}\) then there must exist three independent points \(a,b,a+b\)? A problem of Erdős and Hajnal [Er95d]. The stated problem has been…
Let \(n=p^2+p+1\) for some prime power \(p\), and let \(A_1,\ldots,A_t\subseteq \{1,\ldots,n\}\) be a block design (so that every pair \(x,y\in \{1,\ldots,n\}\) is contained in exactly one \(A_i\)). Is it true that if \(t>n\) then…
Let \(k\geq 4\) and let \(f_k(n)\) be the largest \(m\) such that there is a graph on \(n\) vertices with chromatic number \(k\) in which every odd cycle has length \(> m\). Then \[f_k(n) \asymp n^{\frac{1}{k-2}}.\] A question of Erdős and…
Let \(k\geq 0\). Let \(G\) be a graph such that every subgraph \(H\) contains an independent set of size \(\geq (n-k)/2\), where \(n\) is the number of vertices of \(H\). Must \(G\) have chromatic number at most \(k+2\)? A question of…
Let \(k\geq 4\). Is it true that \[\mathrm{ex}(n;H_k) \ll_k n^{3/2},\] where \(H_k\) is the graph on vertices \(x,y_1,\ldots,y_k,z_1,\ldots,z_{\binom{k}{2}}\), where \(x\) is adjacent to all \(y_i\) and each pair of \(y_i,y_j\) is adjacent…
There are infinitely many \(n\) such that \(τ(n) = τ(n+1)\). Proved in [He84]. Here τ is the divisor counting function, which is σ 0 in mathlib.
If \(P(m)\) is the greatest prime divisor of \(m\), then is it true that \[\frac{P(2^n-1)}{n}\to \infty\] as \(n\to \infty\)? Schinzel [Sc62] proved that \(P(2^n-1)>2n\) for \(n>12\). In [Er65b] Erdős also asks about \(P(n!+1)\). Stewart…
Let \(\epsilon > 0\) and \(f_\epsilon(p)\) be the smallest integer \(m\) such that \(\sum_{n\leq N} \left(\frac{n}{p}\right)<\epsilon N\) for all \(N\geq m\). Prove that \[\sum_{p<x}f_\epsilon(p)\sim c_\epsilon \frac{x}{\log x}\] for some…
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…
Duffin-Schaeffer conjecture
For any function \(f:\mathbb{N}\to \mathbb{R}_{\geq 0}\) the property that, for almost all \(\alpha\) \[\left\lvert \alpha-\frac{p}{q}\right\rvert < \frac{f(q)}{q}\] has infinitely many solutions with \((p,q)=1\), is equivalent to…
Is it true that, for every \(c>0\), there exists \(f(c)\) such that every graph on \(n\) vertices with at least \(\lfloor n^2/4\rfloor+k\) edges, where \(k<c n\), contains at least \(k-f(c)\) many edge disjoint triangles? Erdős [Er71]…
Let \(t<\lfloor n/2\rfloor\). Does every graph on \(n\) vertices with \(\lfloor n^2/4\rfloor+t\) edges contain at least \(t\lfloor n/2\rfloor\) triangles? Rademacher proved that every graph on \(n\) vertices with \(\lfloor n^2/4\rfloor+1\)…
Is it true that, for every \(k \geq 3\), there is a constant \(c_k > 0\) such that \[\mathrm{ex}(n, G_k) \ll n^{3/2 - c_k},\] where \(G_k\) is the bipartite graph between \(\{y_1, \ldots, y_k\}\) and \(\{z_1, \ldots, z_{\binom{k}{2}}\}\),…
Let \(c>0\), and let \(n\) be sufficiently large depending on \(c\). Suppose that \(\mathcal{F}\) is a family of at most \(c2^n\) many finite sets of size \(n\). Let \(X=\cup_{A\in \mathcal{F}}A\). Must there exist…
Let \(2=p_1<p_2<\cdots\) be the sequence of prime numbers. Are there only finitely many \(n\) such that \(n\in [p_{k-1},p_k)\) and the only primes dividing \(n!+1\) are \(p_{k}\) and \(p_{k+1}\)? A conjecture of Erdős and Stewart, as…
Let \(ϕ(n)\) be the Euler's totient function, then the \(n\) satisfies \(ϕ(n)>ϕ(n - ϕ(n))\) have asymptotic density 1. Reference: [LuPo02] Luca, Florian and Pomerance, Carl, On some problems of {M}\polhk akowski-{S}chinzel and {E}rd\H os…
Let \(1=d_1<\cdots<d_{\tau(n)}=n\) be the divisors of \(n\), and for \(\alpha>1\) let \[h_\alpha(n) = \sum_i \left( \frac{d_{i+1}}{d_i}-1\right)^\alpha.\] Is it true that \[\liminf_{n\to \infty}h_\alpha(n) \ll_\alpha 1?\] Erdős [Er81h]…
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\)…
Let \(\alpha>0\) be a real number, not an integer. The density of integers \(n\geq 1\) for which \((n,\lfloor n^\alpha\rfloor)=1\) is \(6/\pi^2\). This is true, and was proved by Bergelson and Richter [BeRi17].
Let \(0<\epsilon<1\) and let \(g_\epsilon(N)\) be the minimal \(k\) such that if \(G\) is an abelian group of size \(N\) and \(A\subseteq G\) is a uniformly random subset of size \(k\), and \[F_A(g) = \#\left\{ S\subseteq A : g =…
Let \(\epsilon>0\). Does there exist a constant \(C_\epsilon\) such that, for all primes \(p\), every residue modulo \(p\) is the sum of at most \(C_\epsilon\) many elements of \[\{ n^{-1} : 1\leq n\leq p^\epsilon\}\] where \(n^{-1}\)…
Let \(a,K\geq 1\). Does there exist \(f(a,K)\) such that if \(a=a_1<\cdots <a_s\) is a sequence of integers with \(a_s> f(a,K)\) and with bounded gaps \(a_{i+1}-a_i\leq K\) then there are two distinct intervals \(I\) and \(J\) such that…
Let \(x,y\geq 1\) be integers such that, for all \(n\geq 1\), the set of primes dividing \(x^{n}-1\) is equal to the set of primes dividing \(y^n-1\). Must \(x=y\)? Erdős asked this at a 1988 number theory conference in Banff. A positive…
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…