Bounding the size of square-free subgraphs of the hypercube (Q1024494)

It was conjectured by Erdős that the maximum size of a subgraph \(G\) of the \(n\)-dimensional cube \(Q_n\) without a square (\(Q_2)\) is asymptotically \(1/2\) the size of \(Q_n\). The objective of the authors is to determine \[ d = \max_{Q_2 \not\subset G \subset Q_n} \frac{e(G)}{e(Q_n)}, \] where \(e(G)\) denotes the number of edges in the graph \(G\). They show that \(d \leq \alpha = .62256..\) where \(\alpha\) is a root of the polynomial \(x^4 - 4x^3 + 4x^2 - 6x + 3\). This bound was obtained by using properties of the \(5\)-cube \(Q_5\) and considering the \(Q_5\) subgraphs of \(Q_n\).