nLab
Dowker's theorem

Dowker's Theorem

Note

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.

The two nerves of a relation: Dowker’s construction

Let X,YX, Y be sets and RR a relation between XX and YY, so RX×YR \subseteq X \times Y. We write xRyx R y for (x,y)R(x, y) \in R.

Example

(In addition to those given in Vietoris complex.)

If KK 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 KX = V_K to be the set of vertices of KK and Y=S KY = S_K, the set of simplices of KK with xRyx R y if xx is a vertex of the simplex yy.

Returning to the general situation, we define two simplicial complexes associated to RR, as follows:

  1. K=K R:K = K_R:

    • the set of vertices is the set XX;
    • a pp-simplex of KK is a set {x 0,,x p}X\{x_0, \cdots, x_p\}\subseteq X such that there is some yYy \in Y with x iRyx_i R y for i=0,1,,pi = 0, 1, \cdots, p.
  2. L=L R:L = L_R :

    • the set of vertices is the set, YY;
    • pp-simplex of KK is a set {y 0,,y p}Y\{y_0, \cdots, y_p\}\subseteq Y such that there is some xXx \in X with xRy jx R y_j for j=0,1,,pj = 0, 1, \cdots, p.

Clearly the two constructions are in some sense dual to each other.

Note

These two simplicial complexes were denoted V(R)V(R) and C(R)C(R) at Vietoris complex.

We next need some classical subdivision ideas.

Barycentric subdivisions

Combinatorially, if KK is a simplicial complex with vertex set V KV_K, then one associates to KK the partially ordered set of its simplices. Explicitly we write S KS_K for the set of simplices of KK and (S K,)(S_K, \subseteq) for the partially ordered set with \subseteq being the obvious inclusion. The barycentric subdivision, KK', of KK has S KS_K as its set of vertices and a finite set of vertices of KK' (i.e. simplices of KK) is a simplex of KK' if it can be totally ordered by inclusion. (Thus KK' is the simplicial complex given by taking the nerve of the poset, (S K,)(S_K, \subseteq).)

Note

It is important to note that there is in general no natural simplicial map from KK' to KK. If however V KV_K is ordered in such a way that the vertices of any simplex in KK are totally ordered (for instance by picking a total order on V KV_K), then one can easily specify a map

φ:KK \varphi : K' \rightarrow K

by:

  • if σ={x 0,,x p}\sigma' = \{ x_0, \cdots, x_p\} is a vertex of KK' (so σS K\sigma' \in S_K), let φσ\varphi \sigma' be the least vertex of σ\sigma' in the given fixed order.

This preserves simplices, but reverses order so if σ 1σ 2\sigma_1' \subset \sigma_2' then φ(σ 1)φ(σ 2)\varphi (\sigma_1') \geq \varphi(\sigma_2').

If one changes the order, then the resulting map is contiguous:

Contiguity

Let φ,~ψ:KL\varphi,~ \psi : K \rightarrow L be two simplicial maps between simplicial complexes. They are contiguous if for any simplex σ\sigma of KK, φ(σ)ψ(σ)\varphi (\sigma) \cup \psi (\sigma) forms a simplex in LL.

Contiguity gives a constructive form of homotopy applicable to simplicial maps.

If ψ:KL\psi : K \rightarrow L is a simplicial map, then it induces ψ:KL\psi' : K' \rightarrow L' after subdivision. As there is no way of knowing / picking compatible orders on V KV_K and V LV_L in advance, we get that on constructing

φ K:KK\varphi_K : K' \rightarrow K

and

φ L:LL\varphi_L : L' \rightarrow L

that φ Lψ\varphi_L \psi' and ψφ K\psi \varphi_K will be contiguous to each other but rarely equal.

Returning to K RK_R and L RL_R, we order the elements of XX and YY. Then suppose yy' is a vertex of L RL'_R, so y={y 0,,y p}y' = \{y_0, \cdots, y_p\}, a simplex of L RL_R and there is an element xXx \in X with xRy i,i=0,1,,px R y_i, i = 0, 1, \cdots, p. Set ψy=x\psi y' = x for one such xx.

If σ={y 0,,y q}\sigma = \{ y'_0, \cdots, y'_q\} is a qq-simplex of L RL'_R, assume y 0y'_0 is its least vertex (in the inclusion ordering)

φ L(y 0 )y 0y foreachy iσ\varphi_L (y^\prime_0) \in y'_0 \subset y^\prime for each y_i \in \sigma

hence ψy iRφ L(y 0)\psi y'_i R \varphi_L (y'_0) and the elements ψy 0,,ψy q\psi y'_0, \cdots, \psi y'_q form a simplex in K RK_R, so ψ:L RK R\psi : L'_R \rightarrow K_R is a simplicial map. It, of course, depends on the ordering used and on the choice of xx, but any other choice x¯\bar x for ψy\psi y' gives a contiguous map.

