A Generalization of the Methods of Brass, Harboth, and Nieborg

Abstract

In 1995, Brass, Harborth and Nienborg disproved a conjecture of Erdős when they showed that a $C_4$-free subgraph of the hypercube, $Q_n$, can have at least $(\frac 12 +ω(1))e(Q_n)$ edges. In this paper, we generalize the idea of Brass, Harborth and Nienborg to provide good constructions of $Q_3$-free subgraphs of $Q_n$ for some small values of $n$.