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 some threshold exponent splits the density of integers with a divisor above 1 congruent to 1 modulo m into a limit of zero below and one above.
Asks whether the greatest common divisor of n choose i and n choose j always tends to infinity with n, uniformly over all i and j between 2 and half of n.
Asks whether, for k at least 4 and n large in terms of k, more k-subsets of the first n integers than those through a fixed pair force two meeting in one point; Frankl proved it, while the site's wording, with no range, fails.
The largest family of subsets of the first n integers in which no two members intersect in exactly r elements.
Asks whether some girth bound forces every finite unit distance graph in the plane to be 3-colorable.
Asks whether every finite Sidon set of integers can be extended to a perfect difference set modulo p squared plus p plus 1 for some prime p.
Asks whether every 4-regular graph contains a 3-regular subgraph, and whether some degree r forces one in every r-regular graph; both answered yes by Tashkinov in 1982, for degree 4 and for every degree at least 3.
Asks whether the largest 3-uniform hypergraph on n vertices containing no three edges spanning six vertices has o(n squared) edges, fewer than any fixed fraction of n squared for large n.
Asks whether the chromatic number of an n-vertex graph is at most a constant times n^{1/2}/log n times the order of its largest clique subdivision; the Erdős–Fajtlowicz conjecture, proved by Fox, Lee and Sudakov in 2013.
Asks whether a constant times r squared times n edges on n vertices always force a subdivision of the complete graph on r vertices; the conjecture of Erdős, Hajnal and Mader, proved by Bollobás–Thomason and Komlós–Szemerédi.
Asks whether the size Ramsey number of the path grows faster than linearly but slower than quadratically, and whether that of the cycle is subquadratic; both are linear, so the first answer is no and the others yes.
Bounds the least n such that every red-blue coloring of 1 up to n has a red three-term progression or a blue k-term one; Green, Hunter and Schoen meet the two explicit challenges while the order of magnitude stays open.
Asks whether a Steiner system on n points with blocks of size k covering every r-set once exists for large n whenever the divisibility conditions hold.
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 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.
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 contain an edge lying on a cycle of every sufficiently large length.
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.
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.