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.
Let \(f(n)\) be minimal such that every triangle-free graph \(G\) with \(n\) vertices and diameter \(2\) contains a vertex with degree \(\geq f(n)\). What is the order of growth of \(f(n)\)? Does \(f(n)/\sqrt{n}\to \infty\)? Asked by Erdős…
If \(T\) is a tree which is a bipartite graph with \(k\) vertices in one class and \(2k\) vertices in the other class then \[R(T)=4k-1.\] This is false: Norin, Sun, and Zhao [NSZ16] have proved that if \(T\) is the union of two stars on…
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 that is Ramsey for \(G\). If \(G\) has \(n\) vertices and maximum degree \(d\) then prove that…
Is there a covering system such that no two of the moduli divide each other? Asked by Schinzel, motivated by a question of Erdős and Selfridge (see [7](https://www.erdosproblems.com/7)). The answer is no, as proved by Balister, Bollobás,…
Is there some function \(f\) such that for all \(k\geq 1\) if a finite graph \(G\) has chromatic number \(\geq f(k)\) then \(G\) has \(k\) edge disjoint cycles on the same set of vertices? A problem of Erdős and Hajnal. This was resolved…
Let \(c<1\) be some constant and \(A_1,\ldots,A_m\subseteq \{1,\ldots,n\}\) be such that \(\lvert A_i\rvert >c\sqrt{n}\) for all \(i\) and \(\lvert A_i\cap A_j\rvert\leq 1\) for all \(i\neq j\). Must there exist some set \(B\) such that…
Let \(G\) be a finite unit distance graph in \(\mamthbb{R}^2\). Is there some \(k\) such that if \(G\) has girth \(≥ k\), then \(\chi(G) ≤ 3\)? The general case was solved by O'Donnell [OD99], who constructed finite unit distance graphs…
Let \(A\subseteq \mathbb{N}\). Can there exist some constant \(c>0\) such that \[\sum_{n\leq N} 1_A\ast 1_A(n) = cN+O(1)?\] A conjecture of Erdős and Turán. Erdős and Fuchs [ErFu56] proved that the answer is no in a strong form: in fact…
Let \(A\subseteq \mathbb{N}\). Can there exist some constant \(c>0\) such that \[\sum_{n\leq N} 1_A\ast 1_A\ast 1_A(n) = cN+O(1)?\] The case of \(1_A\ast 1_A(n)\) is the subject of [763](https://www.erdosproblems.com/763). The answer is…
Let \(f(k)\) be the minimal \(n\) such that any \(2\)-colouring of \(\{1,\ldots,n\}\) contains a monochromatic \(k\)-term descending wave: a sequence \(x_1<\cdots <x_k\) such that, for \(1<j<k\), \[x_j \geq \frac{x_{j+1}+x_{j-1}}{2}.\]…
Let \(f(m,n)\) be maximal such that any graph on \(n\) vertices in which every induced subgraph on \(m\) vertices has an independent set of size at least \(\log n\) must contain an independent set of size at least \(f(n)\). Estimate…
Let \(r\geq 3\) and \(k\) be sufficiently large in terms of \(r\). Is it true that every \(r\)-uniform hypergraph with chromatic number \(k\) has at least \[\binom{(r-1)(k-1)+1}{r}\] edges, with equality only for the complete graph on…
If \(A_1, A_2\) are disjoint additive bases of order \(2\) (i.e. \(A_i + A_i\) contains all large integers) then must \(A = A_1 \cup A_2\) contain a minimal additive basis of order \(2\) (one such that deleting any element creates…
Let \(f\in \mathbb{C}[x]\) be a monic polynomial and \[E=\{ z: \lvert f(z)\rvert <1\}.\] If \(E\) is connected then is \(E\) contained in a disc of radius \(2\)? A problem of Erdős, Herzog, and Piranian [EHP58], who also ask, if…
If \(\mathbb{N}\) is \(2\)-coloured, must there exist an infinite set \(A=\{a_1<a_2<\cdots\}\) such that all expressions of the shape \[\sum_{j=1}^{k}\prod_{i\in S_j}a_i,\] for \(k\geq 1\) and pairwise disjoint nonempty finite sets of…