Problems
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
618 of 1,221 problems match
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Asks whether for infinitely many pairs of integers , where is Euler's totient and is the sum of divisors.
Asks whether a set on which Euler's totient function is strictly increasing has , or even . Erdős's exact conjecture, that the primes are a largest such set, is open.
Asks whether, for every , every large enough finite set of integers has at least integers that are sums or products of distinct elements of .
Asks to improve the Burr–Erdős bounds on how sparse a Ramsey -complete sequence can be. Conlon, Fox and Pham determined the order as , closing the gap to a constant factor.
Asks for non-trivial bounds on how sparse a set of integers can be if, for a given , all large integers are monochromatic sums of elements of under every -coloring of .
Asks whether the multiples of the first primes form the largest subset of with no pairwise relatively prime elements.
Asks whether the reciprocals of the odd cycle lengths of a graph with infinite chromatic number must sum to infinity.
Asks whether a graph whose odd cycles have at most distinct lengths has chromatic number at most , with equality only if it contains .
Asks whether the number of graphs on vertices containing no copy of a fixed graph is at most .
Asks whether every graph with infinite chromatic number contains a cycle of length for infinitely many .
Asks whether every has unbounded discrepancy, that is, whether for every some give .
Asks whether is irrational, where is the number of distinct prime factors of .
Asks whether, for every infinite arithmetic progression containing even numbers, there is a constant such that every graph of average degree at least has a cycle whose length lies in .
Asks whether there are a set of density and a constant such that every large graph of average degree at least has a cycle whose length lies in .
Asks whether a graph in which every subgraph on vertices has an independent set of size at least becomes bipartite after deleting vertices.
Asks whether, for every , some graph of infinite chromatic number has every -vertex subgraph made bipartite by deleting at most edges.
Asks whether every -coloring of the edges of has at least edge-disjoint monochromatic triangles; yes, by a 2020 theorem of Gruslys and Letzter that erdosproblems.com accepted.
Asks whether infinitely many graphs fail to be Ramsey size linear while all their proper subgraphs are Ramsey size linear. Wigderson proved this in 2024 by a non-constructive argument, and no explicit example beyond is known.
Bounds the size of a family of -element subsets of a -element set in which every two members share at least two elements.
Asks whether, for some , every -vertex graph with no clique or independent set of size has an induced subgraph with edges for every .
Asks whether every set of distinct points in the plane has at most pairs at distance .
Asks for the largest such that some -point set in the plane has, for each of its points , at least points of the set equidistant from , and whether .
States that points in the plane forming a convex polygon determine at least distinct distances.
States that if points in the plane form a convex polygon and pairs of them are at distance , then .
States that if pairs among points in the plane are at distance , then for every .