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.
Estimates , the size of the largest subset of whose sets of sums of distinct members are disjoint for distinct , and asks whether .
Estimates the number of maximal sum-free subsets of and asks whether . The answer is yes, and with a constant that depends on modulo .
Asks whether the integers that are sums of or fewer distinct elements of an additive basis of order have bounded gaps.
Asks for the size of the largest whose nonempty subset sums form a set in which no element divides another.
Asks whether the sum of over all pairs of divisors of is at most an absolute constant times , the sum over consecutive divisors.
Asks for the size of the largest in which any in with a square satisfy .
Asks whether, for a lacunary sequence , the integers can be finitely colored so that no two numbers of the same color differ by an element of . Proved, and Peres and Schlag's bound of order colors is the best known.
Asks whether, for all large , every triangle-free graph on has three pairwise nonadjacent vertices of the form , and .
Asks for an estimate of the largest number of integers with exactly one representation , , , over ; the order of magnitude is .
Asks whether the sum of distances from an interior point to a triangle's vertices is at least twice the sum of its distances to the three sides.
Asks whether every infinite set of naturals with density zero has unbounded as .
Asks whether the uniform random graph with vertices and edges, , almost surely has a path of length , where as and as . Proved by Ajtai, Komlós and Szemerédi in 1981.
Asks whether a block design on points, with a prime power and every pair of points in exactly one block, must have at least blocks if it has more than .
Asks whether, for , every graph with vertices and edges, the Turán number for , has an -clique with degree sum at least . Proved by Bollobás and Nikiforov in 2005; the erdosproblems.com wording, with no range, fails below vertices.
Asks whether every graph on vertices with more than edges has an edge in at least triangles. Proved by Khadzhiivanov and Nikiforov in 1979, by Edwards (unpublished), and by Bollobás and Nikiforov in 2005.
Asks whether a real function with every difference continuous must be the sum of a continuous function and an additive one.
Asks whether a real function with every difference measurable is the sum of a measurable function, an additive function and a function with for each and almost all . The erdosproblems.com wording asks for a continuous first term.
Asks whether, for each , there is a space of dimension whose square also has dimension .
Asks whether every graph on vertices with minimum degree at least has vertex-disjoint copies of . This is Erdős's conjecture, proved by Hajnal and Szemerédi in 1970 and reproved in refereed papers of 2008 and 2010.
Asks whether a graph with vertices and edges has two vertices joined by disjoint paths. False for if the paths are vertex-disjoint, true for every if they are edge-disjoint; Bloom's catalog labeled it solved.
Asks whether, for , every graph with vertices and edges has a cycle and another vertex adjacent to three of its vertices. Proved by Thomassen in 1974; the erdosproblems.com wording, with no range, fails at .
Asks whether, for every , the largest chromatic number of a -free graph on vertices satisfies for some constant .
Asks whether, for every , the largest such that some -chromatic graph on vertices has every odd cycle longer than is of order .
Asks whether a graph in which every subgraph on vertices has an independent set of size at least has chromatic number at most .