2 solved out of 6 shown

$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, 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$. 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.\]

$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)?\]

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

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

$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$, Green and Tao [GrTa17] for $k=4$, and Leng, Sah, and Sawhney [LSS24] for $k\geq 5$.

See also [3].

$1000

Let $r_k(N)$ be the largest possible size of a subset of $\{1,\ldots,N\}$ that does not contain any non-trivial $k$-term arithmetic progression. Prove an asymptotic formula for $r_k(N)$.

The best known bounds are due to Kelley and Meka [KeMe23] for $k=3$, Green and Tao [GrTa17] for $k=4$, and Leng, Sah, and Sawhney [LSS24] for $k\geq 5$. Erdős remarked this is 'probably unattackable at present'. Given that Erdős elsewhere offered \$5000 just for (essentially) showing that $r_k(N)=o_k(N/\log N)$, the value of this prize seems odd.