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.
Asks whether the smallest size forcing balanced two-colorings of a complete uniform hypergraph varies continuously with the density parameter or jumps.
Asks whether the size threshold beyond which some two-coloring of K_n balances every large induced subgraph grows like c log n; corrected to "smallest", it is the question of Problem 563, which is open.
Asks for an asymptotic formula for the Ramsey number of a triangle versus a complete graph on k vertices; the order k^2/log k is known and the constant lies between 1/2 and 1.
Asks whether a graph with at most k edge-disjoint triangles can be made triangle-free by deleting at most 2k edges (Tuza's conjecture); open, the site's label falsifiable, with Haxell's 66/23 the best refereed constant.
The limiting density of the largest subset of the first N integers containing no triple of the form n, twice n, three times n, and whether it is irrational.
Estimates the largest possible sum of reciprocals of a set of integers with no arithmetic progression of k terms, and compares it to van der Waerden numbers.
The limiting value, divided by the square root of N, of the smallest subset of zero through N whose difference set covers every integer up to N.
Asks whether every two-coloring of the plane contains a monochromatic congruent copy of every triangle, with at most one exception.
Bounds the least N forcing every plus-minus-one sign pattern to have a k-term arithmetic progression with partial sum of absolute value at least a given size.
The smallest bound, as a function of the common difference, on the largest partial sum along arithmetic progressions of a single plus-minus-one sign function.
The best length, in the common difference d, of a monochromatic progression of difference d forced for infinitely many d in every two-coloring of the integers; at most (1 + o(1)) log_2 d by Beck 1980, with no usable lower bound known.
The least number of terms k such that the plane can be two-colored avoiding red points at unit distance and blue unit-spaced progressions of k terms; Erdős and Graham's question, with the step left free, has no finite answer.
The largest number of terms k such that every permutation of the integers contains a monotone arithmetic progression of k terms.
Asks whether the positive integers split into two sets, each of which can be permuted to avoid monotone three-term arithmetic progressions.
Asks whether the longest arithmetic progression of primes below N has length a vanishing fraction of the logarithm of N.
Determines how large a subset free of k-term arithmetic progressions can be guaranteed inside any N integers, and how that compares with the case of one to N.
Asks whether some integer coprime to 6 makes every number of the form two to the k times three to the l times it, plus one, composite.
Bounds the gaps between consecutive squarefree numbers, asking whether they are smaller than any fixed power, and whether a sharp logarithmic bound holds.
Asks whether the plane contains a dense set of points all of whose pairwise distances are rational.
Asks whether, for every n at least 4, there are n points in the plane with no three collinear and no four concyclic and all distances integers.
Asks for which n there are n points, no three collinear and no four concyclic, whose distances take each multiplicity up to n minus one.
Asks whether consecutive prime gaps increase half the time and decrease half the time, and whether two consecutive gaps are equal infinitely often.
Bounds the gaps between consecutive integers that are sums of two squares, from above and below.
Asks whether the sum of the squares of the first N prime gaps is at most a constant times N times the square of the logarithm of N.
Asks whether the density of primes whose gap to the next prime is below c times the logarithm exists for every c and varies continuously in c.