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 n-th root of the maximum number of minimal disconnecting vertex sets of a graph on n vertices tends to a limit below two; proved, the limit lying between 1.4457 and the golden ratio by refereed papers.
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 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 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 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 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 every subset of a fixed positive density of a large grid of words must contain a combinatorial line.
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).
Asks whether one plus-minus-one function can keep the initial partial sums along each of infinitely many prescribed integer sequences bounded.
Bounds how many k-term arithmetic progressions a set of N integers can have before it must contain a longer progression of a given length.
Asks whether every finite family of forbidden graphs contains one member whose own extremal edge count is comparable to that of the whole family.
The maximum number of edges on n vertices with no k-regular subgraph, and whether it is barely more than linear in n, for every k at least 3.
Determines the limit of the k-th root of the least order forcing a monochromatic triangle in every k-coloring of a complete graph.
Asks whether every graph on n vertices decomposes into at most a constant times n edge-disjoint cycles and single edges, the Erdős-Gallai cycle decomposition conjecture; answered yes by the OpenAI release's 2026 theorem.
Asks whether the largest subset of the ternary cube of dimension n with no three points on a line has size a vanishing fraction of three to the n.
The order of growth of the largest subset of the first N integers in which no element is the average of two or more other elements.
Asks whether every finite coloring of the plane has a color class containing the vertices of a rectangle of every possible area.
Asks whether the least N forcing a monochromatic or a rainbow k-term arithmetic progression in every coloring of [N] has k-th root growing faster than k; proved by Bae and by Fox and Hunter in 2026 preprints.
Asks whether every two-coloring of the pairs from 2 up to n yields a monochromatic complete set whose reciprocal-logarithm sum is arbitrarily large; proved by Rödl, with the order determined by Conlon, Fox and Sudakov.
Determines in which dimensions an infinite walk taking positive unit-vector steps must contain a three-term arithmetic progression.
Asks whether an infinite walk in the integer lattice of dimension three with steps from a finite set must contain three collinear points.
Asks whether every ordering of the real numbers contains an increasing or decreasing arithmetic progression of k terms, for k at least 3.
Asks whether every permutation of the positive integers contains a monotone arithmetic progression of four terms; a Lean-checked construction certified by the bounty site Conjectures.io in September 2026 gives one with none.