Problem 181

Erdős Problem #181: declared status 'open'. Formalized: no. 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.$$ Current best: The trivial bound is$$R(Q_n) \leq R(K_{2^n})\leq C^{2^n}$$for some constant $C>1$. Prize: no. Tags: graph theory, ramsey theory.