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, for k at least five, the most edges of a 3-uniform hypergraph on n vertices with no j vertices spanning j minus two edges for any j from four to k is asymptotic to n squared over six; false for the single family as printed.
Asks whether every graph with n^{1+α} edges has an almost-regular subgraph on more than n^{1−α} vertices with εm^{1+α} edges; false as written, with n^α the right size on the site's account of a 2025 preprint.
Asks whether an r-partite graph with n vertices per part and minimum degree about (r − 3/2)n must contain a complete graph on r vertices; proved by Haxell, with the exact threshold from Haxell and Szabó by complementation.
Asks whether a graph with the Turán number of edges has a linear-degree vertex whose neighborhood has the Turán number of edges for r − 1; proved by Bollobás and Thomason in 1981, strengthened by Bondy in 1983.
Asks whether a bipartite graph on n vertices with a part of size about n^(2/3) and at least cn edges must contain a six-cycle; disproved by the superlinear 6-cycle-free constructions credited by the site, papers not held.
Asks whether the count of integers up to x that are sums of two squarefull numbers is asymptotic to a constant times x over the square root of log x.
Asks whether n points in the plane with no three collinear always determine at least the floor of n/2 distinct distances, even as seen from a single point.
Estimates the least number of distinct distances determined by n points in d-dimensional space, asking whether it is nearly n to the power two over d.
Estimates the largest number of pairs at distance exactly one among n points in d-dimensional space that are pairwise at distance at least one.
Estimates the largest possible number of pairs at distance exactly one among n points in d-dimensional space.
Estimates the largest number of triangles of equal area whose vertices come from a set of n points in the plane.
Estimates the largest number of four-point subsets with two pairs at equal distance among n points in the plane, and whether it is nearly n cubed.
Estimates how many points in d dimensions force n of them with all pairwise distances distinct, and whether that count is subexponential in d.
Estimates the fewest points in d-dimensional space guaranteeing at least n distinct distances, and whether dividing it by d to the n minus one has a limit.
Asks whether, for each k at least 3, some finite planar set has every two-coloring giving a line whose at least k points of the set share one color.
Asks whether every graph with chromatic number four and no complete graph on four vertices contains an odd cycle with at least two diagonals; Erdős first asked for one diagonal, which Larson proved in 1979.
Determines the largest f so that a graph whose every m-vertex subgraph is an r-colorable graph plus at most f edges has chromatic number at most r plus one.
Studies the deficiency of n choose k, the number of the k integers from n downwards whose prime factors are all at most k, when no prime up to k divides it.
Asks whether the least prime factor of n choose k is at most the larger of n over k and k for all n at least 2k, with only finitely many exceptions.
Estimates the smallest n greater than k plus one for which every prime factor of n choose k exceeds k.
Asks whether the gaps between consecutive finite sums of distinct powers of q tend to zero for every q slightly above one; proved by Erdős and Komornik (1998), Akiyama and Komornik (2013) and Feng (2016), each for a range of q.
Determines how many values can arise as the common difference of a three-term arithmetic progression inside a set of n integers.
Concerns the non-commuting graph of a group, whose vertices are the group elements and whose edges join pairs that do not commute.
Asks whether the sum of the ratios of consecutive divisors of n minus one, each raised to a power alpha above one, has bounded limit inferior over all n.
Concerns the number of consecutive pairs of divisors of n that are coprime.