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 points in the plane forming a convex polygon have only pairs at distance . The answer is no, by Kruer and Kohlmeyer's Lean construction of convex point sets with unboundedly many unit distances per point.
Asks whether disjoint plane sets and of and points, with not all collinear, always admit a line through at least two points of and none of .
Asks whether , where is the largest total side length of interior-disjoint squares in the unit square.
Asks whether, for every and , large enough chromatic number forces a subgraph of girth and chromatic number ; disproved at and by a Lean counterexample family.
Asks whether every of positive upper density contains a sumset with and both infinite.
Asks whether one function bounds, for all large , the order of a smallest subgraph of chromatic number in every graph of chromatic number .
Asks how many edge deletions make every -vertex subgraph of a graph bipartite, and whether this number grows faster than when has chromatic number .
Asks whether a bipartite graph has Turán number exactly when it is -degenerate, that is, has no induced subgraph of minimum degree at least .
Asks whether a monic polynomial of degree with connected has on that set. Eremenko and Lempert proved it, and Erdős's exact bound fails for every .
Asks whether a monic polynomial of degree with all roots in the unit disc has on a set of area at least ; proved by Pommerenke (1961), and with area by Krishnapur, Lundberg and Ramachandran.
Asks whether, for an order type such that every two-coloring of has a red or a blue , every such coloring also has a red or a blue for each .
Asks, for unimodular and , whether , whether for infinitely many , and whether for all large , for some . The answers are yes, by Wagner, Beck, and Korsky with GPT 5.6-Pro.
Asks whether the largest subset of in which no distinct elements, or more generally no fixed odd number at least of them, multiply to a square has size . Tao (2024) disproved it for products of any fixed number of elements.
Asks whether, for pairwise coprime , every large integer is a sum of distinct numbers , none dividing another. Erdős also suggested the weaker hypothesis that have no common factor, under which the answer is no, as , and show.
Asks whether has positive lower density, where and are the integers whose only digits are and in base and in base .
Asks whether , where is the least number of distinct prime factors of over sets of size .
Asks whether, for graphs with edges, the guaranteed excess of a largest bipartite subgraph over edges is unbounded along some sequence of .
Asks for an estimate of the largest subset of in which no element divides the sum of any distinct others. The question whether it exceeds is answered no, and one unreviewed claim asserts the order .
Asks for the order of growth of the largest such that every triangle-free graph on vertices with diameter has a vertex of degree at least , and whether .
Asks whether a triangle-free graph on vertices with maximum degree below can be made into a triangle-free graph of diameter by adding at most edges.
Asks whether points in the plane, any four of which determine at least five distinct distances, must determine distinct distances.
Asks for the least number of colors for the edges of such that every contains at least colors.
Asks for better bounds on the van der Waerden number , the least such that every two-coloring of has a monochromatic -term arithmetic progression, for example a proof that .
Asks whether , where is the size of the largest subset of with no non-trivial -term arithmetic progression.
Asks whether for every , where is the size of the largest subset of with no non-trivial -term arithmetic progression.