# zbMATH — the first resource for mathematics

Morse theory and evasiveness. (English) Zbl 1028.05110
Summary: J. Kahn, M. Saks and D. Sturtevant [Combinatorica 4, 297-306 (1984; Zbl 0577.05061)] have shown that if $$M$$ is a non-contractible subcomplex of a simplex $$S$$ then $$M$$ is evasive. In this paper we make this result quantitative, and show that the more non-contractible $$M$$ is, the more evasive $$M$$ is. Recall that $$M$$ is evasive if for every decision tree algorithm $$A$$ there is a face $$\sigma$$ of $$S$$ that requires that one examines all vertices of $$S$$ (in the order determined by $$A$$) before one is able to determine whether or not $$\sigma$$ lies in $$M$$. We call such faces evaders of $$A$$. $$M$$ is nonevasive if and only if there is a decision tree algorithm $$A$$ with no evaders. A main result of this paper is that for any decision tree algorithm $$A$$, there is a CW complex $$M'$$, homotopy equivalent to $$M$$, such that the number of cells in $$M'$$ is precisely $\frac 12 (\text{the number of evaders of} A)\pm 1,$ where the constant is $$+1$$ if the empty set $$\emptyset$$ is not an evader of $$A$$, and $$-1$$ otherwise. In particular, this implies that if there is a decision tree algorithm with no evaders, then $$M$$ is homotopy equivalent to a point. This is the theorem of J. Kahn, M. Saks and D. Sturtevant.
In fact, they showed that if $$M$$ is non-collapsible then $$M$$ is evasive, and we also present a quantitative version of this more precise statement.
The proofs use the discrete Morse theory developed by the author in [Adv. Math. 134, 90-145 (1998; Zbl 0896.57023)].

##### MSC:
 05C99 Graph theory 55U05 Abstract complexes in algebraic topology 57M15 Relations of low-dimensional topology with graph theory
##### Keywords:
Morse theory; evasiveness
Full Text: