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 how large n must be, in terms of r, for an antichain of subsets of one to n in which every occurring size is used at least r times to reach n minus 3 distinct sizes; three claims are pending, none accepted.
Asks how many comparable pairs a family of m subsets of one to n can have for m near 2^(n/2); three questions answered yes, no, yes by Alon and Frankl and by Alon, Das, Glebov and Sudakov.
Asks whether the first player can win the game of alternately coloring edges of a complete graph so that her largest monochromatic clique beats her opponent's.
Asks whether, for the product P of the first n primes, there is always a prime p between the n-th prime and P such that P plus p is prime.
Asks whether t-coloring the edges of the complete r-uniform hypergraph on enough vertices forces some color class to contain k pairwise disjoint edges; proved by Alon, Frankl and Lovász in 1986 (Lovász 1978 for k = 2).
Estimates the least n such that every two-coloring of one to n has a monochromatic k-term descending wave, and whether it is k squared minus k plus one.
Asks whether the squares contain arbitrarily long progressions with bounded gap error, and arbitrarily large sets of all zero-one sums of given numbers.
Asks which set of pairwise coprime integers between two and N, with reciprocal sum at most a fixed constant, leaves the fewest integers up to N divisible by none of its elements; read, with the site, up to o(N), where the largest primes up to N are optimal.
Asks whether a bounded reciprocal sum for a set of divisors forces at least x over a power of log x integers up to x divisible by none of them.
Asks whether two infinite sets whose sumset covers all large integers and whose counting functions multiply to about x must have that product exceed x by an amount tending to infinity.
Asks whether, for every small epsilon, some set of natural numbers of density above one minus epsilon has equal products only between equally many factors.
The largest subset guaranteed inside any n real numbers with no two distinct elements summing to a member of the set; the Erdős–Moser function, between a power of log n above the first and exp(O(sqrt(log n))).
The least total size of a set B in (2n, 4n) plus a largest C in (n, 2n) whose distinct pairs never sum into B; Choi's interval function, between n^(1/2) and n^(3/5+o(1)), with an unreviewed 2026 claim of the conjectured n^(1/2+o(1)).
The largest subset guaranteed inside any n integers in which equal sums of elements can only occur between equally many terms.
The largest subset guaranteed inside any n integers in which no element equals the sum of two or more other distinct elements of the subset; known to lie between the square root of n log n over log log n and n over log n.
Estimates the fewest elements of zero to n whose pairwise sums cover zero to n (the smallest finite additive 2-basis); its square lies between 2.181 n and 3.458 n, and the guess 2 sqrt(n) is refuted (Hämmerer-Hofmeister, Mrose).
Estimates the largest sum-free subset, having no solution to a plus b equals c, guaranteed inside any set of n integers; the main term n/3 is settled and the second-order term lies between c log log n and o(n).
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 subset of one to n in which every number has fewer than k representations as a product of two distinct members; asks whether the second-order term for k equal to three has an asymptotic constant.
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.