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.
Characterizes which sequences of arc lengths tending to zero with infinite sum make random independent arcs cover the whole unit circle with probability one.
Asks whether, for almost all sign choices, a signed power series with small but not square-summable coefficients converges somewhere on the unit circle.
The value of the limiting growth rate per step of the number of self-avoiding walks of n steps from the origin in the k-dimensional integer lattice.
Asks whether the expected end-to-end distance of an n-step self-avoiding walk is of larger order than the square root of n in the plane, and at most of that order in every dimension at least three.
The order of the largest Sidon subset, one with no non-trivial equal pairwise sums, guaranteed inside every set of N real numbers.
Estimates the least N such that every two-coloring of the integers up to N contains a set of k numbers all of whose non-empty subset sums have the same color.
Asks whether every two-coloring of the natural numbers admits an infinite set all of whose finite non-empty subset sums share one color; yes, by Hindman's theorem, held in his 1974 paper and Baumgartner's 1974 note.
Asks whether a graph on n vertices with no complete subgraph on five vertices and a positive edge density has a triangle-free set of linearly many vertices.
The largest subset of the integers up to N that contains N itself and in which every two distinct elements share a common factor greater than one.
Estimates the largest subset of the integers up to N containing no r elements whose pairwise greatest common divisors are all equal, for r at least three.
The largest subset of the integers up to N containing no three distinct elements whose three pairwise least common multiples are all equal.
Asks whether every subset of the integers up to N of positive density contains three elements which become equal after multiplying each by a distinct prime.
The best upper bound for the reciprocal sum of a set of integers up to N in which every number has at most r representations as a prime times a set element.
Estimates the least possible size of the set of ratios of each element to the greatest common divisor of a pair, over all sets of n natural numbers.
Asks whether any subset of the integers modulo N of size at least a constant times the square root of N has a non-empty subset summing to zero modulo N; proved by Szemerédi in 1970 for all finite abelian groups.
Asks whether p residues modulo p, whose zero-sum non-empty subsets all have the same size, must take at most two distinct values; Graham's conjecture, proved for large primes in 1976 and for every modulus in 2010.
Asks whether a set of integers up to n with pairwise least common multiples above n has reciprocal sum at most 31/30, and whether a positive proportion of the integers up to n avoid its multiples; yes and no, Schinzel-Szekeres.
Asks whether the number of random elements of an abelian group of order N whose subset sums cover it is at most log base two of N plus a small error.
Asks whether the gap between consecutive Ramsey numbers of a triangle against a complete graph tends to infinity, and whether it is smaller than order k; open, with the gap known only to lie between 3 and k+1.
Asks whether, for all large m, the graph with m edges that is as complete as possible has the largest Ramsey number among graphs with m edges and no isolated vertices; open, while the site's wording, for every m, fails at two edges.
Asks whether the Ramsey number of any graph with m edges and no isolated vertices is at most exponential in the square root of m.
Asks whether every tree on n at least 2 vertices has Ramsey number at most 2n minus 2; proved, since 2026 on a third party's Lean proof built here, while the site's wording fails for the one-vertex tree.
Records the proved Erdős–Sós tree edge bound and the precise relation between its sharp threshold and the site's statement.
Asks whether a tree that is bipartite with k vertices in one class and two k in the other has Ramsey number exactly four k minus one.
Asks for a proof bounding the Ramsey number of a large tree against a complete multipartite graph by a formula in its chromatic number and smallest class size.