Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
606 of 1,221 problems match
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Asks whether the largest subset of one to n in which no element divides the product of two others has an asymptotic led by a prime-counting term; proved with the constant 27/2 in Chojecki's 2026 manuscript, accepted by the site.
Asks whether every three-uniform hypergraph on 3n vertices with more than n cubed edges has four vertices spanning three edges; false as written by a 28-edge example, while the Turán density of K_4 minus an edge stays open.
Asks whether the largest subset of one to n with all subset products distinct is bounded by the primes up to n plus those up to the square root of n; proved by Raghavan with a power-saving error term.
The largest number of colors needed to color any graph of maximum degree d so that no edge and no cycle uses only one or two colors respectively; of order d^{4/3} up to a (log d)^{1/3} factor by Alon, McDiarmid and Reed 1991.
The fewest points in the n by n grid of integers whose pairwise connecting lines cover every point of that grid.
Asks whether almost every graph on n vertices has list chromatic number o(n); yes by Alon 1992 (O(n log log n / log n)), sharpened by Alon, Krivelevich and Sudakov 1999 to order n / log n.
Asks whether every graph on n vertices with no two adjacent vertices both of degree at least three has Ramsey number at most a constant times n.
Asks whether a graph on n vertices with no independent set larger than the square root of n has a set of that many vertices spanning many more edges.
Asks whether every K_r-free graph on n vertices with average degree t has an independent set of order n log t over t; true for r = 3 since 1980, and for every r at least 4 by a Lean-checked theorem of the 2026 OpenAI release.
Asks whether every graph with n log n edges has an almost-regular subgraph on m vertices with much more than m log m edges; false by Alon's 2008 random bipartite construction, with Janzer and Sudakov's bound the best positive one.
Estimates the largest independent set forced in a graph on n vertices where every induced subgraph on m vertices has an independent set of size log n.
Asks whether every set of at most sqrt(n) integers up to n lies in B + B for some B of size o(sqrt(n)); proved by Alon, Bukh and Sudakov with a basis of order sqrt(n) log log n / log n, the sharp order.
Asks whether the random graph with edge probability one half almost surely needs exactly n minus its independence number complete bipartite graphs to partition its edges; disproved by Alon, then by Alon, Bohman and Huang.
Asks whether, for a graph on a set of n integers with many edges, the sums or the products along its edges must number nearly as many as the edge count.
Asks whether the fewest colors making every odd cycle of length 2k+1 rainbow on some n-vertex graph one edge past the Turán number is asymptotically n squared over eight for all k at least 3; proved by two Lean developments built and audited here, Asad Shahab's, filed first, and the project's claim L17.
Asks whether a graph with one edge more than the count forcing a subgraph of minimum degree k has such an induced subgraph on a constant fraction fewer vertices; proved by Sauermann for k at least 3, with k = 2 elementary.
Asks whether a graph with n vertices, 2n - 2 edges and no proper induced subgraph of minimum degree 3 has a cycle of each fixed length k for large n; false at k = 23 (Narins, Pokrovskiy, Szabó), true for k up to 6, even k open.
Asks whether a finite set of integers with small sumset must have product set nearly the square of its size, up to a power of a logarithm.
Asks whether the integers of the form n plus the Euler totient of n have positive lower density.
Asks whether, for every real number at least one, there are pairs of integers with equal sums of divisors whose ratio tends to that number.
Asks whether there is a constant C such that every integer whose sum of divisors exceeds C times it is a sum of distinct proper divisors of itself.
Records Alon's counterexamples to the complete-hypergraph edge benchmark, while separating the defective equality wording and the open r=3 case.
Records the Erdős–Lovász exponential vertex-degree bound and an explicit constant that covers every uniformity r at least two.
Asks whether there is a three-critical three-uniform hypergraph in which every vertex has degree at least seven.
Estimates the least length of a run of integers just above n that contains a subset whose product with n is a perfect square; Erdős's original question, whether the n with t_n at least n^{1-o(1)} have density zero, has the answer yes.