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.
494 of 1,221 problems match
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Asks whether the order of every finite projective plane must be a prime power.
Asks whether the largest number of mutually orthogonal Latin squares of order is .
Asks for a reasonable such that, for almost all , the least with satisfies .
Asks, for all large , for a non-trivial pairwise balanced design on points in which each block size is used only times.
Asks whether, for every graph of chromatic number and every cardinal , there is a graph of chromatic number all of whose finite subgraphs occur in .
Asks whether every triangle-free graph of infinite chromatic number contains every tree as an induced subgraph.
Asks whether a graph of infinite chromatic number must have a subgraph of chromatic number for every infinite cardinal .
Asks whether can always be written as the edge-disjoint union of given trees , where has vertices. This tree packing conjecture of Gyárfás is open, and one arXiv proof claim was withdrawn.
Asks whether, for each , some has of lower density at least while every integer has representations as a sum of two elements of .
Asks for the best constant such that reals whose every four-element subset has contain a Sidon set of size .
Asks whether large chromatic number forces large dichromatic number, and whether large cochromatic number forces a subgraph of large dichromatic number. Cochromatic classes induce complete or empty graphs, and dichromatic colorings avoid monochromatic oriented cycles.
Asks for estimates of , the least Turán number over graphs with vertices and edges, for , and whether it is strictly monotone in . Open; asymptotics are known only at the pairs and .
Asks for the size of the largest Sidon subset of the squares , and whether it is .
Asks whether every infinite set of natural numbers whose finite subsets each contain a dissociated subset (one with distinct subset sums) of proportional size is a finite union of dissociated sets.
Two players alternately color the edges of a complete graph, and the first wins if her largest monochromatic clique beats her opponent's. Asks whether the first player can win.
Asks whether, for the product of the first primes, there is always a prime with such that is prime.
Asks whether the squares contain arbitrarily long quasi-progressions, with all gaps between and for a fixed , and arbitrarily large cubes .
Asks how large a subset of any real numbers can be chosen with no two distinct elements summing to one of the numbers (the Erdős–Moser function ). Known bounds are for some .
Estimates , the size of the largest sum-free subset (no solution to ) guaranteed inside any set of integers. The main term is settled and the second-order term is ; an unrefereed 2025 preprint claims that it is at least .
Asks for which functions there is a graph on vertices in which every induced subgraph on vertices has a clique and an independent set of size .
Asks whether there is an such that, for all large , some graph on vertices with at least edges can be edge-colored with colors so that every gets four distinct colors.