Here (specifically in Lemma 4.18) is ``where the miracle of algebraic topology occurs". Through Lemma 4.18 many Lefschetz numbers become computable and thus a host of combinatorially surprising fixed point theorems (many of which still have no combinatorial proof) enters the theory.

**Proof:**
First note that and
, since for
we have

while for there is an with and thus

Now since and (with being the isomorphism) we have

Adding the two equations, multiplying with
and summing over *q* gives the
equality of the Lefschetz numbers and the equality
of the Euler characteristics follows from
. \

**Proof:**
The generators for are the differences
*v*-*w*, where *v*,*w* are vertices of *K* with .
Thus if *u*,*z* are vertices in the same component of *K*, then
.
On the other hand if , then *u*-*z* must the the sum
of finitely many generators of and thus *u* and
*z* must be in
the same component of *K*.

Since , the vertex set of *K*, this implies
that any two vertices *x*,*y* in the same component of *K*
satisfy , while if
*x*' and *y*' are not in the same component of
*K* we have .
Hence has exactly *k* generators with no further
conditions to be satisfied, i.e., it is isomorphic to
. \

In particular this means that if *K* is connected, then
is isomorphic to .
If this is the only interesting homology group of *K*, we
will say that *K* is acyclic.

Clearly a simplicial complex is the clique complex of a graph iff it satisfies the clique condition (cf. [46], Proposition 4.4, or originally [125], Gikas also investigates the Euler characteristic of the chain complex of an ordered set in [46], Chapter 4).

**Proof:**
First note that if is a simplex
of *K* that does not contain *x*, then
.
On the other hand no nonzero sum of orientations of
simplexes that all contain *x* can ever be in .
Thus the cosets of the orientations of the simplexes that contain *x*
are a set of generators for with
no equations beyond
for being an odd permutation
to be satisfied.

Let . If
is a simplex that contains
*x*, we can find a representative
of
such that
.
Since any two such representatives only differ by an even permutation
of the indices up to *q*-1
we have that is a well-defined map
from the
set of orientations of simplexes that contain *x* to .
Since the orientations of simplexes
that contain *x* are a system of representatives for
the generators of and their inverses and since

extends in a natural fashion to a homomorphism
from to , which we will
also call .
For *q*=1, we let ,
and extend this in the natural fashion
to a homomorphism.
Surjectivity of follows from the clique condition and
if

then , which implies that

Thus is an isomorphism
(for *q*=1 this is trivial).
To see the equation
for
consider:

For the statement for the homology groups is now trivial.
For *q*=0 note that is the whole
group (which is generated by
) in case there is a such that
and that if not.
For *q*=1
note that
the generators of
are the set
while the generators of
are the set
Thus any difference
with *a*,*c* in the same component
of is in and no difference
with *a*,*d* in different components of
is in .
If is connected, then
clearly and
.
If is not connected,
let be the components of and let
be a vertex of .
Then the generators
( )
are mutually
distinct and there are no equations between them to be
satisfied. Moreover all other elements of are
sums of these generators and their inverses.
This proves the claim.
\

Theorem 4.25, which is an easy consequence of Lemmas 4.22 and 4.24, provides an algorithm to compute the homology of collapsible ordered sets. These are defined as follows.

Obviously (connected) collapsibility is a generalization of dismantlability. However while dismantlability of an ordered set can be determined in polynomial time, it is not clear if the same can be said for (connected) collapsibility (cf. open question 3). Connected collapsibility also gives some insight in the structure of the sets of fixed points of order-preserving maps (cf. Theorem 5.6). The definition of connectedly collapsible graphs is analogous and we can record:

**Proof:**
Let *G*=(*V*,*E*) be a connectedly collapsible
graph.
We prove the statement by induction on *n*=|*V*|.
For *n*=1 there is nothing to prove.
Now suppose and the result holds for all
graphs with .
Let *G*=(*V*,*E*) be a graph with |*V*|=*n*. Then
by the definition of connected collapsibility
there is an such that is a retract of
*V*, is connectedly collapsible and
is connectedly collapsible.
Then is not an empty graph (since the empty graph is not
connectedly collapsible). Thus
since both and have
at most *n*-1 vertices both are acyclic.
Thus by Theorem 4.25 *G* is acyclic.
\

**Proof:** Dismantlability implies connected collapsibility.
\

**Proof:**
``2 3" follows from
Theorem 4.27.
``3 1"
follows from Lemma 4.21.
Finally for ``1 2"
suppose *P* is collapsible and not connectedly collapsible.
We will prove by induction on *n*:=|*P*|
that *P* does not have the fixed point property.
For *n*=1 there is nothing to prove.
Suppose now *n*>1 and the result holds for all ordered sets
*Q* with
|*Q*|<*n*. Then there is a retractable point such that
is collapsible and not connectedly collapsible
or
is
collapsible and not
not connectedly collapsible. By induction hypothesis
this would mean that
does not have the fixed point property
or
does not have the fixed point property or it is empty
(in which case it also does not have the fixed point property).
This implies by Theorem 3.4 that *P* does not have the
fixed point property. \

Again clearly a similar result can be proved relating collapsibility of graphs to acyclicity and the fixed clique property.

**Figure 3:** Figures to illustrate example 4.30.

It is finally worth recording that (obviously) since the homology of an ordered set and the associated complexes are defined through the comparability graph they all are comparability invariants and thus only useful in the study of other comparability invariants.