Excluded–Minor Characterizations of Antimatroids arisen from Posets and Graph Searches

✍ Scribed by M. Nakamura

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 616 KB
• Volume: 11
• Category: Article
• ISSN: 1571-0653
• DOI: 10.1016/s1571-0653(04)00098-8

✦ Synopsis

An antimatroid is a family of sets such that it contains an empty set, and it is accessible and closed under union of sets. An antimatroid is a 'dual' or 'antipodal' concept of matroill.

We shall show that an antimatroid is derived from shelling of a poset if and only if it. docs not contain a minor isomorphic to (S_{7}) where (S_{7}) is the smallest semimodular lattice that, is not. modular (See Fig.1). It is also shown that an antimatroid is a node-search antimatroid of is digraph if and only if it does not contains a minor isomorphic to (D_{5}) where (D_{5}) is a latic`" consisting of five elements (\emptyset,{x},{y},{x, y}) and ({x, y, z}). Furthermore, an antimatroid is shown to be a node-search antimatroid of an undirected graph if and only if it does not conlitin (D_{5}) nor (S_{10}) as a minor: (S_{10}) is a locally free lattice consisting of ten elements shown in Fig.2.