Acyclic matching

The next theorem is the crucial combinatorial fact pertaining to matchings in Hasse diagrams of posets. It characterizes acyclic matchings by means of linear extensions. 

Assume now that we are given an acyclic matching, and let us define L inductively. Let Q denote the set of elements that are already ordered in L. We start with Q = 0. Let W denote the set of minimal elements in P Q. At each step we have one of the following cases. 

An example of a linear extension derived from an acyclic matching by this procedure is shown in Figure 11.2. ... 

Theorem 11.4. ( Acyclic matchings via poset maps with small fibers)... 

For any poset map with small fibers P Q, the partial matching M[ip) is acyclic. Conversely, any acyclic matching on P can be represented as M (p) for some poset map with small fibers (p. 

On the other hand, by Theorem 11.2, for any acyclic matching on P there exists a linear extension L of P such that the elements a and u a) follow consecutively in L. Gluing a with u a) in this order yields a poset map with small fibers from P to a chain. ... 

Given an acyclic matching M, we say that a collapsing order 99 is a collapsing order for M if it satisfies M p) = M. The etymology of this terminology is fairly clear the chain Q gives us the order in which it is allowed to perform... 

It turns out that for any poset P and any acyclic matching on P, there exists a universal object a poset whose linear extensions enumerate all allowed collapsing orders. 

Fig. 11.4. A universal poset associated with an acyclic matching.

Beyond the encoding of all allowed collapsing orders as the set of linear extensions of the universal object U (P, M), viewing the posets with small fibers as the central notion of the combinatorial part of discrete Morse theory is also invaluable for the structural explanation of a standard way to construct acyclic matchings as unions of acyclic matchings on fibers of a poset map. 

The decomposition theorem 11.9, is often used as a rationale to construct an acyclic matching on a poset P in several steps first map P to some other poset Q, then construct acyclic matchings on the fibers of this map. By the observation above, these acyclic matchings will patch together to form an acyclic matching for the whole poset. See Figure 11.5 for an example. For future reference, we summarize this observation in the next theorem. 

Assume that p P Q is an order-preserving map, and assume that we have acyclic matchings on subposets p (g), for all q Q. Then the union of these matchings is itself an acyclic matching on P. 

Proof. The role of the base space here is played by the poset Q, and the fiber maps gq are given by the acyclic matchings on the subposets ip q). The decomposition theorem tells us that there exists a poset map from P to the total space of the corresponding poset fibration, and that the fibers of this map are the same as the fibers of the fiber maps Qq. Since the latter are given by acyclic matchings, we conclude that we have a poset map from P with small fibers that corresponds precisely to the patching of acyclic matchings on the subposets 95 (g), for q Q. ... 

Fig. 11.5. Acyclic matching composed of acyclic matchings on fibers.

Remark 11. If - The converse of Theorem 11.13(a) is clearly true in the following sense if Ac is a subcomplex of A and if there exists a sequence of collapses from Z to. 4c, then the matching on the cells of 4 4c induced by this sequence of collapses is acyclic. In particular, a polyhedral complex 4 is collapsible if and only if the poset 1F A) 6 allows a complete acyclic matching. 

Let us now define acyclic matchings on the preimages of C under the map ip. We split our argument into three cases. 

If n = 3fc + 1, then this preimage is a face poset with a cone with apex in n in particular, the pairing [Pg.193]

Finally, we describe an acyclic matching on the preimage (p cr) by considering three cases. 

If n = 3k, then we again have a face poset of the join of k copies of S°. Denote the sets of vertices of these k copies of S° by xi,yx, xk,yk -Consider the pairing u x, where i is the minimal index such that Vi cr. This is a well-defined acyclic matching with critical cells xi of dimension 0, and yi,..., yk of dimension k... 

By Theorem 11.10 it is now sufficient to construct acyclic matchings on the fibers

[Pg.196]

In the poset. F(Z (iT i)) U 0 this acyclic matching can be extended to have only the top-dimensional critical element, since the other one is matched with 0. When considered in Si, these maximal chains consist of n—2 elements hence they correspond to critical simplices of dimension n - 3 in A n ). Case 2. Let S = for tt (1)(2)... (n). The matching rule in this... 

Acyclic Matchings on Free Chain Complexes and the Morse Complex... 

Definition 11.23. Let (C, fi) be a free chain complex with a basis, and let A4 be an acyclic matching. The Morse complex... 

Assume that we have a free chain complex with a basis (C, Q), and an acyclic matching Ai. Then C decomposes as a direct sum of chain complexes 0 %, where T Atom (dim6). 

We remark that even if the chain complex C is infinite in both directions, one can still define the notions of the acyclic matching and of the Morse complex. Since each particular homology group is determined by a finite excerpt from C, we may still conclude that... 

Our main innovation in Section 11.1 is the equivalent reformulation of acyclic matchings in terms of poset maps with small fibers, as well as the introduction of the universal object connected to each acyclic matching. The patchwork theorem 11.10 is a standard tool, used previously by several authors. We think that the terminology of poset fibrations together with the decomposition theorem 11.9 give the patchworking particular clarity. 

Remark 12.f. As mentioned above discrete Morse theory is more powerful as a method than shellability. The rationale for this fact is provided by Theorem 12.3(1), saying that the complex A = A IJ j Into- is collapsible, coupled with the fact that a generalized simplicial complex is collapsible if and only if there exists an acyclic matching on the set of its simplices see Theorem 11.13(a) and Remark 11.14. 

---