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, for almost all sign choices, a signed power series with small but not square-summable coefficients converges somewhere on the unit circle.
Asks whether every two-coloring of the natural numbers admits an infinite set all of whose finite non-empty subset sums share one color; yes, by Hindman's theorem, held in his 1974 paper and Baumgartner's 1974 note.
Asks whether a graph on n vertices with no complete subgraph on five vertices and a positive edge density has a triangle-free set of linearly many vertices.
The largest subset of the integers up to N that contains N itself and in which every two distinct elements share a common factor greater than one.
Asks whether every subset of the integers up to N of positive density contains three elements which become equal after multiplying each by a distinct prime.
Asks whether any subset of the integers modulo N of size at least a constant times the square root of N has a non-empty subset summing to zero modulo N; proved by Szemerédi in 1970 for all finite abelian groups.
Asks whether p residues modulo p, whose zero-sum non-empty subsets all have the same size, must take at most two distinct values; Graham's conjecture, proved for large primes in 1976 and for every modulus in 2010.
Asks whether a set of integers up to n with pairwise least common multiples above n has reciprocal sum at most 31/30, and whether a positive proportion of the integers up to n avoid its multiples; yes and no, Schinzel-Szekeres.
Asks whether the number of random elements of an abelian group of order N whose subset sums cover it is at most log base two of N plus a small error.
Asks whether the Ramsey number of any graph with m edges and no isolated vertices is at most exponential in the square root of m.
Asks whether every tree on n at least 2 vertices has Ramsey number at most 2n minus 2; proved, since 2026 on a third party's Lean proof built here, while the site's wording fails for the one-vertex tree.
Records the proved Erdős–Sós tree edge bound and the precise relation between its sharp threshold and the site's statement.
Asks whether a tree that is bipartite with k vertices in one class and two k in the other has Ramsey number exactly four k minus one.
Asks for a proof that the Ramsey number of a k-cycle against a complete graph on n vertices is k minus one times n minus one plus one, when k is at least n.
Asks for a proof that the three-color Ramsey number for two triangles and a complete graph on n vertices grows much faster than the two-color version.
Asks whether the k-color Ramsey number of any tree on n vertices is at most k times n plus a bounded amount.
Asks whether every graph on n vertices with bounded maximum degree has size Ramsey number linear in n; false already for maximum degree three.
Bounds the induced Ramsey number, the fewest vertices of a host graph in which every two-coloring of the edges gives an induced monochromatic copy of a graph.
Asks whether, for each k at least three and sufficiently large m, the Ramsey number of a k-cycle against any m-edge graph without isolated vertices is at most two m plus the floor of half of (k minus one).
Every rational exponent in [1,2) is realized by the Turán number of a finite bipartite graph; records the 2026 proof, accepted on Lean built here, and its exposition qualifications.
Asks whether the most edges on n vertices avoiding cycles of length two k minus one and two k is asymptotic to n over two to the power one plus one over k, for k above one; disproved at k equal to 3 and 5.
Asks whether the extremal number of a finite family with a bipartite member is within a constant factor of some bipartite member's; false as written for two forests, and false for cyclic bipartite families by OpenAI's 2026 report.
Asks whether every graph on four k vertices with minimum degree at least two k contains k vertex-disjoint four-cycles; the Erdős-Faudree conjecture, proved by Wang in 2010 as Theorem B of a refereed paper.
Asks whether a random graph on two to the d vertices with each edge included with probability one half almost surely contains a d-dimensional hypercube; proved by Riordan for every fixed edge probability above one quarter.
Asks whether a large dense graph on n vertices with no complete tripartite subgraph having two vertices per class must have a linear independent set; false at edge density 3/2048 by a Lean construction Conjectures.io certified.