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 there a covering system all of whose moduli are odd (and greater than 1)?
If \(G\) is an edge-disjoint union of \(n\) copies of \(K_n\), then is \(\chi(G) = n\)?
Can every triangle-free graph on \(5n\) vertices be made bipartite by deleting at most \(n^2\) edges?
Does every finite graph with minimum degree at least \(3\) contain a cycle of length \(2^k\) for some \(k \geq 2\)?
Does every convex polygon have a vertex with no other 4 vertices equidistant from it?
'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\).
If \(p(z) \in \mathbb{C}[z]\) is a monic polynomial of degree \(n\), is the length of the curve \(\{z \in \mathbb{C} : \lvert p(z)\rvert = 1\}\) maximised when \(p(z) = z^n - 1\)? We require \(n \geq 1\). For \(n = 0\) the only monic…
Let G be a graph with n vertices such that every induced subgraph on ≥ \(n/2\) vertices has more than \(n^2/50\) edges. Must G contain a triangle?
Erdős-Straus conjecture
For every \(n>2\) there exist distinct integers \(1 ≤ x < y < z\) such that \(\frac 4 n = \frac 1 x + \frac 1 y + \frac 1 z\).
Let \(k\geq2\). Is it true that, for any distinct integers \(1 < n_1 < \cdots < n_k\) such that \(\sum_{i=1}^k \frac{1}{n_i} = 1\), we must have \(\max(n_{i+1} - n_i) \geq 3\)?
Are there two finite set of primes \(P\) and \(Q\) such that \[ 1 = \left( \sum_{p \in P} \frac{1}{p} \right) \left( \sum_{q \in Q} \frac{1}{q} \right) \] ? Asked by Barbeau [Ba76]. [Ba76] Barbeau, E. J., _Computer challenge corner:…
There is no consecutive triple of powerful numbers.
ambiguous statement
Are there any \(2\)-full \(n\) such that \(n+1\) is \(3\)-full?
Is Erdos375Prop true?
Brocard-Ramanujan conjecture
**Brocard's Problem** Does \(n! + 1 = m^2\) have integer solutions other than \(n = 4, 5, 7\)?
Let \(\operatorname{lcm}(1, \dots, n)\) denote the least common multiple of \(\{1, \dots, n\}\). Let \(p_k\) be the \(k\)-th prime. Is it true that for all \(k \geq 1\),…
Let \(A\) be a finite set and \[B=\{ n \geq 1 : a\mid n\textrm{ for some }a\in A\}.\] Is it true that, for every \(m>n\geq \max(A)\), \[\frac{\lvert B\cap [1,m]\rvert }{m}< 2\frac{\lvert B\cap [1,n]\rvert}{n}?\]
Prove that \[R(C_k,K_n)=(k-1)(n-1)+1\] for \(k\geq n\geq 3\) (except when \(n=k=3\)). Asked by Erdős, Faudree, Rousseau, and Schelp. This problem is #18 in Ramsey Theory in the graphs problem collection.
Erdős Problem 556 (Bondy–Erdős): for all \(n \ge 4\), \[R(C_n; 3) \le 4n - 3.\] The case \(n = 3\) is excluded since \(R(K_3; 3) = 17\).
Every connected graph on \(n\) vertices can be partitioned into at most \(\lceil n/2\rceil\) edge-disjoint paths. A problem of Erdős and Gallai.
Let \(r\geq 3\). If the edges of \(K_{r^2+1}\) are \(r\)-coloured then there exist \(r+1\) vertices with at least one colour missing on the edges of the induced \(K_{r+1}\). In other words, there is no balanced colouring. A conjecture of…
Erdős-Lovász Tihany Conjecture
Let \(G\) be a graph with chromatic number \(k\) containing no \(K_k\). If \(a,b\geq 2\) and \(a+b=k+1\) then must there exist two disjoint subgraphs of \(G\) with chromatic numbers \(\geq a\) and \(\geq b\) respectively?
Let \(\tau(n)\) count the number of divisors of \(n\). Is there some \(n > 24\) such that \[ \max_{m < n}(m + \tau(m)) \leq n + 2? \]
Can the product of an arithmetic progression of positive integers \(n, n + d, ..., n + (k - 1)d\) of length \(k ≥ 4\), with \((n, d) = 1\), be a perfect power? Erdős believed not, i.e. that Erdos672With k l holds for all \(k ≥ 4\) and…
Sylvester and Schur: for \(1 \le i \le n/2\) there is a prime \(p > i\) dividing n.choose i.
If there is a finite projective plane of order \(n\) then must \(n\) be a prime power?
**Murty-Simon Conjecture** Let \(G\) be a graph on \(n\) vertices with diameter \(2\) such that deleting any edge increases the diameter. Is it true that \(G\) has at most \(\lfloor n^2 / 4 \rfloor\) edges? Equality is conjectured to hold…
tree packing conjecture
Let \(T_2,\ldots,T_n\) be a collection of trees such that \(T_k\) has \(k\) vertices. Can we always write \(K_n\) as the edge disjoint union of the \(T_k\)? A conjecture of Gyárfás, known as the tree packing conjecture. We state it as a…
Does there exist a \(k>2\) such that the \(k\)-sized subsets of {1,...,2k} can be coloured with \(k+1\) colours such that for every \(A\subset \{1,\ldots,2k\}\) with \(\lvert A\rvert=k+1\) all \(k+1\) colours appear among the \(k\)-sized…
Is the maximum size of a set \(A ⊆ \{1, \dots, N\}\) such that \(ab + 1\) is never squarefree (for all \(a, b ∈ A\)) achieved by taking those \(n ≡ 7 \pmod{25}\)? This asks whether Erdos848 N holds for all \(N\) (formulated using A ⊆…
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.
Erdős matching conjecture
Let \(f(n;r,k)\) be the maximal number of edges in an \(r\)-uniform hypergraph which contains no set of \(k\) many independent edges. For all \(r\geq 3\), \[f(n;r,k)=\max\left(\binom{rk-1}{r}, \binom{n}{r}-\binom{n-k+1}{r}\right).\] Note:…
**Erdős–Herzog–Piranian Component Lemma** (Metric Properties of Polynomials, 1958): If \(f\) is a monic degree \(n\) polynomial with all roots in the unit disk, then some connected component of \(\{z \mid |f(z)| < 1\}\) contains at least…
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?