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

Brendon Stanton

paper

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

arXiv:1405.5957

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{1}{2} + ω (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$ .