Antimatroids and oracle complexity

Abstract

Antimatroids are a new and growing area of mathematics. They arise out of matroids and greedoids, and have a rich structure of their own, as is most naturally seen when considering convex closure in Euclidean space. I give a brief background theory of matroids and greedoids, then survey the current state of knowledge about antimatroids, focusing on some of the more basic properties. I develop new theory for antimatroids in the area of oracles and oracle complexity, and compare the relative strengths of the oracles as well as giving examples of how the oracles are used to determine some simple properties of antimatroids. Finally, I consider the antimatroids arising from partially ordered sets, and from directed and undirected graphs. I give a characterization of these antimatroids in terms of feasible sets and in terms of circuits, and then go on to show how to construct and recognise them, and consider the complexity of such issues. I prove that an antimatroid can be recognised in polynomial time if it is derivable from a downward ideal poset, and that an antimatroid can only be recognised in exponential time if it is derivable from a directed, or undirected, graph.