All Random Solved Random 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.