Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
516 of 1,221 problems match
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Densities and growth of the smallest endpoint at which the collective gcd of the integer power differences becomes one.
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 the first player can win the game of alternately coloring edges of a complete graph so that her largest monochromatic clique beats her opponent's.
Asks whether, for the product P of the first n primes, there is always a prime p between the n-th prime and P such that P plus p is prime.
Asks whether the squares contain arbitrarily long progressions with bounded gap error, and arbitrarily large sets of all zero-one sums of given numbers.
The largest subset guaranteed inside any n real numbers with no two distinct elements summing to a member of the set; the Erdős–Moser function, between a power of log n above the first and exp(O(sqrt(log n))).
Estimates the fewest elements of zero to n whose pairwise sums cover zero to n (the smallest finite additive 2-basis); its square lies between 2.181 n and 3.458 n, and the guess 2 sqrt(n) is refuted (Hämmerer-Hofmeister, Mrose).
Estimates the largest sum-free subset, having no solution to a plus b equals c, guaranteed inside any set of n integers; the main term n/3 is settled and the second-order term lies between c log log n and o(n).
Characterizes the functions g for which some graph on n vertices has every induced subgraph on g of n vertices with a clique and independent set of size log n.
Asks whether some graph on n vertices with a positive fraction of all possible edges can be edge-colored with n colors so that every four-cycle gets four distinct colors.
Asks which graphs are forced as rainbow copies in every balanced coloring of a large complete graph with as many colors as the graph has edges, where each vertex sees equally many edges of every color.
Asks whether consecutive diagonal Ramsey numbers grow by at least a constant factor, and whether their difference is at least a constant times n squared.
Estimates the largest clique forced in an n-vertex graph where every seven vertices span a triangle: the exponent lies between 5/12 (Bucić and Sudakov) and 1/2 (Erdős and Hajnal), and whether either end can be moved is open.
Estimates the least N for which some n-element set of integers up to N has all subset sums free of k-term progressions, and asks whether the k = 3 case grows like 3^n; open, with a 2026 preprint claiming a negative answer.
Estimates the largest possible size of the sumset within the integers up to N of a subset of them having about root N elements; open, with Erdős and Freud's 1991 bounds 3/8 and 1/2 and an unreviewed 2026 note claiming 0.469.
Infinitely-often coprimality of two and three power differences, and the growth of the least bases admitting a coprime pair.
Estimates the number of coprime pairs of integers below x that have the same sum of divisors; a lower bound with exponent 13/8 is claimed in an AI-assisted write-up of August 2026.
Asks whether there are infinitely many n for which the number of divisors of n plus k is at most a constant times k for every k at least one.
Estimates how many points in general position in the plane force k of them whose triples all determine circles of distinct radii.
Asks whether, for every integer a, there are infinitely many n whose Euler totient divides n plus a.
Asks whether the number of ways to write n as a sum of two cubes is at most a power of the logarithm of n.
Asks whether there are infinitely many amicable pairs, and whether the count of them up to x is at least x to the power one minus a small amount.
Estimates the least number of distinct radii among circles through three of n points in the plane, with no three collinear and no four concyclic.
Asks whether some k above two lets the k-element subsets of the integers up to two k get k plus one colors so every k plus one of them sees all colors.