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, for any increasing integer sequence, the discrepancy of its multiples of alpha stays near the square root of N for almost every alpha.
Asks whether, for almost every alpha, the fractional parts of its integer multiples visit every measurable set in the unit interval with frequency its measure.
Asks whether the fractional parts of alpha times the primes fail to be well distributed for every alpha.
Asks whether an interval with bounded discrepancy along the fractional multiples of an irrational alpha must have length a fractional multiple of alpha; the site's wording, asking that of both endpoints, is false.
Asks whether almost-all approximability of alpha by fractions within f of q over q equals divergence of the sum of the totient of q times f of q over q.
Concerns how many fractions with denominator the kth term of an integer sequence reduce to a denominator not equal to an earlier term of the sequence.
Asks whether the measure of reals well approximated by fractions with denominator between N and cN tends to a limit, and what that limit is explicitly.
Asks whether the logarithmically normalized sum of one half minus fractional parts of multiples of a fixed irrational has an asymptotic distribution function.
Estimates f(n), the largest d such that Farey fractions of order n at most d places apart are similarly ordered; asks if f(n) = (c + o(1))n. Marked solved on Cipollini's 2026 preprint (c = 1/4, matching van Doorn's upper bound).
Asks whether every graph of girth at least five has an acyclic orientation that stays acyclic after any one edge is reversed; false, by Nešetřil and Rödl's large-girth graphs with a monotone cycle under every vertex ordering.
The smallest number of edges of a graph of dimension four, the least Euclidean dimension in which it embeds with every edge a unit segment; nine, attained only by K_{3,3} up to isolated vertices, by House and Chaffee-Noble.
Asks whether every graph with m edges has a four-cycle-free subgraph with at least a constant times m^{2/3} edges; true (Conlon, Fox and Sudakov), while Bollobás and Erdős's first form with m^{3/4} fails by Folkman's example.
Asks whether, for each positive c, a graph on n vertices with the Turán number plus k edges, k below cn, has at least k minus f(c) edge-disjoint triangles; proved by Győri (1988), a paper known only by attestation.
Asks whether every graph on n vertices with the Turán number plus t edges, t below half of n, has at least t times the floor of half of n triangles; the Erdős-Rademacher conjecture, proved in full by Lovász and Simonovits.
Determines or estimates how large n must be, in terms of k, for a given edge count to force a cycle through all but k of the n vertices; Woodall's 1972 Corollary 11.1 gives every n at least 2k + 3 and covers the smaller n too.
Asks whether, for each fixed k, the ratio of consecutive off-diagonal Ramsey numbers R(k,l+1)/R(k,l) tends to one; answered yes by a 2026 manuscript hosted by OpenAI, attributed to an internal model and accepted by the site.
The most vertices a two-colored complete graph can force to be left over when it is covered by disjoint monochromatic copies of K_t; Burr, Erdős and Spencer determine it for fixed t and large n in terms of R(t,t−1), so it grows exponentially.
Asks whether every large graph with at least n to the power one plus epsilon edges has a non-planar subgraph of bounded size; answered yes by Kostochka and Pyber in 1988 through a bounded subdivided K_5.
Asks whether every graph on n vertices with the Turán number plus half of n edges contains a saturated planar subgraph on more than three vertices; proved by Simonovits in his thesis, attested by Erdős and the site.
Asks whether, for every k at least three, the extremal number of the bipartite graph joining each pair among k vertices to its own vertex beats n to the 1.5.
Asks whether sets of size at least t, few of which lie inside any given set relative to its size, can always be two-colored with no monochromatic member.
Asks whether the largest family of subsets of the first n integers with no member a union of others is a constant times two to the n over the square root of n.
Estimates the largest independent set guaranteed in a three-uniform hypergraph on n vertices in which any two edges share at most one vertex.
Independent sets for a function assigning to each pair from the first n integers a third value, meaning sets closed away from the values of their own pairs.
Determines the largest possible sum of a monotonic subsequence of a sequence of n distinct real numbers.