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 when points in the plane can be given positive weights so that every line through at least two of them has the same total weight.
Asks whether every graph of chromatic number has an edge that lies on a cycle of every sufficiently large length.
Asks whether every with of positive upper density splits into two parts whose sumsets both have positive upper density, and whether some basis of order has no split in which both self-sumsets have bounded gaps.
Asks whether , where is the fewest edges whose deletion makes bipartite some -vertex graph of chromatic number whose proper subgraphs all have smaller chromatic number.
Asks for the size of the second largest component of the random graph on vertices with edge probability . Aldous (1997) gives order , while erdosproblems.com credits Komlós, Sulyok and Szemerédi's supercritical bound.
Asks whether a uniform random graph on vertices with at least edges is almost surely Hamiltonian. This Erdős–Rényi conjecture was settled by Korshunov and by Komlós and Szemerédi.
Asks how many edges a random -uniform hypergraph on vertices needs so that it almost surely has vertex-disjoint edges.
Asks whether, for every , some graph of infinite chromatic number has an independent set of size at least in every -vertex subgraph.
Asks whether the smallest gap between consecutive cycle lengths in a graph of chromatic number can be arbitrarily large, and whether this can happen with large girth.
Asks whether a graph with minimum degree and girth greater than must have distinct cycle lengths.
Asks whether some constant makes the list chromatic numbers of every -vertex graph and its complement sum to more than .
Asks whether , where is the largest number such that some points in have every point equidistant from at least of the others.
Asks whether a set of points in the plane can determine distinct distances, each occurring for more than pairs of points.
Asks for small values of , the largest cochromatic number of an -vertex graph, and in particular whether . The cochromatic number is the fewest colors whose classes each induce a complete or an empty graph.
Asks for the growth rate of the largest cochromatic number of a graph embeddable on the orientable surface of genus . The cochromatic number is the fewest colors whose classes each induce a complete or an empty graph.
Asks whether every graph with chromatic number contains a subgraph with cochromatic number . The cochromatic number is the fewest colors such that every color class induces a complete graph or an independent set.
Asks whether a -free graph with cochromatic number has chromatic number . Steiner answered no in 2024 with graphs of clique number , cochromatic number and chromatic number .
Asks whether, for some set of naturals and some , the number of representations of as a sum of two elements of , summed over , equals .
Asks whether, for some set of naturals and some , the number of representations of as a sum of three elements of , summed over , equals .
Asks for an asymptotic formula for , the largest number of edges in a graph on vertices with no .
Asks whether, for large , the most edges in an -vertex graph with no cycle carrying chords at one cycle vertex is . Proved for by Jiang (2004); a 2026 preprint claims the threshold.
Asks whether , where is the largest size such that, for every , some subset of of that size has no subset summing to .
Asks whether , where is the size of the largest Sidon set guaranteed inside any integers in which no number has more than representations as a sum of two elements.