Problem #1035: Is there a constant $c>0$ such that every graph on $2^n$...

---

Progress

Erdős [Er93] says 'if the conjecture is false, two related problems could be asked':

• Determine or estimate the smallest $m>2^n$ such that every graph on $m$ vertices with minimum degree $>(1-c)2^n$ contains a $Q_n$, and


• For which $u_n$ is it true that every graph on $2^n$ vertices with minimum degree $>2^n-u_n$ contains a $Q_n$.

See also [576] for the extremal number of edges that guarantee a $Q_n$.