On the coverings of the d-cube for d <= 6

Abstract

A cut of the d-cube is any maximal set of edges that is sliced by a hyperplane, that is, intersecting the interior of the d-cube but avoiding its vertices. A set of k distinct cuts that cover all the edges of the d-cube is called a k-covering. The cut numberS(d) of the d-cube is the minimum number of hyperplanes that slice all the edges of the d-cube. Here by applying the geometric structures of the cuts, we prove that there are exactly 13 non-isomorphic 3-coverings for the 3-cube. Moreover, an extended algorithmic approach is given that has the potential to find 5(7) by means of largely-distributed computing. As a computational result, we also present a complete enumeration of all 4-coverings of the 4-cube as well as a complete enumeration of all 4-coverings of 78 edges of the 5-cube. Crown Copyright (C) 2008 Published by Elsevier B.V. All rights reserved.