Next: Topological Considerations Up: Order vs. Algebraic Topology Previous: The Lefschetz Number

## (Integer) Homology

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.

Next: Topological Considerations Up: Order vs. Algebraic Topology Previous: The Lefschetz Number

Bernd.S.W.Schroder