Excluded-minor characterizations of antimatroids arisen from posets and graph searches

✍ Scribed by M. Nakamura

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 161 KB
• Volume: 129
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(02)00581-4

✦ 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 an 'antipodal' concept of matroid.

We shall show that an antimatroid is derived from shelling of a poset if and only if it does not contain a minor isomorphic to S7 where S7 is the smallest semimodular lattice that is not modular. It is also shown that an antimatroid is a node-search antimatroid of a rooted digraph if and only if it does not contain a minor isomorphic to D5 where D5 is a lattice consisting of ÿve elements ∅; {x}; {y}; {x; y} and {x; y; z}. Furthermore, it is shown that an antimatroid is a node-search antimatroid of a rooted undirected graph if and only if it does not contain D5 nor S10 as a minor: S10 is a locally free lattice consisting of 10 elements.