Great problems

20th century

1. 1932
   Erdős discrepancy problemCombinatorics and discrete mathematics, Arithmetic and number theory. Every infinite $\pm 1$ sequence has arbitrarily large partial sums along some homogeneous arithmetic progression $d, 2d, \dots, nd$; proved by Terence Tao in 2015.ErdősTTTerence Tao, 2015
2. 1935
   Happy ending problem (Erdős–Szekeres)Combinatorics and discrete mathematics, Geometry. How many points in general position in the plane are needed to guarantee a convex $n$-gon? Posed by Esther Klein for $n = 4$ in 1933—leading to her marriage to George Szekeres and Paul Erdős's nickname "the Happy Ending Problem"—the conjectured exact value $\mathrm{ES}(n) = 2^{n-2} + 1$ is proved only for $n \le 6$, though Andrew Suk established $\mathrm{ES}(n) = 2^{n + o(n)}$ in 2016.ErdősOpen
3. 1941
   Erdős–Turán conjecture on additive basesArithmetic and number theory, Combinatorics and discrete mathematics. If a set of natural numbers eventually covers all integers by pairwise sums (an asymptotic basis of order $2$), must some integers have arbitrarily many representations as a sum of two elements? Posed by Paul Erdős and Pál Turán in 1941, the conjecture $\limsup_{n \to \infty} r_A(n) = \infty$ remains open.ErdősOpen
4. 1946
   Erdős unit distance problemGeometry, Combinatorics and discrete mathematics. How many pairs among $n$ points in the plane can lie at distance $1$? Bounded above by $O(n^{4/3})$, while a 2026 number-theoretic construction disproved Erdős's $n^{1+o(1)}$ conjecture by proving $u(n) = \Omega(n^{1+c})$.ErdősOpen
5. 1948
   Erdős–Straus conjectureArithmetic and number theory. Formulated in 1948 by Paul Erdős and Ernst G. Straus, this Egyptian-fraction conjecture asks whether $4/n$ is always a sum of three reciprocals of positive integers. Because any decomposition for a divisor $d \mid n$ scales to a decomposition for $n$, it suffices to prove the statement when $n = p$ is prime. Simple algebraic identities immediately cover primes $p \not\equiv 1 \pmod{24}$, and larger modular covering systems eliminate almost all residue classes, enabling computer verification up to $n = 10^{17}$, yet a complete covering system of finitely many identities cannot exist.ErdősOpen
6. 1960
   Erdős–Rado sunflower conjectureCombinatorics and discrete mathematics. How large can a family of $w$-element sets be without containing $r$ sets whose pairwise intersections are all identical? Posed by Paul Erdős and Richard Rado in 1960 with the factorial bound $w! (r - 1)^w$, the problem saw a landmark breakthrough in 2019 by Alweiss, Lovett, Wu, and Zhang (refined to $(C r \log w)^w$), while the pure exponential bound $C_r^w$ remains open.ErdősOpen
7. 1972
   Erdős–Faber–Lovász conjectureCombinatorics and discrete mathematics. Can the union of $n$ cliques of size $n$ that pairwise share at most one vertex always be properly vertex-colored with $n$ colors? Posed by Paul Erdős, Vance Faber, and László Lovász in 1972, the conjecture was proved for all sufficiently large $n$ in 2021 by Kang, Kelly, Kühn, Methuku, and Osthus (published in the Annals of Mathematics in 2023), while small cases $n \le 12$ are verified computationally and intermediate values remain open.ErdősSolved
8. 1973
   Erdős conjecture on arithmetic progressionsArithmetic and number theory, Combinatorics and discrete mathematics. If the sum of reciprocals $\sum_{n \in A} \frac{1}{n} = \infty$, must $A$ contain arbitrarily long arithmetic progressions? Proved for $k = 3$ by Thomas Bloom and Olof Sisask (2020), while all lengths $k \ge 4$ remain open.ErdősOpen
9. 1977
   Erdős–Hajnal conjectureCombinatorics and discrete mathematics. Whereas general $n$-vertex graphs need only contain a clique or independent set of logarithmic size $\Theta(\log n)$, Paul Erdős and András Hajnal conjectured in 1977 that forbidding any fixed induced subgraph $H$ forces a polynomial-size clique or independent set $n^{\delta_H}$.ErdősOpen