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 every graph whose chromatic number is large enough in terms of contains a triangle-free subgraph with chromatic number at least .
Asks whether, for and , some -free graph has a monochromatic in every -coloring of its edges. True, by Folkman for two colors and by Nešetřil and Rödl for every .
Asks whether every -vertex graph whose edges can be 2-colored with no monochromatic triangle has an independent set of size for some fixed . Disproved through the Alon–Rödl bound on .
Asks whether an -vertex graph avoiding has edges, where is a vertex joined to others and each pair of these has its own further common neighbor.
Asks whether the largest number of distinct clique sizes in a graph on vertices is . Disproved by Spencer, whose construction removes the term.
Asks whether the integers with and have a density, where is the largest prime factor. The OpenAI release of September 2026 shows the density is a Dickman product; this is accepted because its Lean proof was built.
Asks whether there are infinitely many four-term arithmetic progressions of pairwise coprime powerful numbers.
Asks whether every sufficiently large integer is the sum of at most three powerful numbers.
Asks whether, for every and , some -chromatic graph has every vertex critical but no critical set of at most edges. A Lean proof certified by the bounty site Conjectures.io in September 2026 settles it.
Asks whether there are infinitely many such that and have the same number of divisors.
Asks whether an exact covering system exists, that is, finitely many congruence classes with distinct moduli such that every integer satisfies exactly one of them.
Asks whether there are and such that every -coloring of the integers has a sequence with for infinitely many whose finite subset sums miss a color. No, by a 2026 AI-generated coloring that erdosproblems.com accepted after review.
Asks whether there is an infinite sequence of distinct Gaussian primes with consecutive terms a bounded distance apart. This is the Gaussian moat problem, answered negatively by an accepted 2026 claim with a Lean proof.
Asks whether the multiplicities of the smallest and largest distances among points in the plane have product at most .
Asks whether planar points with distances of multiplicities must be equally spaced on a line or a circle.
Asks how many ordinary lines points in the plane with no on a line must have to force of the points to span only ordinary lines, and whether suffice.
Asks whether the ratios of consecutive divisor counts are dense in .
Asks whether every 2-coloring of admits a set of size whose sums of two distinct elements all have one color. False in ZFC, by Komjáth and by Soukup and Weiss, after Hindman, Leader and Strauss showed it false under CH.
Asks whether, for , some set with no -term arithmetic progression has a monochromatic -term one in every -coloring. True, by Spencer's 1975 restricted van der Waerden theorem.
Asks whether complex numbers whose power sums vanish on infinitely many runs of consecutive indices must essentially be the th roots of unity, in the precise form of Tijdeman's classification.
Asks how often an irreducible with positive leading coefficient and degree , not a power of 2, takes - or -power-free values, and whether is squarefree infinitely often.
Asks whether , with the least th power nonresidue of . It is proved for every under Elliott's convention (Erdős 1961 for , Elliott 1967), and the variant over every prime with a th power nonresidue is open for composite .