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 the number of sum-free subsets of 1 up to n is two to the power of half of n times one plus a vanishing term.
Asks, for any function tending to infinity, whether some graph of infinite chromatic number has every m-vertex subgraph containing a large independent set.
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 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 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 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.
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.
Asks whether a three-uniform hypergraph on n vertices can have at least n minus O(1) different sizes of maximal complete subgraphs.
Asks how many comparable pairs a family of m subsets of one to n can have for m near 2^(n/2); three questions answered yes, no, yes by Alon and Frankl and by Alon, Das, Glebov and Sudakov.
Asks whether t-coloring the edges of the complete r-uniform hypergraph on enough vertices forces some color class to contain k pairwise disjoint edges; proved by Alon, Frankl and Lovász in 1986 (Lovász 1978 for k = 2).
Estimates the least n such that every two-coloring of one to n has a monochromatic k-term descending wave, and whether it is k squared minus k plus one.
Asks which set of pairwise coprime integers between two and N, with reciprocal sum at most a fixed constant, leaves the fewest integers up to N divisible by none of its elements; read, with the site, up to o(N), where the largest primes up to N are optimal.
Asks whether a bounded reciprocal sum for a set of divisors forces at least x over a power of log x integers up to x divisible by none of them.
Asks whether two infinite sets whose sumset covers all large integers and whose counting functions multiply to about x must have that product exceed x by an amount tending to infinity.