×

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
PDF BibTeX XML Cite
Full Text: DOI