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.
Concerns the union of a family of at most a constant times two to the n many sets each of size n, for large n.
Estimates the least possible maximum, over subsets of the first n integers, of the sum of a plus or minus one valued function over the pairs inside that subset.
Asks whether a graph on n vertices with no empty or complete subgraph of size ten times the logarithm of n has an induced non-trivial (neither empty nor complete) regular subgraph of logarithmic size.
Asks whether a graph on n vertices with more than n²/4 edges has a triangle to which nearly half of all vertices are joined twice; the Erdős–Faudree conjecture, disproved by Ma and Tang's construction with constant 2 − √(5/2).
Asks whether a graph on n vertices with no empty or complete subgraph of logarithmic size has exponentially many pairwise non-isomorphic induced subgraphs.
Asks whether a graph on n vertices with each degree repeated at most twice and more than half of n distinct degrees has a large empty or complete subgraph.
Asks what can be said about a closed set in the plane of transfinite diameter one that lies inside no closed disc of radius one.
Asks whether every monic non-constant complex polynomial has a line onto which the set where its absolute value is at most one projects to measure at most two.
Determines the infimum of the largest component boundary length of the region where a polynomial with all roots in the closed unit disc is below one.
Asks whether the set where a monic complex polynomial has absolute value below one must lie in a disc of radius two whenever that set is connected.
Examines a monic polynomial with m distinct roots and a threshold so small that the set where its absolute value is at most that threshold has m components.
Asks whether a monic polynomial with all roots of absolute value at most r below two has a component of diameter over two minus r where it is below one.
Asks whether the sum over all n of one over two to the power n minus three is irrational.
Asks whether the sum of one over consecutive products of an increasing integer sequence is irrational whenever the sequence grows doubly exponentially.
Asks whether only finitely many n lying between two consecutive primes have n factorial plus one divisible only by the next two primes.
The largest subset of one to n in which no element divides two other distinct elements, and whether its density tends to an irrational limit; an exact formula and an irrational limit near 0.67297, by a Lean proof Conjectures.io certified.
Asks whether the totient of n exceeds the totient of n minus its totient for almost all n and the reverse holds infinitely often; the first part proved by Luca and Pomerance (2002), the second by Grytczuk, Luca and Wójtowicz (2001).
Asks whether every graph of chromatic number aleph one contains an infinitely connected subgraph of chromatic number aleph one.
Bounds the lines containing at least k of n plane points by n squared over k cubed for k up to root n; fails as worded at k = 1, and Szemerédi and Trotter proved it for k from 2 to root n.
Asks whether a finite family of pairwise disjoint unit segments in the unit square can be maximal, so that no further unit segment can be added.
Asks whether, for k at least five, the most edges of a 3-uniform hypergraph on n vertices with no j vertices spanning j minus two edges for any j from four to k is asymptotic to n squared over six; false for the single family as printed.
Asks whether every graph with n^{1+α} edges has an almost-regular subgraph on more than n^{1−α} vertices with εm^{1+α} edges; false as written, with n^α the right size on the site's account of a 2025 preprint.
Asks whether an r-partite graph with n vertices per part and minimum degree about (r − 3/2)n must contain a complete graph on r vertices; proved by Haxell, with the exact threshold from Haxell and Szabó by complementation.
Asks whether a graph with the Turán number of edges has a linear-degree vertex whose neighborhood has the Turán number of edges for r − 1; proved by Bollobás and Thomason in 1981, strengthened by Bondy in 1983.
Asks whether a bipartite graph on n vertices with a part of size about n^(2/3) and at least cn edges must contain a six-cycle; disproved by the superlinear 6-cycle-free constructions credited by the site, papers not held.