ANTIPODAL GRAPHS AND ORIENTED MATROIDS

A graph is antipodal if, for every vertex v, there exists exactly one vertex vBAR which is not closer to v than every vertex adjacent to vBAR. In this paper we consider the problem of characterizing tope graphs of oriented matroids, which constitute a broad class of antipodal graphs. One of the results is to characterize tope graphs of more general systems than oriented matroid, namely, an L1-embeddable system and acycloid. Another is to characterize tope graphs of oriented matroids of rank at most three. The characterization theorem says: a graph G is isomorphic to the tope graph of an oriented matroid of rank at most three if and only if G is antipodal, planar and isometrically embeddable in some hypercube. For tope graphs of oriented matroids of any higher rank, the characterization problem is still open.