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 a -uniform hypergraph on vertices can have at least different sizes of maximal complete subgraphs.
Asks how many comparable pairs a family of subsets of can have for near . The three questions are answered yes, no and yes: the first by Alon, Das, Glebov and Sudakov, the other two by Alon and Frankl.
Asks whether every -coloring of the edges of the complete -uniform hypergraph on vertices has a color class with pairwise disjoint edges. Alon, Frankl and Lovász proved it in 1986, and Lovász had proved the case in 1978.
Asks for an estimate of the least such that every two-coloring of has a monochromatic -term descending wave, and whether it equals for all .
Asks which set of pairwise coprime integers in with reciprocal sum at most a fixed leaves the fewest integers up to divisible by none of its elements. Following erdosproblems.com, it is read up to an error of , and then the largest primes up to are optimal.
Asks whether a set of integers in with reciprocal sum at most must leave integers up to divisible by none of them, for some .
Asks whether infinite sets of naturals with containing all large integers and must have .
Estimates , the fewest elements of whose pairwise sums cover (the smallest finite additive -basis). Its square lies between and , and the guess is refuted (Hämmerer and Hofmeister, Mrose).
Asks whether the largest in which no element divides the product of two others has size . Chojecki's 2026 manuscript, accepted by erdosproblems.com, proves this with .
Asks whether every -uniform hypergraph on vertices with more than edges has four vertices spanning three edges. False as written, by a -edge example; the Turán density of minus an edge stays open.
Asks whether the largest with all subset products distinct has size at most ; proved by Raghavan with a power-saving error term.
Asks for an estimate of the largest acyclic chromatic number of a graph with maximum degree (proper colorings with no two-colored cycle), in particular whether . Alon, McDiarmid and Reed (1991) showed that has order up to a factor.
Asks to estimate , the fewest points in the grid whose pairwise connecting lines cover every point of the grid, and in particular whether .
Asks whether almost every graph on vertices has list chromatic number . Alon proved this in 1992 with the bound , and Alon, Krivelevich and Sudakov sharpened it in 1999 to order .
Asks whether every graph on vertices with no two adjacent vertices both of degree at least 3 has at most an absolute constant times .
Asks whether every graph on vertices with no independent set of more than vertices has a set of at most vertices spanning edges.
Asks whether every -free graph on vertices with average degree has an independent set of size . True for since 1980, and for every by a Lean-checked theorem of the 2026 OpenAI release.
Asks whether every graph on vertices with edges has an almost-regular subgraph on vertices with edges. False by Alon's 2008 random bipartite construction; Janzer and Sudakov's bound is the best positive one.
Estimates the largest independent set forced in an -vertex graph in which every induced subgraph on vertices has an independent set of size .
Asks whether every set of at most integers in lies in for some of size . Alon, Bukh and Sudakov proved it with a basis of order , which is the sharp order.
Asks whether the random graph almost surely needs exactly complete bipartite graphs to partition its edges. Disproved by Alon, then by Alon, Bohman and Huang.
Asks whether, for any graph with many edges on a set of integers, the sums or the products along its edges must number nearly as many as the edges.
Asks whether, for every , the fewest colors that make every rainbow in some -vertex graph with edges is asymptotically . Proved by two independent Lean developments built and audited here: the project's claim L17, published first, and Asad Shahab's, filed first on erdosproblems.com.
Asks whether a graph with one edge more than the count forcing a subgraph of minimum degree has such an induced subgraph on at most vertices. Proved by Sauermann for ; the case is elementary.
Asks whether, for large , a graph with vertices, edges and no proper induced subgraph of minimum degree contains for each fixed . False at (Narins, Pokrovskiy and Szabó), true for , open for even .