On the maximum number of edges in a c4-free subgraph of qn

For the maximum number f(n) of edges in a C₄-free subgraph of the n-dimensional cube-graph Q_n we prove f(n) ≥ 1/2(n +√n)2^n?1 for n = 4^r, and f(n) ≥ 1/2(n +0.9√n)2^n?1 for all n ≥ 9. This disproves one version of a conjecture of P. Erdos. © 1995 John Wiley & Sons, Inc.