Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
606 of 1,221 problems match
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Asks whether a graph on n vertices with no large clique or independent set has many induced subgraphs that pairwise differ in vertex count or edge count.
Asks whether a graph on n vertices with no large clique or independent set has an induced subgraph on many vertices realizing many distinct degrees.
Asks whether any two-coloring of the edges of K_n leaves at most n²/4 edges on no monochromatic triangle for large n, as Erdős stated it; proved by Keevash and Sudakov's exact theorem, while the site's wording fails for n from 3 to 6.
Asks whether a high enough chromatic number forces a graph to contain k edge-disjoint cycles on the same vertex set, for every k.
Asks whether every two-coloring of the positive integers has a monochromatic three-term progression whose difference exceeds its first term; proved by Brown and Landman in 1999, with an elementary argument recorded by the site.
Asks whether, for any finitely many distinct primes, infinitely many n make n factorial divisible by an even power of each of those primes.
Estimates the length of the longest chain of integers below n whose greatest prime factors are strictly decreasing.
Asks whether for any two primes p and q there is an integer n whose greatest prime factor is p while that of n plus one is q.
Asks for the least number of distinct multiples of distinct members of an m-set in the first N integers that every interval of length 2N holds; it is min(m, ceiling of 2 root m), by van Doorn, Li and Tang (2026); not root m.
Asks whether the number of points in general position in k-dimensional space needed to guarantee n of them in convex position grows exponentially in n.
Asks whether the least possible number of distinct distances from the k-th of n planar points, in units of root n, grows with k; Erdős's first guess, that it is unbounded already at k = 3, fails by a construction of Elekes.
Asks whether n points in the plane can take almost n different values among the counts of distinct distances from each point to the others; yes by a Lean proof certified by Conjectures.io, unrefereed, kernel-checked by that site.
Asks whether every set of positive upper density contains, after some shift, all pairwise sums of distinct members of an infinite subset.
Asks whether every subset of the N by N grid of positive density contains the four vertices of a square, once N is large enough.
Asks whether n planar points can have every four of them determining at least three distances while the total number of distinct distances is far below n.
Concerns families of subsets of the first n integers, each of size above a constant times the square root of n, with any two sharing at most one element.
Asks whether every subgraph of the n-dimensional hypercube with a positive fraction of its edges contains a six-cycle, once n is large enough.
Asks whether the sum of the ratios of consecutive divisors of n tends to infinity for almost all n, and seeks an asymptotic formula for its average.
Asks whether x to the power x times y to the power y equals z to the power z has integer solutions with x, y and z all greater than one.
Asks whether infinitely often a block of k consecutive integers has a larger least common multiple than a later block of k+1; proved in a strong form by Cambie (2024, arXiv), the ratio exceeding any constant.
Asks whether almost every n admits an integer strictly between the nth and next prime whose least prime factor is at least the gap between those primes.
The density of the integers whose kth smallest prime factor is a given prime p, and how that density behaves as k and p vary.
Asks whether the density of integers with exactly one divisor in an interval from n to m is unimodular in m; disproved by Cambie, who also shows many local maxima.
Estimates how large the ratio of the largest to the smallest integer with a given value of Euler's totient function can be for values up to x.
The longest chain of primes dividing n, and the longest chain of divisors of n, in which each term is congruent to 1 modulo the previous term.