Covering the vertices of the hypercube
------------------------------------
When we work with coordinates, plane geometry (with an x-coordinate and a y-coordinate) and three-dimensional geometry (with an x-coordinate, a y-coordinate and a z-coordinate) readily generalize to geometry in n dimensions. In two dimensions, the points whose coordinates are all either 0 or 1 form a square. In three-dimensional space, the vertices, denoted 000, 100, 110, 010, 001, 101, 111 and 011, form a cube. In n-dimensional space, we obtain a hypercube, denoted H*n. We can also consider hyperplanes, which are simply the sets of points described by equations of the form a*1 x1 + a2 x2 + … +*an xn = b*.
Once the setting is in place, mathematicians have been playing a little game for some time: covering sets of points with as few hyperplanes as possible, particularly sets consisting of certain vertices of the hypercube. In 1993, the Israeli Noga Alon and the Hungarian Zoltán Füredi proved that covering every vertex of the hypercube except the origin (the vertex whose coordinates are all zero, sometimes denoted 0*n ) requires exactly n hyperplanes. We can choose the hyperplanes with equations xi* = 1. The challenge is to understand why fewer hyperplanes cannot suffice.
