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 only finitely many with have the next two primes and as the only prime factors of .
Asks for the size of the largest subset of in which no element divides two other distinct elements, and whether is irrational. A Lean proof certified by Conjectures.io gives an exact formula and an irrational limit near 0.67297.
Asks whether for almost all and the reverse inequality holds for infinitely many . Luca and Pomerance (2002) proved the first part, and Grytczuk, Luca and Wójtowicz (2001) the second.
Asks whether every graph of chromatic number contains an infinitely connected subgraph of chromatic number .
Bounds the number of lines containing at least of points in the plane by for . The bound fails as worded at , and Szemerédi and Trotter proved it for .
Asks whether a finite family of pairwise disjoint unit segments in the unit square can be maximal, so that no further unit segment can be added.
Asks whether, for , the most edges of a -uniform hypergraph on vertices with no vertices spanning edges for any is asymptotic to . The version as printed, with only the single family , is false.
Asks whether every graph on vertices with edges has an almost-regular subgraph on vertices with at least edges. It is false as written; on erdosproblems.com's account of a 2025 preprint, is the right size.
Asks whether an -partite graph with vertices in each part and minimum degree at least must contain a . Proved by Haxell, with the exact threshold following from Haxell and Szabó by complementation.
Asks whether, for , a graph on vertices with at least edges has a vertex of degree whose neighborhood has at least edges. Proved by Bollobás and Thomason in 1981 and strengthened by Bondy in 1983.
Asks whether some makes every bipartite graph on vertices with a part of vertices and at least edges contain a . Disproved by the superlinear -free constructions erdosproblems.com credits, whose papers are not held.
Asks whether the number of that are sums of two squarefull numbers is asymptotic to for some .
Asks to estimate , the least number such that any points in determine at least distinct distances, and whether exists.
Asks whether, for each , some finite set in the plane has the property that every -coloring of it gives a line meeting it in at least points, all of the same color.
Asks whether every -free graph with chromatic number contains an odd cycle with at least two diagonals. Erdős first asked for one diagonal, which Larson proved in 1979.
Asks whether , in particular for , where is the largest function such that a graph whose every -vertex subgraph is an -colorable graph plus at most edges has chromatic number at most .
Asks whether, for every slightly above , the gaps between consecutive finite sums of distinct powers of tend to ; proved by Erdős and Komornik (1998), Akiyama and Komornik (2013) and Feng (2016), each for a range of .
Asks whether, if the non-commuting graph of a group has no infinite complete subgraph, its complete subgraphs have bounded size. The graph has the group elements as vertices and joins pairs that do not commute.
Asks whether, for each , the sum over consecutive divisors of has limit inferior bounded in terms of as .
Asks how fast a sequence must increase if, for every , only finitely many make squarefree (property ), or if, for infinitely many , every with makes squarefree (property ).
Asks for the anti-Ramsey numbers of cycles and paths, the most colors on the edges of without a rainbow copy. It proposes an asymptotic formula for cycles and an exact formula for paths.
Asks whether, for gap bounds and , every sufficiently lacunary sequence misses the -fold sumset of some sequence with gaps between and .
Asserts that if the roots of a real polynomial form an arithmetic progression, then the gaps between consecutive zeros of increase from the midpoint of toward the endpoints.
Asks how slowly the length in of a path on which an entire of finite order tends to can grow, and whether is possible; disproved at every finite order, even for growing arbitrarily close to the threshold that guarantees radial paths.
Asks whether some meromorphic (or entire) has for every , where counts the roots of in .