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 least number of distinct prime factors of the product of the sums of two distinct elements of a set of n natural numbers grows faster than the logarithm of n.
Asks whether the excess over a known bound in the number of edges of a largest bipartite subgraph of a graph with m edges is unbounded along some sequence of m.
Asks whether a graph on n vertices whose every induced subgraph on at least half the vertices has more than n squared over fifty edges has a triangle.
Asks for a bound of the form C^(sqrt n) on the least N forcing, in any r-coloring of K_N, n vertices missing some color's triangle; a random coloring refutes the site's wording, and no source gives another intended form.
Asks how large the chromatic and clique numbers can be for the integer-distance graph on an infinite plane set with no three collinear and no four concyclic.
Estimates the largest subset of the first N integers in which no element divides the sum of any distinct others; the displayed root-N question is answered no, and the order carries one unreviewed claim of exponent 1/5.
Asks whether any n points in the plane give two distances each occurring between at most n pairs, and whether the number of such distances grows.
Determines the growth of the largest degree forced in every triangle-free graph on n vertices of diameter two, in particular whether it beats root n.
Asks whether a triangle-free graph on n vertices with maximum degree below n to the power one half minus epsilon can reach diameter two by adding few edges.
Asks whether a set of n points in the plane in which every four points give at least five distinct distances must determine order n squared distinct distances.
Determines the least number of edge colors of the complete graph on n vertices such that every four vertices span at least five colors.
Asks whether the product of k consecutive positive integers, for some k at least three, can ever be powerful, meaning every prime dividing it divides it twice.
Improves bounds on the van der Waerden number, the least N forcing a monochromatic k-term progression in any two-coloring, and whether its k-th root grows.
Asks whether the largest subset of the first N integers with no non-trivial k-term arithmetic progression has size a vanishing proportion of N.
Asks whether the largest subset of the first N integers with no three-term arithmetic progression is smaller than N over any fixed power of the logarithm of N.
Asks whether, for every k at least three, there are k consecutive primes forming an arithmetic progression.
Asks for an asymptotic formula for the largest subset of the first N integers containing no non-trivial k-term arithmetic progression.
Asks whether a countable set of reals above one where every integer multiple of an element is at distance one or more from another must be sparse.
Asks whether almost every integer has two divisors with the larger less than twice the smaller, so that the density of such integers exists and equals one.
Asks whether the average of the alpha-th power of gaps between consecutive squarefree numbers up to x has a limit for every non-negative alpha.
Asks whether a bipartite r-degenerate graph has extremal number at most n to the power two minus one over r; disproved at r equal to two by Theorem 1.2 of Chapter 10 of OpenAI's 2026 report, credited by the site's curator.
Asks whether every bipartite graph of minimum degree r has extremal number at least order n to the power two minus one over r minus one, plus a positive gain.
Estimates the number of ways to write one as a sum of reciprocals of k distinct increasing positive integers.
Asks whether the strong chromatic index of any graph, the least number of induced matchings partitioning its edges, is at most five quarters of the squared maximum degree; open, with the refereed record at 1.772 times it.
Asks whether the n-th root of the maximum number of minimal disconnecting vertex sets of a graph on n vertices tends to a limit below two; proved, the limit lying between 1.4457 and the golden ratio by refereed papers.