Is the simplicical complex induced by a non-evasive decision tree always connected?

Question

I am reading Evasiveness of Graph Properties and Topological Fixed Point Theorems. The paper states a theorem:

Theorem 2.1. Let $V_0$ be a finite set. Let $$ h : \mathbf{G}(V_0) \to \{ 0, 1 \}$$ be a monotone-increasing function which is not evasive. If the complex $\Delta_h$ is not empty, then it is collapsible.

The simplicial complex $\Delta_h$ is the set of all nonempty subsets $E$ of the set $\{\{v,w\} \mid v,w \in V_0\}$ such that:

$$h((V_0, E)) = 0$$

My best attempt at summarizing the proof is:

1. Create the simplicial complex.
2. Impose a "lowest common ancestor" ordering on the leaves of the tree.
3. Each leaf has a parent and child face.
4. By popping each one off in order, the parent face is maximal, and the child face is a free face, so a collapse can happen.
5. Repeat until a single point.

How can we guarentee that such a process ends at a single point? What if the simplicial complex has two separate subcomponents? Then you will be left with more than one point! Can we conclude that the simplicial complex induced by the property $h$ is connected? Furthermore, the paper says there are $n = |V_0|$ collapses available. How is the number acheived?

Answer 1

I think that the claim that the last simplex in the sequence is $\Delta_n$ is just an accident of notation: the paper wants to use $n$ for $|V_0|$, and separately wanted something for the length of the sequence of collapses, and called them both $n$. In general, the number of collapses can be much larger than $n$.

We know that we will be left with a single point, because every face of $\Delta_h$ is eventually removed! Every face of $\Delta_h$ corresponds to a graph $G$ with $h(G)=0$, which is found at some bottom node of the decision tree; at some point, we will get to that node and collapse the faces there. (Except for the last node, which consists of $\{\{e\}, \varnothing\}$: at that step, $\Delta_{\text{last}}$ is a single point, and we're done.)

So in a sense, this proof is also a proof that if $h$ is non-evasive and monotone-increasing, then $\Delta_h$ must be connected. But if you like, I can give you a separate proof.

---

Suppose that $h$ is monotone-increasing and $\Delta_h$ is not connected. That means that there is a partition $E_1 \cup E_2$ of the edge set such that no $\sigma \in \Delta_h$ contains elements of $E_1$ and of $E_2$. (In other words, as soon as our graph $G$ contains $e_1 \in E_1$ and $e_2 \in E_2$, we know that $h(G)=1$.) We will show that $h$ must be evasive.

We slightly change the partition $E_1 \cup E_2$ into $E_1' \cup E_2' \cup E_*$, where $E_*$ consists of all $e$ such that, as soon as that edge is present in $G$, we know that $h(G)=1$. In other words, no $\sigma \in \Delta_h$ contains elements of $E_*$, even a point; but any point from $E_1'$ or $E_2'$ is in $\Delta_h$.

Then here is an answering strategy such that after $\binom{n}{2}-1$ questions, you will not be able to know whether the graph has the property $h$ or not:

• Whenever you ask about $e \in E_*$, I say NO.
• Whenever you ask about $e \in E_1' \cup E_2'$, I say NO, except:
• If you're on the last element of $E_1'$, and have not already exhausted $E_2'$, or if you're on the last element of $E_2'$, and have not already exhausted $E_1'$, I say YES. (In particular, I never say YES twice for this reason.)

After $\binom{n}{2}-1$ questions, you must have exhausted either $E_1'$ or $E_2'$, or both, so I've said YES exactly once. If I say NO to the $\binom{n}{2}^{\text{th}}$ question, then the graph $G$ only has a single edge in either $E_1'$ or $E_2'$, and we know $h(G) =0$. On the other hand:

• If the last question is about an element of $E_*$, and I say YES, then we know $h(G)=1$, because $h(G)=1$ whenever $G$ contains an edge in $E_*$.
• If the last question is about an element of $E_1'$, and I say YES, I've already said YES about an element of $E_2'$, and because $\Delta_h$ is disconnected, we know $h(G)=1$ in this case.
• If the last question is about an element of $E_2'$, and I say YES, I've already said YES about an element of $E_1'$, and because $\Delta_h$ is disconnected, we know $h(G)=1$ in this case.

So either way, you don't know $h(G)$ until the $\binom{n}{2}^{\text{th}}$ question, and therefore $h$ is evasive.