Monotone graph property

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

Every nontrivial monotone graph property for graphs on n vertices is evasive. 

Proposition 13.9. A monotone graph property Q is evasive if and only if the associated abstract simplicial complex A Q) is evasive. 

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

Assume now that n = p, for some prime number p. Assume that the Evasiveness Conjecture is false for that value of n, and let Q denote a monotone, but nonevasive, graph property. Furthermore, let GF(n) denote a field with n elements, which exists because n is a prime power, and let GF(n) denote the multiplicative group of that field. Let F be a subgroup of [Pg.228]

Fig. 2.7 shows the graph of T in A. The shape of the graph explains the mapping s name. All points with x < 0 are mapped monotonically to —oo. Points with x > 1 are first mapped to 3(1 — x) < 0 and then also to —oo. Thus, none of the points outside A will ever be mapped into A. This is an important property. It implies that whenever a point of A is mapped outside A this point will never return to A. Thus, this property is called the never-come-hackpiopeTty. It facilitates appreciably the analysis of the tent map. 

---