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.
Bounds the least N forcing every plus-minus-one sign pattern to have a k-term arithmetic progression with partial sum of absolute value at least a given size.
The smallest bound, as a function of the common difference, on the largest partial sum along arithmetic progressions of a single plus-minus-one sign function.
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.
Asks whether the Ramsey number of the n-dimensional hypercube graph is at most a constant times its number of vertices; open on the site, with the linear bound claimed in full by a 2026 OpenAI release preprint.
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.
The best length, in the common difference d, of a monochromatic progression of difference d forced for infinitely many d in every two-coloring of the integers; at most (1 + o(1)) log_2 d by Beck 1980, with no usable lower bound known.
The least number of terms k such that the plane can be two-colored avoiding red points at unit distance and blue unit-spaced progressions of k terms; Erdős and Graham's question, with the step left free, has no finite answer.
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.
The largest number of terms k such that every permutation of the integers contains a monotone arithmetic progression of k terms.
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.
Asks whether the positive integers split into two sets, each of which can be permuted to avoid monotone three-term arithmetic progressions.
Asks whether the complement of a set of integers with all pairwise sums distinct must contain an infinite arithmetic progression.
Asks whether the complement of a set of reals with no three-term arithmetic progression must contain an infinite arithmetic progression.
Asks whether the longest arithmetic progression of primes below N has length a vanishing fraction of the logarithm of N.