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.
Estimates, for subsets A and B of {1,...,N}, the largest possible number of integers with exactly one representation ab with a in A and b in B; the order of magnitude is N^2/((log N)^delta (log log N)^(3/2)).
Asks whether an additive function whose values on prime powers are unboundedly large compared with the logarithm must have consecutive differences unboundedly large compared with log n, or even unbounded ratios.
Asks whether the sum of distances from an interior point to a triangle's vertices is at least twice the sum of its distances to the three sides.
Asks whether every infinite set of density zero has difference set counts that are infinitely often arbitrarily larger than its own counting function.
Asks whether the uniform random graph with n vertices and cn edges, c above one half, almost surely has a path of length f(c)n with f tending to 0 at one half and to 1 at infinity; proved by Ajtai, Komlós and Szemerédi, 1981.
Concerns block designs on p squared plus p plus one points, for a prime power p, in which every pair of points lies in exactly one block.
Asks whether, for n at least r, a graph with n vertices and at least the Turán number of edges for r plus one has an r-clique of degree sum at least 2rm/n; proved by Bollobás and Nikiforov in 2005, while the site's wording, with no range, fails below r vertices.
Asks whether every graph on n vertices with more than n^2/4 edges has an edge on at least n/6 triangles; proved by Khadzhiivanov and Nikiforov in 1979, by Edwards (unpublished) and by Bollobás and Nikiforov in 2005.
Asks whether a real function whose every fixed-shift difference is continuous must be the sum of a continuous function and an additive one.
Asks whether a real function whose every fixed-shift difference is measurable splits into measurable, additive and almost-everywhere-shift-invariant parts; the site prints continuous.
Asks whether, for each n at least two, there is a space of dimension n whose square also has dimension n.
Asks whether every graph on rm vertices with minimum degree at least m(r−1) has m vertex-disjoint copies of K_r; Erdős's conjecture, proved by Hajnal and Szemerédi in 1970 and reproved in refereed papers of 2008 and 2010.
Asks whether a graph with 1+n(m−1) vertices and 1+n·C(m,2) edges has two vertices joined by m disjoint paths; false for m at least 5 if the paths are vertex-disjoint, true for every m if edge-disjoint; the site labels it solved.
Asks whether, for n at least 4, every graph with n vertices and 2n−2 edges has a cycle and a further vertex adjacent to three of its vertices; proved by Thomassen in 1974, while the site's wording, with no range, fails at n = 1.
The largest possible chromatic number of a graph on n vertices containing no complete graph on k vertices.
Asks whether, for every k at least 4, the longest odd cycle avoidable in a k-chromatic graph on n vertices has length about the (k minus 2)th root of n.
Asks whether a graph in which every subgraph on n vertices has an independent set of size at least (n minus k)/2 has chromatic number at most k plus 2.
Asks whether every graph whose chromatic number is large enough in terms of k contains a triangle-free subgraph with chromatic number at least k.
Asks whether, for k at least 2 and l at least 3, some graph with no clique on l plus 1 vertices forces a monochromatic l-clique in every k-edge-coloring; true, by Folkman for two colors and by Nešetřil and Rödl for every k.
Asks whether every n-vertex graph whose edges can be 2-colored with no monochromatic triangle has an independent set above the cube root of n by a power; disproved through the Alon–Rödl bound on R(3,3,m).
Bounds by n to the power three halves the edges of an n-vertex graph avoiding a fixed graph made of a vertex joined to k others whose pairs are linked.
Asks whether the largest number of distinct clique sizes in a graph on n vertices is n minus log_2 n minus the iterated-logarithm count, up to O(1); disproved by Spencer, whose construction removes the iterated term.
Asks whether the density exists of integers n whose largest prime factor is below n to the alpha while that of n plus 1 is below n plus 1 to the beta; the OpenAI release of September 2026 shows it is a Dickman product, accepted on its built Lean proof.
Asks whether there are infinitely many four-term arithmetic progressions made of pairwise coprime powerful numbers.
Asks whether every sufficiently large integer is the sum of at most three powerful numbers.