Evasiveness of Graph Properties

Definition 13.1. A graph property is called monotone if the set of graphs that satisfy this property is closed under removal of edges. 

Examples of monotone properties include planarity and the property of being disconnected. The condition in Definition 13.1 is basically the same condition as the one defining abstract simplicial complexes. In fact, the following is the standard construction associating an abstract simphcial complex to a monotone graph property. 

Definition 13.2. Given a monotone graph property Q of graphs with n vertices, the abstract simplicial complex A Q) has ( ) vertices labeled by ordered 

A graph property is called trivial if either no graphs with n vertices satisfy it, in which case A Q) is void, or all graphs with n vertices satisfy it, in which case A Q) is an (n — l)-dimensional simplex. 

Let us now consider the following algorithmic situation. We are given a certain graph property Q, which we know, and a certain graph G, which we do not know. However, we can ask an oracle questions of the type 

---