02
Erdős conjecture on arithmetic progressions Open
If A ⊆ N A \subseteq \mathbb{N} A ⊆ N has divergent reciprocal sum ∑ a ∈ A 1 / a = ∞ \sum_{a \in A} 1/a = \infty ∑ a ∈ A 1/ a = ∞ , prove it contains arbitrarily long arithmetic progressions. erdos-arithmetic-progressions
attack →
03
Growth rate of diagonal Ramsey numbers Open
For the diagonal Ramsey number R ( k ) R(k) R ( k ) , determine whether lim k R ( k ) 1 / k \lim_k R(k)^{1/k} lim k R ( k ) 1/ k exists and its value. It is known that 2 ≤ lim inf ≤ lim sup ≤ 4 \sqrt{2} \leq \liminf \leq \limsup \leq 4 2 ≤ lim inf ≤ lim sup ≤ 4 . erdos-ramsey-growth
attack →
04
Erdős–Rado sunflower conjecture Open
A k k k -sunflower is a family of k k k sets with a common pairwise intersection (core). Prove that any family of more than C k w C_k^{\,w} C k w sets of size w w w contains a k k k -sunflower, for a constant C k C_k C k depending only on k k k . 05
Erdős–Szemerédi sum-product problem Open
For finite A ⊆ R A \subseteq \mathbb{R} A ⊆ R , prove max ( ∣ A + A ∣ , ∣ A A ∣ ) ≫ ∣ A ∣ 2 − ε \max(|A+A|,\, |AA|) \gg |A|^{2 - \varepsilon} max ( ∣ A + A ∣ , ∣ AA ∣ ) ≫ ∣ A ∣ 2 − ε for every ε > 0 \varepsilon > 0 ε > 0 : a set cannot be both additively and multiplicatively structured. erdos-sum-product
attack →
06
Erdős–Hajnal conjecture Open
For every fixed graph H H H , prove there is c ( H ) > 0 c(H) > 0 c ( H ) > 0 such that every n n n -vertex graph with no induced copy of H H H has a clique or independent set of size ≥ n c ( H ) \geq n^{c(H)} ≥ n c ( H ) . 07
Erdős–Turán conjecture on additive bases Open
If A ⊆ N A \subseteq \mathbb{N} A ⊆ N is a basis of order 2 (every large integer is a sum of two elements of A A A ), prove its representation count r A ( n ) r_A(n) r A ( n ) is unbounded. erdos-turan-additive-basis
attack →
08
Erdős–Szekeres convex-polygon problem Open
Let E S ( n ) \mathrm{ES}(n) ES ( n ) be the least N N N such that any N N N points in general position contain a convex n n n -gon. Prove the conjectured exact value E S ( n ) = 2 n − 2 + 1 \mathrm{ES}(n) = 2^{\,n-2} + 1 ES ( n ) = 2 n − 2 + 1 . erdos-szekeres-convex-polygon
attack →
09
Maximum size of a Sidon set Open
A Sidon set in { 1 , … , N } \{1, \ldots, N\} { 1 , … , N } has all pairwise sums distinct. Its maximum size is N 1 / 2 + E ( N ) N^{1/2} + E(N) N 1/2 + E ( N ) ; determine the true order of the error E ( N ) E(N) E ( N ) (conjectured O ( N ε ) O(N^{\varepsilon}) O ( N ε ) for every ε > 0 \varepsilon > 0 ε > 0 ). erdos-sidon-set-size
attack →
10
Erdős–Gyárfás cycle conjecture Open
Prove that every graph with minimum degree at least 3 3 3 contains a cycle whose length is a power of 2 2 2 — or exhibit a min-degree- 3 3 3 graph with no such cycle. erdos-gyarfas-cycles
attack →