The purpose of this entry is simply to state and prove a result of Dowker that was mentioned at Vietoris complex. Here we will look at a version of Dowker’s original proof. In later sections we will see other ways of proving it. We will also discuss some of the interpretations and applications of the result and ask about possible generalisations.
To keep the discussion fairly self contained, certain ideas will be repeated from that, and possibly other, entries.
Let $X, Y$ be sets and $R$ a relation between $X$ and $Y$, so $R \subseteq X \times Y$. We write $x R y$ for $(x, y) \in R$.
(In addition to those given in Vietoris complex.)
If $K$ is a simplicial complex, its structure is specified by a collection of non-empty finite subsets of its set of vertices namely those sets of vertices declared to be simplices. This collection of simplices is supposed to be downward closed, i.e., if $\sigma$ is a simplex and $\tau \subseteq \sigma$ with $\tau \neq \emptyset$, then $\tau$ is a simplex. For our purposes here, set $X = V_K$ to be the set of vertices of $K$ and $Y = S_K$, the set of simplices of $K$ with $x R y$ if $x$ is a vertex of the simplex $y$.
Returning to the general situation, we define two simplicial complexes associated to $R$, as follows:
$K = K_R:$
$L = L_R :$
Clearly the two constructions are in some sense dual to each other.
These two simplicial complexes were denoted $V(R)$ and $C(R)$ at Vietoris complex.
We next need some classical subdivision ideas.
Combinatorially, if $K$ is a simplicial complex with vertex set $V_K$, then one associates to $K$ the partially ordered set of its simplices. Explicitly we write $S_K$ for the set of simplices of $K$ and $(S_K, \subseteq)$ for the partially ordered set with $\subseteq$ being the obvious inclusion. The barycentric subdivision, $K'$, of $K$ has $S_K$ as its set of vertices and a finite set of vertices of $K'$ (i.e. simplices of $K$) is a simplex of $K'$ if it can be totally ordered by inclusion. (Thus $K'$ is the simplicial complex given by taking the nerve of the poset, $(S_K, \subseteq)$.)
It is important to note that there is in general no natural simplicial map from $K'$ to $K$. If however $V_K$ is ordered in such a way that the vertices of any simplex in $K$ are totally ordered (for instance by picking a total order on $V_K$), then one can easily specify a map
by:
This preserves simplices, but reverses order so if $\sigma_1' \subset \sigma_2'$ then $\varphi (\sigma_1') \geq \varphi(\sigma_2')$.
If one changes the order, then the resulting map is contiguous:
Let $\varphi,~ \psi : K \rightarrow L$ be two simplicial maps between simplicial complexes. They are contiguous if for any simplex $\sigma$ of $K$, $\varphi (\sigma) \cup \psi (\sigma)$ forms a simplex in $L$.
Contiguity gives a constructive form of homotopy applicable to simplicial maps.
If $\psi : K \rightarrow L$ is a simplicial map, then it induces $\psi' : K' \rightarrow L'$ after subdivision. As there is no way of knowing / picking compatible orders on $V_K$ and $V_L$ in advance, we get that on constructing
and
that $\varphi_L \psi'$ and $\psi \varphi_K$ will be contiguous to each other but rarely equal.
Returning to $K_R$ and $L_R$, we order the elements of $X$ and $Y$. Then suppose $y'$ is a vertex of $L'_R$, so $y' = \{y_0, \cdots, y_p\}$, a simplex of $L_R$ and there is an element $x \in X$ with $x R y_i, i = 0, 1, \cdots, p$. Set $\psi y' = x$ for one such $x$.
If $\sigma = \{ y'_0, \cdots, y'_q\}$ is a $q$-simplex of $L'_R$, assume $y'_0$ is its least vertex (in the inclusion ordering)
hence $\psi y'_i R \varphi_L (y'_0)$ and the elements $\psi y'_0, \cdots, \psi y'_q$ form a simplex in $K_R$, so $\psi : L'_R \rightarrow K_R$ is a simplicial map. It, of course, depends on the ordering used and on the choice of $x$, but any other choice $\bar x$ for $\psi y'$ gives a contiguous map.
Reversing the roles of $X$ and $Y$ in the above we get a simplicial map
Applying barycentric subdivisions again gives
and composing with $\psi : L_R' \rightarrow K_R$ gives a map
Of course, there is also a map
The two maps $\varphi_K \varphi'_K$ and $\psi \bar\psi'$ are contiguous.
Before proving this, note that contiguity implies homotopy and that $\varphi \varphi'$ is homotopic to the identity map on $K_R$ after realisation, i.e., this proves the following modulo the proof of the proposition:
$|K_R| \simeq |L_R|.$
The homotopy depends on the ordering of the vertices and so is not natural.
Let $\sigma''' = \{ x_0'', x_1'', \cdots, x_q''\}$ be a simplex of $K_R''$ and as usual assume $x_0''$ is its least vertex, then for all $i \gt 0$
We have that $\varphi'_K$ is clearly order reversing so $\varphi'_K x_i'' \subseteq \varphi'_K x_0''$. Let $y = \bar\varphi \varphi'_K x_0''$, then for each $x \in \varphi'_K x_0''$, $x Ry$. Since $\varphi_K \varphi'_K x_i'' \in \varphi'_K x_i'' \subseteq \varphi'_K x_0''$, we have $\varphi_K \varphi'_K x_i'' R y$.
For each vertex $x'$ of $x_i'', \bar \psi x' \in \bar \psi' x_i''$, hence as $\varphi'_K x_0'' \in x_0'' \subset x_i'', y = \bar \psi \varphi'_K xx_0'' \in \bar \psi' x_i''$ for each $x_i ''$, so for each $x_i'', \psi \bar \psi' x_i'' R y$, however we therefore have
forms a simplex in $K_R$, i.e. $\varphi_K \varphi'_K$ and $\psi \bar \psi'$ are contiguous.