On the complexity of representing sets of vertices in the n-cube

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.