Problem 86 — Visual explainer (undergrad)
=========================================

Problem statement
---------------
Let $Q_n$ be the $n$-dimensional hypercube graph (so that $Q_n$ has $2^n$ vertices and $n2^{n-1}$ edges). Is it true that every subgraph of $Q_n$ with\[\geq \left(\frac{1}{2}+o(1)\right)n2^{n-1}\]many edges contains a $C_4$?

Picture
-------
Graph picture:

o---o
|\  |
| \ |
o---o    K4 is the complete graph on 4 vertices (all connections)

Question: what to look at
------------------------
- Restate the problem as: given the constraint, what asymptotic bound or
  structure must follow?
- Use the comments as benchmarks (best known bounds / constructions).

Context
-------
Area hint: infinite graph theory / Ramsey-type decompositions.

Notation (if it appears above)
-----------------------------
- `o(g(n))` means "grows strictly smaller than g(n)" (ratio → 0 as n→∞).

Benchmarks / known results (from comments)
----------------------------------------
- Let $f(n)$ be the maximum number of edges in a subgraph of $Q_n$ without a
  $C_4$, so that this conjecture is that $f(n)\leq
  (\frac{1}{2}+o(1))n2^{n-1}$.
- Erd\H{o}s showed that\[f(n) \geq
  \left(\frac{1}{2}+\frac{c}{n}\right)n2^{n-1}\]for some constant $c>0$, and
  wrote it is 'perhaps not hopeless' to determine $f(n)$ exactly.
- Brass, Harborth, and Nienborg improved this to\[f(n) \geq
  \left(\frac{1}{2}+\frac{c}{\sqrt{n}}\right)n2^{n-1}\]for some constant
  $c>0$.
- Balogh, Hu, Lidicky, and Liu proved that $f(n)\leq 0.6068 n2^{n-1}$.