Connected Components - Linear Decision Trees

Question

What does connected components mean in the context of non-graphs? Graphs have vertices and the vertices are connected by edges. Hence, you can build a spanning tree (for example) by systematically joining connected components (where connected components refer to connected subgraphs).

Previous discussion on this topic reveals that each connected component of a linear decision tree on some function F represents a particular region bounded by a set of half-planes and hyperplanes. For linear decision trees applied to the element uniqueness problem, we have 2 possible type of connected components (correct me if I'm wrong) - YES and NO components.

Apparently there is only 1 NO component, and at least n! YES components when for linear decision trees applied to the element uniqueness problem on a set of "n" distinct items. I can understand the number of YES components (simply permute all items), but I'm not sure why there's only 1 NO component.

Answer 1

Connected components are a concept of topology. Under the usual topology on $\mathbb{R}^n$, we say that two points $x,y \in S$ belong to the same connected component if there is a path from $x$ to $y$ which is entirely in $S$ (this is known as path-connectedness). This defines an equivalence relation on $S$, and a connected component of $S$ is an equivalence class of this relation. This generalizes the graphical definition which is more familiar to this audience.