OPEN
Let $Q_n$ be the $n$-dimensional hypercube graph (so that $Q_n$ has $2^n$ vertices and $n2^{n-1}$ edges). Prove that
\[R(Q_n) \ll 2^n.\]
Conjectured by Burr and Erdős. The trivial bound is
\[R(Q_n) \leq R(K_{2^n})\leq C^{2^n}\]
for some constant $C>1$. This was improved a number of times; the current best bound due to Tikhomirov
[Ti22] is
\[R(Q_n)\ll 2^{(2-c)n}\]
for some small constant $c>0$. (In fact $c\approx 0.03656$ is permissible.)
See also the entry in the graphs problem collection.
