Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
1,221 problems
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
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.
Characterizes the functions g for which some graph on n vertices has every induced subgraph on g of n vertices with a clique and 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 some graph on n vertices with a positive fraction of all possible edges can be edge-colored with n colors so that every four-cycle gets four distinct colors.
Asks which graphs are forced as rainbow copies in every balanced coloring of a large complete graph with as many colors as the graph has edges, where each vertex sees equally many edges of every color.
Asks whether consecutive diagonal Ramsey numbers grow by at least a constant factor, and whether their difference is at least a constant times n squared.
Estimates the largest clique forced in an n-vertex graph where every seven vertices span a triangle: the exponent lies between 5/12 (Bucić and Sudakov) and 1/2 (Erdős and Hajnal), and whether either end can be moved is open.
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 graph with 2n + 1 vertices and n^2 + n + 1 edges has two equal-degree vertices joined by a path of length 3; corrected to n at least 2, since n = 1 (the triangle) fails; proved for n at least 600 by Chen and Ma and claimed for every n at least 2 by Liu and Zeng.
Estimates the least N for which some n-element set of integers up to N has all subset sums free of k-term progressions, and asks whether the k = 3 case grows like 3^n; open, with a 2026 preprint claiming a negative answer.
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.
Estimates the largest possible size of the sumset within the integers up to N of a subset of them having about root N elements; open, with Erdős and Freud's 1991 bounds 3/8 and 1/2 and an unreviewed 2026 note claiming 0.469.
Infinitely-often coprimality of two and three power differences, and the growth of the least bases admitting a coprime pair.
Asks whether, for every positive epsilon, infinitely many n have more than n to the power one minus epsilon integers whose Euler totient equals n; a proof is claimed by the OpenAI release of September 2026.
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.
Estimates the number of coprime pairs of integers below x that have the same sum of divisors; a lower bound with exponent 13/8 is claimed in an AI-assisted write-up of August 2026.
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.