The prolific
mathematicianPaul Erdős and his various collaborators made many famous mathematical
conjectures, over a wide field of subjects, and in many cases Erdős offered monetary rewards for solving them.
Unsolved
The
Erdős–Gyárfás conjecture on cycles with lengths equal to a power of two in graphs with minimum degree 3.
The
Erdős–Hajnal conjecture that in a family of graphs defined by an excluded induced subgraph, every graph has either a large clique or a large independent set.[1]
A conjecture that would have strengthened the
Furstenberg–Sárközy theorem to state that the number of elements in a square-difference-free set of positive integers could only exceed the square root of its largest value by a polylogarithmic factor, disproved by
András Sárközy in 1978.[9]
The
Erdős–Heilbronn conjecture in combinatorial number theory on the number of sums of two sets of residues modulo a prime, proved by Dias da Silva and Hamidoune in 1994.[11]
The
Erdős–Graham conjecture in combinatorial number theory on monochromatic Egyptian fraction representations of unity, proved by
Ernie Croot in 2000.[12]
The Erdős primitive set conjecture that the sum for any primitive set A (a set where no member of the set divides another member) attains its maximum at the set of primes numbers, proved by Jared Duker Lichtman in 2022.[21][22][23]
The Erdős-Sauer problem about maximum number of edges an n-vertex graph can have without containing a k-
regular subgraph, solved by Oliver Janzer and
Benny Sudakov[24][25]
^Hajnal, A.;
Szemerédi, E. (1970), "Proof of a conjecture of P. Erdős", Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), North-Holland, pp. 601–623,
MR0297607.
^Sárközy, A. (1978), "On difference sets of sequences of integers. II", Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, 21: 45–53 (1979),
MR0536201.
^Ramaré, Olivier; Granville, Andrew (1996), "Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients", Mathematika, 43 (1): 73–107,
doi:
10.1112/S0025579300011608
^Lichtman, Jared Duker (2022-02-04). "A proof of the Erdős primitive set conjecture".
arXiv:2202.02384 [
math.NT].