id: 01604309
dt: j
an: 01604309
au: Forman, Robin
ti: Morse theory and evasiveness.
so: Combinatorica 20, No.4, 489-504 (2000).
py: 2000
pu: János Bolyai Mathematical Society, Budapest; Springer-Verlag, Berlin
la: EN
cc: 
ut: Morse theory; evasiveness
ci: Zbl 0577.05061; Zbl 0896.57023
li: doi:10.1007/s004930070003
ab: Summary: {\it J. Kahn, M. Saks} and {\it 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 $σ$
    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
    $σ$ 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)].
rv: