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 some infinite set of totient values has the smallest integer attaining each value growing faster than any fixed multiple of the value.
Asks whether the larger of the sumset and product set of a finite set of integers always has size at least the set's size squared, up to a small power loss.
Asks whether, for every k, a large enough finite set of integers gives at least its size to the power k integers that are sums or products of distinct elements.
Asks to improve the Burr–Erdős bounds on how sparse a Ramsey 2-complete sequence can be; Conlon, Fox and Pham determined the order as the square of the logarithm, closing the gap to a constant factor.
Bounds the growth of the sparsest sets of integers for which every large integer is a monochromatic sum under any coloring with more than two colors.
Asks whether the multiples of the first k primes form the largest subset of the first N integers with no k plus one pairwise relatively prime elements.
Asks whether the reciprocals of the odd cycle lengths of a graph with infinite chromatic number must always sum to infinity.
Asks whether a graph with odd cycles of at most k distinct lengths has chromatic number at most two k plus two, with equality only if it has a big clique.
Asks whether the number of graphs on n vertices containing no copy of a fixed graph is at most two raised to nearly the extremal number of edges.
Asks whether every graph on n vertices with more edges than the extremal number for four-cycles contains at least about the square root of n four-cycles.
Asks whether every graph on n vertices with no induced copy of a fixed graph has a clique or an independent set of size at least a fixed power of n.
Asks whether two graphs of chromatic number aleph-one must share a common subgraph of chromatic number four, or even of countably infinite chromatic number.
Asks whether every graph with infinite chromatic number contains a cycle whose length is a power of two, for infinitely many powers of two.
Asks whether every finite graph with minimum degree at least three contains a cycle whose length is a power of two with exponent at least two.
Asks whether the reciprocals of the distinct cycle lengths of a graph with n vertices and kn edges sum to at least a constant times log k, and whether a complete bipartite graph minimizes that sum.
Asks whether some set of naturals has its number of representations as a sum of two elements, divided by the logarithm of n, tending to a nonzero limit.
Asks whether every function on the naturals taking values plus and minus one has unbounded discrepancy: for every bound, some step and length give a partial sum along the multiples of the step that exceeds it.
Asks whether the sum over integers n at least two of one over n factorial minus one is irrational.
Asks whether the sum over n of the number of distinct prime factors of n divided by two to the power n is irrational.
Asks whether the order type of the real line arrows a countable ordinal and a finite number for two-colorings of triples.
Asks whether each infinite arithmetic progression with even numbers has a degree bound forcing every graph of that average degree to have such a cycle length.
Asks whether some set of integers of density zero meets the cycle lengths of every large graph whose average degree is at least a fixed constant.
Asks whether a graph whose every n-vertex subgraph has an independent set of at least (n-k)/2 vertices becomes bipartite after deleting a number of vertices bounded in terms of k.
Asks whether, for every function growing to infinity, some graph of infinite chromatic number has each n-vertex subgraph made bipartite by that many deletions.
Asks whether some graph of chromatic number aleph-one on aleph-one vertices has every large n-vertex subgraph containing an independent set of size above n^(1-epsilon) for each epsilon > 0, and asks the same for linear size.