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.
Asks whether a graph of chromatic number four can have arbitrarily large gaps between consecutive cycle lengths, and whether this is possible with large girth.
Asks whether a graph with minimum degree k and no cycle of length at most twice s must have at least a constant times k to the power s distinct cycle lengths.
Asks whether some constant c > 0 makes the list chromatic numbers of every n-vertex graph and its complement sum to more than n^(1/2 + c).
Estimates the largest f(n) for which some set of n points in four-dimensional space has every point equidistant from at least f(n) of the others.
Asks whether n points in six-dimensional space span at most about one twenty-seventh of n cubed unit equilateral triangles.
Asks whether a set of n points in the plane can determine on the order of n distinct distances each occurring for more than n pairs of points.
Determines the best constant c such that n reals whose every four-element subset has at least eleven differences contain a Sidon set of size c times n.
Determines the largest cochromatic number of an n-vertex graph, where each color class must induce a complete or an empty graph.
Asks for the growth rate of the largest cochromatic number of a graph embeddable on the orientable surface of genus n, the cochromatic number being the fewest colors whose classes each induce a complete or an empty graph.
Bounds the cochromatic number of a graph, the fewest colors needed so that every color class induces either a complete graph or an independent set.
Asks how the least number of colors whose classes induce complete or empty graphs compares with the least number avoiding monochromatic oriented cycles.
Asks whether a graph with no K_5 and cochromatic number at least 4 has chromatic number at most the cochromatic number plus 2; answered no by Steiner's 2024 graphs with clique number 4, cochromatic 4 and chromatic 7.
Asks whether a set of naturals can have its count of representations as a sum of two elements, summed up to N, equal to cN plus O(1) for a constant c > 0.
Asks whether a set of naturals can have its count of representations as a sum of three elements, summed up to N, equal to cN plus O(1) for a constant c > 0.
Asks for an asymptotic formula for the largest number of edges of a graph on n vertices containing no cycle of length four.
Asks for estimates of the least Turán number over all graphs with k vertices and l edges in the range k < l ≤ k²/4, and whether it is strictly monotone in l; open, with asymptotics known at the pairs (5,6) and (6,9) only.
Asks whether the most edges on n vertices with no cycle carrying k chords at one cycle vertex is (k+1)n minus (k+1) squared for large n; proved for n at least 3k+3 by Jiang (2004), with a 2026 preprint claiming the threshold.
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).
Bounds the least k beyond which the n-dimensional unit cube splits into k homothetic cubes, in particular whether it grows at least like n to the power n.
Densities and growth of the smallest endpoint at which the collective gcd of the integer power differences becomes one.
The largest size such that, for every m, some subset of one to n of that size has no sub-collection of its elements summing to m.
The largest Sidon set guaranteed inside any n integers in which no number has more than k representations as a sum of two elements.
The size of the largest Sidon subset of the squares up to N squared, and whether it is N to the power one minus o(1).
Asks whether every infinite set of natural numbers whose finite subsets each contain a dissociated subset (one with distinct subset sums) of proportional size is a finite union of dissociated sets.
Asks whether a three-uniform hypergraph on n vertices can have at least n minus O(1) different sizes of maximal complete subgraphs.