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

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.''