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 the sum of one over p, over primes p at most n whose remainder of n lies in the upper half of the interval up to p, is about half of log log n.
Asks, for each k at least 2, whether the square of the factorial of n plus k divides the factorial of two n for infinitely many n.
Asks whether infinitely many triples a, b, n with a plus b above n plus C log n have a! b! dividing n! (a+b-n)!; answered yes in 2026 by an AI-generated proof credited to Barreto and, separately, by Pomerance.
Asks whether infinitely many triples a, b, n have a plus b above n plus C log n while n! over a! b! has only bounded primes in its denominator; answered yes in 2026 by an AI-generated proof credited to Barreto and Price.
Asks whether infinitely many pairs of distinct integers n and m give central binomial coefficients with exactly the same set of prime divisors; answered yes in 2026, with consecutive pairs, by an AI proof credited to Price.
Asks for a function describing, for almost all n, the least integer that fails to divide the central binomial coefficient of n.
Asks whether at least exp(c n^(1/2) log n) increasing sequences of block sizes arise from a design on n points in which every pair of points lies in exactly one block.
Bounds by exp(O(n^{1/2})) the number of nondecreasing sequences that can be the point counts of lines, each through at least two of n points in the plane.
Asks for a non-trivial pairwise balanced design on n points in which each block size is used at most about the square root of n times.
Determines when n points in the plane can be given positive weights so that every line through at least two of them has the same total weight.
Asks whether a graph of chromatic number aleph one must, for every cardinal m, admit a graph of chromatic number m all of whose finite subgraphs occur in it.
Asks whether a graph of chromatic number aleph one must contain an edge lying on a cycle of every sufficiently large length.
Asks whether every triangle-free graph of infinite chromatic number contains every tree as an induced subgraph.
Asks whether a graph of infinite chromatic number m must have a subgraph of chromatic number n for every infinite cardinal n below m.
Asks whether a graph of infinite chromatic number m must contain a subgraph of the same chromatic number with no odd cycle of length at most r.
Asks whether every set of naturals whose sumset has positive upper density splits into two parts whose sumsets both do, and whether some basis of order two has no split in which both self-sumsets have bounded gaps.
Asks whether a graph on n vertices of diameter two in which deleting any edge raises the diameter has at most n squared over four edges; proved by Füredi for all large n, with one unreviewed proof claim for every n.
Asks whether the complete graph on n vertices can always be split into edge-disjoint copies of given trees with 2, 3, up to n vertices; the tree packing conjecture of Gyárfás, open, with one arXiv proof claim withdrawn.
Estimates the fewest edges whose deletion makes bipartite some n-vertex graph of chromatic number k in which every proper subgraph has smaller chromatic number.
Asks for the size of the second largest component of the random graph on n vertices with edge probability one over n; the site credits Komlós, Sulyok and Szemerédi's supercritical log n bound; Aldous (1997) gives n^(2/3).
Asks whether the uniform random graph on n vertices with slightly more than half of n times log n edges is almost surely Hamiltonian; the Erdős-Rényi conjecture, settled by Korshunov and by Komlós and Szemerédi.
Determines how many edges a random three-uniform hypergraph on three n vertices needs so that it almost surely has n disjoint edges.
Asks whether the number of sum-free subsets of 1 up to n is two to the power of half of n times one plus a vanishing term.
Asks whether a set of naturals can have a sumset of lower density near one while every integer has boundedly many representations as a sum of two elements.
Asks, for any function tending to infinity, whether some graph of infinite chromatic number has every m-vertex subgraph containing a large independent set.