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 (contrary to Erdős' expectations) that 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$.

OPEN - $1000

Does every finite 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$.

An infinite tree with minimum degree $3$ shows that the answer is trivially false for infinite graphs.

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].

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.

See also [590].

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$.)

Heckel [He24] and, independently, Steiner [St24b] have shown that it is not the case that $\chi(G)-\zeta(G)$ is bounded with high probability, and in fact if $\chi(G)-\zeta(G) \leq f(n)$ with high probability then $f(n)\geq n^{1/2-o(1)}$ along an infinite sequence of $n$. Heckel conjectures that, with high probability, \[\chi(G)-\zeta(G) \asymp \frac{n}{(\log n)^3}.\]