Problems
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
618 of 1,221 problems match
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Asks whether the density of integers with two divisors exists and equals , so that almost every integer has such a pair.
Asks whether every bipartite -degenerate graph has ; disproved at by Theorem 1.2 of Chapter 10 of OpenAI's 2026 report, which the erdosproblems.com curator credits.
Asks whether every bipartite graph of minimum degree has for some .
Asks whether for some , where is the maximum number of minimal cuts (minimal disconnecting vertex sets) of a graph on vertices. It is proved, and refereed papers place between and the golden ratio.
Asks whether, for every , each sufficiently large finite Sidon set has at least sums with .
Asks whether, for a Sidon set with , the sumset is evenly spread over small moduli, for instance half even and half odd.
Asks whether some infinite Sidon set is an asymptotic basis of order , so that every large integer is a sum of three of its elements.
Asks whether every graph on vertices in which each subgraph has a vertex of degree at most satisfies . Lee proved it (2015 preprint, Ann. of Math. 2017), and the constant is still open.
Asks whether the sum of over a primitive set , one in which no member divides another, is largest when is the set of primes.
Asks to prove that ; proved by Mattheus and Verstraete, with the fourth power of the logarithm.
Asks whether, for every and integer , every subset of of size at least contains a combinatorial line once is large enough.
Asks whether every two-coloring of the plane contains a monochromatic congruent copy of every triangle, with at most one exception.
Asks for a characterization of the Ramsey sets: the finite point sets with a monochromatic copy in every finite coloring of for large enough . OpenAI answered it in 2026 with an algebraic criterion that refutes Graham's conjecture.
Asks whether fails to be squarefree for every . Proved for large by Sárközy (1985), and for every by Velammal (1995) and by Granville and Ramaré (1996).
Asks whether one function can keep the initial partial sums along each of infinitely many prescribed integer sequences bounded.
Asks for upper bounds on , the least number of -term arithmetic progressions that forces a set of integers to contain an -term one, for . Also asks whether and for every .
Asks whether every finite family of forbidden graphs has a member whose extremal number is comparable to the family's, .
Asks, for each , for the maximum number of edges of a graph on vertices with no -regular subgraph, and whether it is .
Asks for , where is the least such that every -coloring of the edges of has a monochromatic triangle.
Asks whether every graph on vertices decomposes into edge-disjoint cycles and single edges (the Erdős–Gallai cycle decomposition conjecture). The answer is yes, by the OpenAI release's 2026 theorem.
Asks whether , where is the largest size of a subset of with no three points on a line.
Asks for the order of growth of , the largest size of a subset of 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 area.
Asks whether , where is the least such that every coloring of has a monochromatic or a rainbow -term arithmetic progression; proved by Bae and by Fox and Hunter in 2026 preprints.
Asks whether, for every and large , every -coloring of the pairs from has a set with all its pairs one color and ; proved by Rödl, with the order of growth determined by Conlon, Fox and Sudakov.