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.
Estimates the least number of edges in an n-uniform hypergraph that cannot be colored with two colors but can with three.
Estimates the least order of a tournament in which every n vertices have a common dominator; open, with Erdős's 1963 upper bound and the Szekeres and Szekeres lower bound of 1965 a factor of order n apart, exact only to n = 3.
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 there is a transcendental entire function whose derivatives, along any infinite subsequence of orders, have zero sets that together are dense in the plane.
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 connected set in n-dimensional space has a connected subset that is neither a single point nor homeomorphic to the whole set.
Asks whether the size Ramsey number of every graph with n vertices and at least Cn edges exceeds the edge count by a factor growing faster than linearly in C; open, with no result found beyond Erdős's 1982 statement.
Estimates how many distinct exponents occur in the prime factorization of n factorial.
Asks whether infinitely many n have all exponents distinct in the prime factorization of n times n plus one.
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.
Separates the proved quadratic lower bound, open k=6 case, and disproved nonmultiples-of-three part of the proposed general asymptotic.
Asks whether some graph has aleph two vertices and chromatic number aleph two while every subgraph on aleph one vertices is countably colorable.
Asks whether some graph on the ordinal omega two squared has chromatic number aleph two while every subgraph of smaller type is countably colorable.
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).