Reversing the roles of XX and YY in the above we get a simplicial map

ψ¯:K RL R.\bar\psi : K_R' \rightarrow L_R.

Applying barycentric subdivisions again gives

ψ¯:K RL R\bar\psi' : K_R'' \rightarrow L_R'

and composing with ψ:L RK R\psi : L_R' \rightarrow K_R gives a map

ψψ¯:K RK R.\psi \bar\psi' : K_R'' \rightarrow K_R.

Of course, there is also a map

φ Kφ K:K RK R.\varphi_K \varphi'_K : K_R''\rightarrow K_R.
Proposition (Dowker, 1952, p. 88)

The two maps φ Kφ K\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 RK_R after realisation, i.e., this proves the following modulo the proof of the proposition:

Dowker’s Theorem

|K R||L R|.|K_R| \simeq |L_R|.

The homotopy depends on the ordering of the vertices and so is not natural.

Proof of Proposition

Let σ={x 0,x 1,,x q}\sigma''' = \{ x_0'', x_1'', \cdots, x_q''\} be a simplex of K RK_R'' and as usual assume x 0x_0'' is its least vertex, then for all i>0i \gt 0

x 0x i.x_0'' \subset x_i''.

We have that φ K\varphi'_K is clearly order reversing so φ Kx iφ Kx 0\varphi'_K x_i'' \subseteq \varphi'_K x_0''. Let y=φ¯φ Kx 0y = \bar\varphi \varphi'_K x_0'', then for each xφ Kx 0x \in \varphi'_K x_0'', xRyx Ry. Since φ Kφ Kx iφ Kx iφ Kx 0\varphi_K \varphi'_K x_i'' \in \varphi'_K x_i'' \subseteq \varphi'_K x_0'', we have φ Kφ Kx iRy\varphi_K \varphi'_K x_i'' R y.

For each vertex xx' of x i,ψ¯xψ¯x ix_i'', \bar \psi x' \in \bar \psi' x_i'', hence as φ Kx 0x 0x i,y=ψ¯φ Kxx 0ψ¯x i\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 ix_i '', so for each x i,ψψ¯x iRyx_i'', \psi \bar \psi' x_i'' R y, however we therefore have

φ kφ K(σ)ψψ¯(σ)=φ kφ K(x i)ψψ¯;x i \varphi_k \varphi'_K (\sigma '') \cup \psi \bar \psi (\sigma''') = \bigcup \varphi_k \varphi'_K (x_i'')\cup \psi \bar \psi; x_i ''

forms a simplex in K RK_R, i.e. φ Kφ K\varphi_K \varphi'_K and ψψ¯\psi \bar \psi' are contiguous.

References

  • C. H. Dowker, Homology Groups of Relations, Annals of Maths, 56, (1952), 84–95.

Revised on February 18, 2013 19:57:45 by Toby Bartels (64.89.53.62)