Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
1,221 problems
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Asks whether every two-coloring of the edges of the complete graph on n vertices yields about n squared over twelve edge-disjoint monochromatic triangles; yes, by a 2020 theorem of Gruslys and Letzter the site accepted.
Asks for the limit of the k-th root of the Ramsey number of the complete graph on k vertices as k grows, a limit not known to exist.
Asks for a constructive proof that the Ramsey number of the complete graph on k vertices grows at least exponentially in k, equivalently for an explicit graph with logarithmic clique and independence numbers.
Asks whether there are infinitely many graphs that are not Ramsey size linear even though all of their proper subgraphs are; proved by Wigderson in 2024 non-constructively, with no explicit example beyond K_4 known.
Estimates the largest book, an edge lying in many triangles, forced in a graph on n vertices with quadratically many edges each in a triangle; open, the polynomial question answered no and the logarithmic one open.
Asks whether the edges of any chordal graph on n vertices can be partitioned into about n squared over 6 cliques.
Asks whether the largest regular induced subgraph guaranteed in every graph on n vertices has size growing faster than the logarithm of n.
Bounds how large a family of half-size subsets of a set of 4n elements can be when every two members share at least two elements.
Asks whether the number f(n) of cycle sets of graphs on n vertices is o(2^n), and whether f(n)/2^(n/2) tends to infinity.
Asks whether the least minimum degree forcing a four-cycle on n vertices is nondecreasing for all large n; open, with the equivalent star Ramsey numbers R(C_4, K_{1,n}) known exactly only for small n and near prime-power squares.
Asks whether every subgraph of the n-dimensional hypercube with slightly more than half of its edges must contain a four-cycle.
Asks whether every graph with chromatic number k has Ramsey number at least a constant fraction, or at least an exponentially small fraction, of the Ramsey number of the complete graph on k vertices; Erdős's original conjecture, at least that Ramsey number itself, fails at k = 4.
Asks whether a graph on n vertices with no clique or independent set of logarithmic size has induced subgraphs of every edge count up to order n squared.
Asks whether n distinct points in the plane always determine at least about n divided by the square root of the logarithm of n distinct distances.
Asks whether n distinct points in the plane can have only about n pairs at distance one, up to a factor n to the power one over the log log of n.
Asks whether, for large n, the n-point plane sets minimizing the number of distinct distances include at least two that are not similar to each other.
Asks how many points can be equidistant from every point of an n-point plane set, and whether this maximum stays below any fixed power of n.
Shows that n points in the plane forming a convex polygon determine at least the floor of n over 2 distinct distances.
Bounds the sum over distances of the squared number of point pairs realizing each distance, for n points forming a convex polygon, by about n cubed.
Bounds the sum over distances of the squared number of pairs realizing each distance, for n plane points, by n cubed times any small power of n.
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 every convex polygon has a vertex with no four other vertices at the same distance from it; Erdős first asked it with three, which Danzer's convex nonagon refutes.
Asks whether the fewest distinct distances among n plane points with no three on a line and no four on a circle grows faster than n.
Asks whether, for all sufficiently large n, an n-point plane set of minimum distance one and smallest possible diameter must contain three points forming a unit equilateral triangle.
Asks whether n plane points whose pairwise distances are at least one and whose distinct distances differ by at least one must have diameter of order n.