Abstract: An antimatroid is an accessible set system (U,F) closed under union. Every antimatroid may be represented as a graph whose vertices are sets of F, where two vertices are adjacent if the corresponding sets are differ by one element. This graph is a partial cube. Hence an antimatroid with the ground set U of size n may be isometrically embedded into the hypercube {0, 1}n. Thus the distance on an antimatroid considered as a graph coincides with the Hamming distance. A poset antimatroid is an antimatroid, which is formed by the lower sets of a poset. We consider different definitions of the distance between elements of an antimatroid, and give a new characterization of poset antimatroids.

Keywords: antimatroid, partial cube, zigzag distance, Hamming distance.

ACM Classification Keywords: G.2

MSC: 05C12; 52B40

Link:

DISTANCES ON ANTIMATROIDS

Yulia Kempner, Vadim E. Levit

http://www.foibg.com/ibs_isc/ibs-25/ibs-25-p14.pdf