On the complexity of representing sets of vertices in the n-cube
Couceiro, Miguel; Foldes, Stephan; Lehtonen, Erkko
ICNAAM 2005, Wiley-VCH, Weinheim, (2005), 876-877
Representations of an arbitrary set of vertices of an n-dimensional cube in terms of convex sets are compared with respect to their complexity. The notion of complexity used in the representations is based on the union, symmetric difference and ternary median operations. Convexity of a set of vertices refers to Hamming distance or, equivalently, to the intersection of cubes with supporting hyperplanes.