Combinatorics of lopsided sets

Abstract

We develop a theory of isometric subgraphs of hypercubes for which a certain inheritance of isometry plays a crucial role. It is well known that median graphs and closely related graphs embedded in hypercubes bear geometric features that involve realizations by solid cubical complexes or are expressed by Euler-type counting formulae for cubical faces. Such properties can also be established for antimatroids, and in fact, a straightforward generalization ("conditional antimatroid") captures this concept as well as median convexity. The key ingredient for the cube counting formulae that work in conditional antimatroids is a simple cube projection property, which, when letting sets be encoded by sign vectors, is seen to be invariant under sign switches and guarantees linear independence of the corresponding sign vectors. It then turns out that a surprisingly elementary calculus of projection and lifting gives rise to a plethora of equivalent characterizations of set systems bearing these properties, which are not necessarily closed under intersections (and thus are more general than conditional antimatroids). One of these descriptions identifies these particular set systems alias sets of sign vectors as the lopsided sets originally introduced by Lawrence in order to investigate the subgraphs of the n-cube that encode the intersection pattern of a given convex set K with the closed orthants of the n-dimensional Euclidean space. This demonstrates that the concept of lopsidedness in its various disguises is most natural and versatile in combinatorics. (C) 2005 Elsevier Ltd. All rights reserved.