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 every graph on n vertices with more edges than the extremal number for four-cycles contains at least about the square root of n four-cycles.
Asks whether every graph on n vertices with no induced copy of a fixed graph has a clique or an independent set of size at least a fixed power of n.
Asks whether two graphs of chromatic number aleph-one must share a common subgraph of chromatic number four, or even of countably infinite chromatic number.
Asks whether every finite graph with minimum degree at least three contains a cycle whose length is a power of two with exponent at least two.
Asks whether the reciprocals of the distinct cycle lengths of a graph with n vertices and kn edges sum to at least a constant times log k, and whether a complete bipartite graph minimizes that sum.
Asks whether some set of naturals has its number of representations as a sum of two elements, divided by the logarithm of n, tending to a nonzero limit.
Asks whether the sum over integers n at least two of one over n factorial minus one is irrational.
Asks whether the order type of the real line arrows a countable ordinal and a finite number for two-colorings of triples.
Asks whether some graph of chromatic number aleph-one on aleph-one vertices has every large n-vertex subgraph containing an independent set of size above n^(1-epsilon) for each epsilon > 0, and asks the same for linear size.
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.
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 largest regular induced subgraph guaranteed in every graph on n vertices has size growing faster than the logarithm of n.
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 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, 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 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.
Asks whether n plane points with no five on a line determine only a negligible fraction of n squared lines containing exactly four points.
Estimates the largest number of collinear points forced when n plane points admit a constant times n squared lines with more than three points each.
Asks whether the number of incongruent n-point plane sets of minimum distance one and least possible diameter grows without bound.