next up previous contents index
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 tex2html_wrap_inline10310 and tex2html_wrap_inline10312 , since for tex2html_wrap_inline10314 we have


while for tex2html_wrap_inline10318 there is an tex2html_wrap_inline10320 with tex2html_wrap_inline10322 and thus


Now since tex2html_wrap_inline10326 and tex2html_wrap_inline10328 (with tex2html_wrap_inline10330 being the isomorphism) we have


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


Proof: The generators for tex2html_wrap_inline10348 are the differences v-w, where v,w are vertices of K with tex2html_wrap_inline10356 . Thus if u,z are vertices in the same component of K, then tex2html_wrap_inline10362 . On the other hand if tex2html_wrap_inline10362 , then u-z must the the sum of finitely many generators of tex2html_wrap_inline10348 and thus u and z must be in the same component of K.
Since tex2html_wrap_inline10376 , the vertex set of K, this implies that any two vertices x,y in the same component of K satisfy tex2html_wrap_inline10384 , while if x' and y' are not in the same component of K we have tex2html_wrap_inline10392 . Hence tex2html_wrap_inline10394 has exactly k generators with no further conditions to be satisfied, i.e., it is isomorphic to tex2html_wrap_inline10398 . \

In particular this means that if K is connected, then tex2html_wrap_inline10394 is isomorphic to tex2html_wrap_inline10404 . 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 tex2html_wrap_inline10534 is a simplex of K that does not contain x, then tex2html_wrap_inline10540 . On the other hand no nonzero sum of orientations of simplexes that all contain x can ever be in tex2html_wrap_inline10544 . Thus the cosets of the orientations of the simplexes that contain x are a set of generators for tex2html_wrap_inline10548 with no equations beyond tex2html_wrap_inline10550 for tex2html_wrap_inline10552 being an odd permutation to be satisfied.
Let tex2html_wrap_inline10554 . If tex2html_wrap_inline10556 is a simplex that contains x, we can find a representative tex2html_wrap_inline10560 of tex2html_wrap_inline10562 such that tex2html_wrap_inline10564 . Since any two such representatives only differ by an even permutation of the indices up to q-1 we have that tex2html_wrap_inline10568 is a well-defined map from the set of orientations of simplexes that contain x to tex2html_wrap_inline10572 . Since the orientations of simplexes that contain x are a system of representatives for the generators of tex2html_wrap_inline10548 and their inverses and since


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


then tex2html_wrap_inline10596 , which implies that


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


For tex2html_wrap_inline10554 the statement for the homology groups is now trivial. For q=0 note that tex2html_wrap_inline10612 is the whole group tex2html_wrap_inline10614 (which is generated by tex2html_wrap_inline10616 ) in case there is a tex2html_wrap_inline8324 such that tex2html_wrap_inline10620 and that tex2html_wrap_inline10622 if not. For q=1 note that the generators of tex2html_wrap_inline10626 are the set tex2html_wrap_inline10628 while the generators of tex2html_wrap_inline10630 are the set tex2html_wrap_inline10632 Thus any difference tex2html_wrap_inline10634 with a,c in the same component of tex2html_wrap_inline10638 is in tex2html_wrap_inline10626 and no difference tex2html_wrap_inline10642 with a,d in different components of tex2html_wrap_inline10638 is in tex2html_wrap_inline10626 . If tex2html_wrap_inline10638 is connected, then clearly tex2html_wrap_inline10652 and tex2html_wrap_inline10654 . If tex2html_wrap_inline10638 is not connected, let tex2html_wrap_inline10658 be the components of tex2html_wrap_inline10638 and let tex2html_wrap_inline10662 be a vertex of tex2html_wrap_inline10664 . Then the generators tex2html_wrap_inline10666 ( tex2html_wrap_inline10668 ) are mutually distinct and there are no equations between them to be satisfied. Moreover all other elements of tex2html_wrap_inline10670 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 tex2html_wrap_inline10706 and the result holds for all graphs with tex2html_wrap_inline10708 . Let G=(V,E) be a graph with |V|=n. Then by the definition of connected collapsibility there is an tex2html_wrap_inline9756 such that tex2html_wrap_inline10716 is a retract of V, tex2html_wrap_inline10720 is connectedly collapsible and tex2html_wrap_inline10722 is connectedly collapsible. Then tex2html_wrap_inline10724 is not an empty graph (since the empty graph is not connectedly collapsible). Thus since both tex2html_wrap_inline10720 and tex2html_wrap_inline10724 have at most n-1 vertices both are acyclic. Thus by Theorem 4.25 G is acyclic. \


Proof: Dismantlability implies connected collapsibility. \


Proof: ``2 tex2html_wrap_inline8128 3" follows from Theorem 4.27. ``3 tex2html_wrap_inline8128 1" follows from Lemma 4.21. Finally for ``1 tex2html_wrap_inline8128 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 tex2html_wrap_inline10762 such that tex2html_wrap_inline10764 is collapsible and not connectedly collapsible or tex2html_wrap_inline10766 is collapsible and not not connectedly collapsible. By induction hypothesis this would mean that tex2html_wrap_inline10764 does not have the fixed point property or tex2html_wrap_inline10766 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 up previous contents index
Next: Topological Considerations Up: Order vs. Algebraic Topology Previous: The Lefschetz Number