Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
99 of 1,221 problems match
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Asks whether a graph of infinite chromatic number m must contain a subgraph of the same chromatic number with no odd cycle of length at most r.
Asks whether a graph on n vertices of diameter two in which deleting any edge raises the diameter has at most n squared over four edges; proved by Füredi for all large n, with one unreviewed proof claim for every n.
Asks whether the proportion of n up to N such that every prime factor p of n has a divisor of n above one congruent to one mod p decays like exp(-(c+o(1)) sqrt(log N) log log N).
Asks how large n must be, in terms of r, for an antichain of subsets of one to n in which every occurring size is used at least r times to reach n minus 3 distinct sizes; three claims are pending, none accepted.
Asks whether, for every small epsilon, some set of natural numbers of density above one minus epsilon has equal products only between equally many factors.
The least total size of a set B in (2n, 4n) plus a largest C in (n, 2n) whose distinct pairs never sum into B; Choi's interval function, between n^(1/2) and n^(3/5+o(1)), with an unreviewed 2026 claim of the conjectured n^(1/2+o(1)).
The largest subset guaranteed inside any n integers in which equal sums of elements can only occur between equally many terms.
The largest subset guaranteed inside any n integers in which no element equals the sum of two or more other distinct elements of the subset; known to lie between the square root of n log n over log log n and n over log n.
The largest subset of one to n in which every number has fewer than k representations as a product of two distinct members; asks whether the second-order term for k equal to three has an asymptotic constant.
Asks whether a graph with 2n + 1 vertices and n^2 + n + 1 edges has two equal-degree vertices joined by a path of length 3; corrected to n at least 2, since n = 1 (the triangle) fails; proved for n at least 600 by Chen and Ma and claimed for every n at least 2 by Liu and Zeng.
Asks whether, for every positive epsilon, infinitely many n have more than n to the power one minus epsilon integers whose Euler totient equals n; a proof is claimed by the OpenAI release of September 2026.
Asks whether the largest set of integers up to N with no two members whose product plus one is squarefree is those congruent to seven mod twenty-five.
Asks whether representation counts growing like a constant times the logarithm force an additive basis of order k to contain a minimal one, for k at least 3.
Determines how small the gaps of an infinite sum-free set of naturals can be, and whether the nth gap can stay below n.
Concerns additive bases of order k that are minimal, in the sense that removing any infinite subset destroys the basis property.
Asks whether a subset of one to n above the triangle threshold of the coprime graph forces all odd cycles up to n/3 + 1 and, for large n, complete (1, l, l) tripartite subgraphs; the second was settled by Sárközy in 1999.
Asks whether there is a transcendental entire function whose derivatives, along any infinite subsequence of orders, have zero sets that together are dense in the plane.
Determines the largest number of unit distances among n disjoint translates of a compact convex set, in particular whether it exceeds n to a power above 1.
Asks whether the least prime congruent to a modulo d exceeds a fixed factor above Euler's totient of d times log d for many residues a; two 2026 proof claims answering yes, one with a Lean development, pending and unreviewed.
Asks whether n complex numbers of modulus at least one, the first equal to one, can keep all their power sums below an exponentially small bound.
Asks whether the sequence counting the independent sets of each size in a tree or forest is unimodal.
Asks how fast a square integrable function's Fourier partial sums must converge for its averages along alpha times a lacunary sequence to equal its integral.
Estimates the fewest edges beyond n for an n-vertex graph to have cycles of every length from three to n; the excess is at least log_2(n-1) - 1, Bondy claimed log_2 n plus an iterated logarithm, and a 2026 proof claim is pending.
Determines the smallest and largest measure of the set where a monic real polynomial with all roots real in minus one to one has absolute value below one.
The radius of the largest disc inside the region where a monic complex polynomial with all roots in the unit disc has absolute value below one.