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 there are infinitely many pairs of integers for which Euler's totient of one equals the sum of the divisors of the other.
Asks whether a set of integers up to N on which Euler's totient function is strictly increasing has at most (1+o(1))π(N) elements, or even o(N); Erdős's exact conjecture, that the primes are a largest such set, is open.
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 with infinite chromatic number contains a cycle whose length is a power of two, for infinitely many powers of two.
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 n of the number of distinct prime factors of n divided by two to the power n is irrational.
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 every two-coloring of the edges of the complete graph on n vertices yields about n squared over twelve edge-disjoint monochromatic triangles; yes, by a 2020 theorem of Gruslys and Letzter the site accepted.
Asks whether there are infinitely many graphs that are not Ramsey size linear even though all of their proper subgraphs are; proved by Wigderson in 2024 non-constructively, with no explicit example beyond K_4 known.
Bounds how large a family of half-size subsets of a set of 4n elements can be when every two members share at least two elements.
Asks whether a graph on n vertices with no clique or independent set of logarithmic size has induced subgraphs of every edge count up to order n squared.
Asks whether n distinct points in the plane can have only about n pairs at distance one, up to a factor n to the power one over the log log of n.
Asks how many points can be equidistant from every point of an n-point plane set, and whether this maximum stays below any fixed power of n.
Shows that n points in the plane forming a convex polygon determine at least the floor of n over 2 distinct distances.
Bounds the sum over distances of the squared number of point pairs realizing each distance, for n points forming a convex polygon, by about n cubed.
Bounds the sum over distances of the squared number of pairs realizing each distance, for n plane points, by n cubed times any small power of n.