Excluded-minor characterizations of antimatroids arisen from posets and graph searches. (Q1406042)

Four classes of antimatroids, each closed under taking minors, are studied, and they are characterized by excluded minors. Three particular antimatroids, denoted \(D_5\), \(S_5\), and \(S_{10}\) (where in each case the subscript indicates the cardinality of the underlying set) are given. It is shown that the antimatroids not having \(S_7\) as a minor are the ``poset shelling antimatroids''; those with \(D_5\) excluded are the ``node search antimatroids of rooted digraphs''; those with \(S_7\) and \(D_5\) excluded are the ``node search antimatroids of rooted directed trees''; and those with \(D_5\) and \(S_{10}\) excluded are the ``node search antimatroids of rooted undirected graphs.''