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 n points in the plane forming a convex polygon have only order n pairs at distance one; false by Kruer and Kohlmeyer's Lean construction of convex point sets with unboundedly many unit distances per point.
Asks whether disjoint plane sets of n and n minus 3 points, the first not all collinear, admit a line meeting two points of the first and none of the second.
Asks whether the largest total side length of interior-disjoint squares packed in the unit square equals k when there are k squared plus one squares.
Asks whether, for every girth bound at least 4 and every k, large enough chromatic number forces a subgraph of that girth with chromatic number at least k; disproved at girth 5 and k = 7 by a Lean counterexample family.
Shows that any set of natural numbers with positive upper density contains the sumset of two infinite sets.
Asks whether one function F(n) bounds, for all large n, the order of a smallest subgraph of chromatic number n in every graph of chromatic number aleph-one.
Asks whether a bipartite graph has Turan number O(n^(3/2)) exactly when it has no induced subgraph of minimum degree at least three.
Asks whether a monic degree n polynomial whose set of modulus at most one is connected has derivative at most (1/2+o(1))n^2 there; Eremenko and Lempert proved it, and Erdős's exact bound n^2/2 fails for every n.
Asks whether a monic polynomial with roots in the unit disc has modulus below one on a set of area at least an inverse power of n; proved by Pommerenke (1961), with a constant over log n by Krishnapur, Lundberg and Ramachandran.
Asks whether an order type whose two-colorings always give a red copy of itself or a blue triangle must likewise force a blue complete graph on n vertices.
Asks whether the maximum modulus on the unit circle of the partial products of z minus a unimodular point is unbounded, exceeds a power of n, and has partial sums above n^(1+c); yes by Wagner, Beck, and Korsky with GPT 5.6-Pro.
Asks whether the largest subset of the first N integers with no five (or no fixed odd number, at least five, of) distinct elements multiplying to a square has size nearly N; Tao (2024) disproved it for every size at least 4.
Asks whether, for pairwise coprime a, b, c above one, every large integer is a sum of distinct products of powers of a, b and c, none dividing another. Erdős also suggested the weaker hypothesis that a, b and c have no common factor, under which the answer is no, as 6, 10 and 15 show.
Asks whether the sumset of integers using only digits zero and one in base three and those using only those digits in base four has positive lower density.
Asks whether the least number of distinct prime factors of the product of the sums of two distinct elements of a set of n natural numbers grows faster than the logarithm of n.
Asks whether the excess over a known bound in the number of edges of a largest bipartite subgraph of a graph with m edges is unbounded along some sequence of m.
Determines the growth of the largest degree forced in every triangle-free graph on n vertices of diameter two, in particular whether it beats root n.
Asks whether a triangle-free graph on n vertices with maximum degree below n to the power one half minus epsilon can reach diameter two by adding few edges.
Asks whether a set of n points in the plane in which every four points give at least five distinct distances must determine order n squared distinct distances.
Determines the least number of edge colors of the complete graph on n vertices such that every four vertices span at least five colors.
Asks whether the largest subset of the first N integers with no non-trivial k-term arithmetic progression has size a vanishing proportion of N.
Asks whether the largest subset of the first N integers with no three-term arithmetic progression is smaller than N over any fixed power of the logarithm of N.
Asks whether almost every integer has two divisors with the larger less than twice the smaller, so that the density of such integers exists and equals one.
Asks whether a bipartite r-degenerate graph has extremal number at most n to the power two minus one over r; disproved at r equal to two by Theorem 1.2 of Chapter 10 of OpenAI's 2026 report, credited by the site's curator.
Asks whether every bipartite graph of minimum degree r has extremal number at least order n to the power two minus one over r minus one, plus a positive gain.