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 every graph on n vertices has a clique transversal of at most n minus the triangle-free independence bound H(n) vertices (Erdős–Gallai); open; best bounds n − √(2n) + √2 (explicit) and n − c√(n log n) (asymptotic).
Asks whether every sufficiently large finite Sidon set has arbitrarily many pairwise sums whose neighbors one above and one below are not pairwise sums.
Asks whether the mean squared gap between consecutive elements of the sumset of a finite Sidon set grows without bound as the set grows.
Asks whether the sumset of a near-maximal Sidon set inside the first N integers is evenly spread over small moduli, for instance half even and half odd.
Asks whether the largest Sidon subset of the first N plus k integers exceeds that of the first N integers by at most one, for every fixed k and all large N.
Asks whether the first N integers contain a maximal Sidon set of size only order N to the power one third.
Asks whether there is an infinite Sidon set that is also an asymptotic basis of order three, so all large integers are sums of three of its elements.
Asks whether every infinite integer set with at most two representations of each number as a sum of two elements has counting function whose ratio to root N has lower limit zero.
Asks whether the Ramsey number for a four-cycle versus a complete graph on n vertices is at most order n to the power two minus a fixed positive constant.
Estimates the least number of colors needed for the first N integers so that every four-term arithmetic progression receives at least three distinct colors.
Asks whether the smallest size forcing balanced two-colorings of a complete uniform hypergraph varies continuously with the density parameter or jumps.
Asks whether the size threshold beyond which some two-coloring of K_n balances every large induced subgraph grows like c log n; corrected to "smallest", it is the question of Problem 563, which is open.
Asks whether graphs in which every subgraph has a vertex of degree at most a fixed bound have Ramsey number linear in the number of vertices; proved by Lee (2015 preprint, Ann. of Math. 2017), with the constant still open.
Asks whether the sum of one over n times the logarithm of n over a set with no member dividing another is largest when the set is the primes.
Asks for an asymptotic formula for the Ramsey number of a triangle versus a complete graph on k vertices; the order k^2/log k is known and the constant lies between 1/2 and 1.
Asks whether the Ramsey number of a complete graph on four vertices versus one on k vertices is at least k cubed divided by a power of the logarithm of k; proved by Mattheus and Verstraete with the fourth power.
Asks whether a graph with at most k edge-disjoint triangles can be made triangle-free by deleting at most 2k edges (Tuza's conjecture); open, the site's label falsifiable, with Haxell's 66/23 the best refereed constant.
The limiting density of the largest subset of the first N integers containing no triple of the form n, twice n, three times n, and whether it is irrational.
Estimates the largest possible sum of reciprocals of a set of integers with no arithmetic progression of k terms, and compares it to van der Waerden numbers.
The limiting value, divided by the square root of N, of the smallest subset of zero through N whose difference set covers every integer up to N.
Asks whether every subset of a fixed positive density of a large grid of words must contain a combinatorial line.
Asks whether every finite coloring of the positive integers admits arbitrarily large finite sets whose sums and products of distinct members share one color.
Asks whether every two-coloring of the plane contains a monochromatic congruent copy of every triangle, with at most one exception.
Characterizes the finite sets of points that admit a monochromatic copy in every finite coloring of a high enough dimensional Euclidean space; answered in 2026 by OpenAI's algebraic criterion, which refutes Graham's conjecture.
Asks whether the central binomial coefficient of 2n choose n fails to be squarefree for every n at least 5; proved for large n by Sárközy (1985) and for every n at least 5 by Velammal (1995) and by Granville and Ramaré (1996).