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
Obviously, $K'$ is ordered by inclusion of simplices, so there is a map $\varphi_{K'}:K_R''\rightarrow K_R'$, and then we get 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_K \varphi_{K'}$ is homotopic to the identity map on $K_R$ after realisation, i.e., this proves the following modulo the proof of the proposition (see addendum below):
$|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.
Addendum. In the current form, it is difficult to see why $\bar\psi' \psi$ should be homotopic to the identity on $|L_R|$. Notice that this is a necessary step in proving the homotopy equivalence between $|K_R|$ and $|L_R|$. The purpose of this addendum is to make a slightly different claim which yields a homotopy equivalence between $|K_R|$ and $|L_R|$.
From above, observe that we have maps $\bar\psi \varphi_{K'}:K_R'' \rightarrow L_R$ and $\varphi_L \bar\psi' : K_R'' \rightarrow L_R$. Dowker proves the following:
The two maps $\bar\psi \varphi_{K'}$ and $\varphi_L \bar\psi'$ are contiguous.
Thus upon passing to the geometric realization, we get that the realizations of the maps are homotopic, i.e. $|\bar\psi| \simeq |\bar\psi'|$. Notice that we are using the fact that $|\varphi_{K'}|$ and $|\varphi_L|$ are homotopic to the respective identity maps.
Thus we obtain $|\psi||\bar\psi'| \simeq |\psi||\bar\psi|$, and in particular, the latter composition is homotopic to the identity on $|K_R|$.
By symmetric arguments, we obtain the following results:
Passing to the geometric realization, we get that $|\bar\psi| |\psi'|$ is homotopic to the identity on $|L_R|$, and also that $|\psi'|\simeq |\psi|$. Thus we see that $|\bar\psi||\psi|$ is homotopic to the identity on $|L_R|$. It follows that $|\psi|: |L_R| \rightarrow |K_R|$ is a homotopy equivalence, with $|\bar\psi|$ as its homotopy inverse.