2 solved out of 7 shown (show only solved or open)
SOLVED - $1000 Can the smallest modulus of a covering system be arbitrarily large? Described by Erdős as 'perhaps my favourite problem'. Hough [Ho15], building on work of Filaseta, Ford, Konyagin, Pomerance, and Yu [FFKPY07], has shown the answer is no: the smallest modulus must be at most$10^{18}$. An alternative, simpler, proof was given by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22], who improved the bound on the smallest modulus to$616000$. OPEN -$1000
Let $f(n,k)$ be minimal such that every $\mathcal{F}$ family of $n$-uniform sets with $\lvert F\rvert \geq f(n,k)$ contains a $k$-sunflower. Is it true that $f(n,k) < c_k^n$ for some constant $c_k>0$?
Erdős and Rado [ErRa60] originally proved $f(n,k)\leq (k-1)^nn!$. Kostochka [Ko97] improved this slightly (in particular establishing an upper bound of $o(n!)$, for which Erdős awarded him the consolation prize of \$100), but the bound stood at$n^{(1+o(1))n}$for a long time until Alweiss, Lovett, Wu, and Zhang [ALWZ20] proved $f(n,k) < (Ck\log n\log\log n)^n$ for some constant$C>1$. This was refined slightly, independently by Rao [Ra20], Frankston, Kahn, Narayanan, and Park [FKNP19], and Bell, Chueluecha, and Warnke [BCW21], leading to the current record of $f(n,k) < (Ck\log n)^n$ for some constant$C>1$. In [Er81] offered \$1000 for a proof or disproof even just in the special case when $k=3$, which he expected 'contains the whole difficulty'. He also wrote 'I really do not see why this question is so difficult'.

The usual focus is on the regime where $k=O(1)$ is fixed (say $k=3$) and $n$ is large, although for the opposite regime Kostochka, Rödl, and Talysheva [KoRoTa99] have shown $f(n,k)=(1+O_n(k^{-1/2^n}))k^n.$

OPEN - $1000 Let$h(N)$be the maximum size of a Sidon set in$\{1,\ldots,N\}$. Is it true that, for every$\epsilon>0$, $h(N) = N^{1/2}+O_\epsilon(N^\epsilon)?$ A problem of Erdős and Turán. It may even be true that$h(N)=N^{1/2}+O(1)$, but Erdős remarks this is perhaps too optimistic. Erdős and Turán [ErTu41] proved an upper bound of$N^{1/2}+O(N^{1/4})$, with an alternative proof by Lindström [Li69]. Both proofs in fact give $h(N) \leq N^{1/2}+N^{1/4}+1.$ Balogh, Füredi, and Roy [BFR21] improved the bound in the error term to$0.998N^{1/4}$, which has been further optimised by O'Bryant [OB22] to yield $h(N)\leq N^{1/2}+0.99703N^{1/4}$ for sufficiently large$N$. See also [241] and [840]. Additional thanks to: Zach Hunter OPEN -$1000
Does every graph with minimum degree at least 3 contain a cycle of length $2^k$ for some $k\geq 2$?
Conjectured by Erdős and Gyárfás, who believed the answer must be negative, and in fact for every $r$ there must be a graph of minimum degree at least $r$ without a cycle of length $2^k$ for any $k\geq 2$.

This was solved in the affirmative if the minimum degree is larger than some absolute constant by Liu and Montgomery [LiMo20] (therefore disproving the above stronger conjecture of Erdős and Gyárfás). Liu and Montgomery prove a much stronger result: if the average degree of $G$ is sufficiently large then there is some large integer $\ell$ such that for every even integer $m\in [(\log \ell)^8,\ell]$, $G$ contains a cycle of length $m$.

SOLVED - $1000 Let$r_k(N)$be the size of the largest subset of$\{1,\ldots,N\}$which does not contain a non-trivial$k$-term arithmetic progression. Prove that$r_k(N)=o(N)$. Proved by Szemerédi [Sz74]. The best known bounds are due to Kelley and Meka [KeMe23] for$k=3$(with further slight improvements in [BlSi23]), Green and Tao [GrTa17] for$k=4$, and Leng, Sah, and Sawhney [LSS24] for$k\geq 5$. See also [3]. Additional thanks to: Zachary Chase OPEN -$1000
Determine which countable ordinals $\beta$ have the property that, if $\alpha=\omega^{^\beta}$, then in any red/blue colouring of the edges of $K_\alpha$ there is either a red $K_\alpha$ or a blue $K_3$.
This property holds for $\beta=2$ and not for $3\leq \beta <\omega$ (Specker [Sp57]) and for $\beta=\omega$ (Chang [Ch72]).
The first open case is $\beta=\omega^2$ (see [591]). Galvin and Larson [GaLa74] have shown that if $\beta\geq 3$ has this property then $\beta$ must be 'additively indecomposable', so that in particular $\beta=\omega^\gamma$ for some $\gamma<\omega_1$. Galvin and Larson conjecture that every $\beta\geq 3$ of this form has this property.
OPEN - $1000 The cochromatic number of$G$, denoted by$\zeta(G)$, is the minimum number of colours needed to colour the vertices of$G$such that each colour class induces either a complete graph or empty graph. Let$\chi(G)$denote the chromatic number. If$G$is a random graph with$n$vertices and each edge included independently with probability$1/2$then is it true that almost surely $\chi(G) - \zeta(G) \to \infty$ as$n\to \infty$? A problem of Erdős and Gimbel (see also [Gi16]). At a conference on random graphs in Poznan, Poland (most likely in 1989) Erdős offered \$100 for a proof that this is true, and \$1000 for a proof that this is false (although later told Gimbel that \$1000 was perhaps too much).
It is known that almost surely $\frac{n}{2\log_2n}\leq \zeta(G)\leq \chi(G)\leq (1+o(1))\frac{n}{2\log_2n}.$ (The final upper bound is due to Bollobás [Bo88]. The first inequality follows from the fact that almost surely $G$ has clique number and independence number $< 2\log_2n$.)