12 Forman's discrete Morse theory

12.1 Functions using discrete Morse theory

12.1-1 SCCollapseGreedy

12.1-2 SCCollapseLex

12.1-3 SCCollapseRevLex

12.1-4 SCHasseDiagram

12.1-5 SCMorseEngstroem

12.1-6 SCMorseRandom

12.1-7 SCMorseRandomLex

12.1-8 SCMorseRandomRevLex

12.1-9 SCMorseSpec

12.1-10 SCMorseUST

12.1-11 SCSpanningTreeRandom

12.1-12 SCHomology

12.1-13 SCHomologyEx

12.1-14 SCIsSimplyConnected

12.1-15 SCIsSimplyConnectedEx

12.1-16 SCIsSphere

12.1-17 SCIsManifold

12.1-18 SCIsManifoldEx

12.1-1 SCCollapseGreedy

12.1-2 SCCollapseLex

12.1-3 SCCollapseRevLex

12.1-4 SCHasseDiagram

12.1-5 SCMorseEngstroem

12.1-6 SCMorseRandom

12.1-7 SCMorseRandomLex

12.1-8 SCMorseRandomRevLex

12.1-9 SCMorseSpec

12.1-10 SCMorseUST

12.1-11 SCSpanningTreeRandom

12.1-12 SCHomology

12.1-13 SCHomologyEx

12.1-14 SCIsSimplyConnected

12.1-15 SCIsSimplyConnectedEx

12.1-16 SCIsSphere

12.1-17 SCIsManifold

12.1-18 SCIsManifoldEx

In this chapter a framework is provided to use Forman's discrete Morse theory [For95] within **simpcomp**. See Section 2.6 for a brief introduction.

Note: this is not to be confused with Banchoff and Kühnel's theory of regular simplexwise linear functions which is described in Chapter 11.

`‣ SCCollapseGreedy` ( complex ) | ( method ) |

Returns: simplicial complex of type `SCSimplicialComplex`

upon success, `fail`

otherwise.

Employs a greedy collapsing algorithm to collapse the simplicial complex `complex`. See also `SCCollapseLex`

(12.1-2) and `SCCollapseRevLex`

(12.1-3).

gap> SCLib.SearchByName("T^2"){[1..6]}; [ [ 4, "T^2 (VT)" ], [ 5, "T^2 (VT)" ], [ 9, "T^2 (VT)" ], [ 10, "T^2 (VT)" ], [ 18, "T^2 (VT)" ], [ 20, "(T^2)#2" ] ] gap> torus:=SCLib.Load(last[1][1]);; gap> bdtorus:=SCDifference(torus,SC([torus.Facets[1]]));; gap> coll:=SCCollapseGreedy(bdtorus); [SimplicialComplex Properties known: Dim, FacetsEx, Name, Vertices. Name="collapsed version of T^2 (VT) \ unnamed complex 8" Dim=1 /SimplicialComplex] gap> coll.Facets; [ [ 1, 3 ], [ 1, 5 ], [ 2, 3 ], [ 2, 5 ], [ 3, 4 ], [ 3, 7 ], [ 4, 7 ] ] gap> sphere:=SCBdSimplex(4);; gap> bdsphere:=SCDifference(sphere,SC([sphere.Facets[1]]));; gap> coll:=SCCollapseGreedy(bdsphere); [SimplicialComplex Properties known: Dim, FVector, FacetsEx, IsPure, Name, NumFaces[], SkelExs[], Vertices. Name="collapsed version of S^3_5 \ unnamed complex 12" Dim=0 FVector=[ 1 ] IsPure=true /SimplicialComplex] gap> coll.Facets; [ [ 5 ] ]

`‣ SCCollapseLex` ( complex ) | ( method ) |

Returns: simplicial complex of type `SCSimplicialComplex`

upon success, `fail`

otherwise.

Employs a greedy collapsing algorithm in lexicographical order to collapse the simplicial complex `complex`. See also `SCCollapseGreedy`

(12.1-1) and `SCCollapseRevLex`

(12.1-3).

gap> s:=SCSurface(1,true);; gap> s:=SCDifference(s,SC([SCFacets(s)[1]]));; gap> coll:=SCCollapseGreedy(s); [SimplicialComplex Properties known: Dim, FacetsEx, Name, Vertices. Name="collapsed version of T^2 \ unnamed complex 18" Dim=1 /SimplicialComplex] gap> coll.Facets; [ [ 1, 3 ], [ 1, 5 ], [ 3, 6 ], [ 3, 7 ], [ 5, 6 ], [ 6, 7 ] ] gap> sphere:=SCBdSimplex(4);; gap> ball:=SCDifference(sphere,SC([sphere.Facets[1]]));; gap> coll:=SCCollapseLex(ball); [SimplicialComplex Properties known: Dim, FVector, FacetsEx, IsPure, Name, NumFaces[], SkelExs[], Vertices. Name="collapsed version of S^3_5 \ unnamed complex 22" Dim=0 FVector=[ 1 ] IsPure=true /SimplicialComplex] gap> coll.Facets; [ [ 5 ] ]

`‣ SCCollapseRevLex` ( complex ) | ( method ) |

Returns: simplicial complex of type `SCSimplicialComplex`

upon success, `fail`

otherwise.

Employs a greedy collapsing algorithm in reverse lexicographical order to collapse the simplicial complex `complex`. See also `SCCollapseGreedy`

(12.1-1) and `SCCollapseLex`

(12.1-2).

gap> s:=SCSurface(1,true);; gap> s:=SCDifference(s,SC([SCFacets(s)[1]]));; gap> coll:=SCCollapseGreedy(s); [SimplicialComplex Properties known: Dim, FacetsEx, Name, Vertices. Name="collapsed version of T^2 \ unnamed complex 28" Dim=1 /SimplicialComplex] gap> coll.Facets; [ [ 1, 3 ], [ 1, 6 ], [ 3, 6 ], [ 3, 7 ], [ 6, 7 ] ] gap> sphere:=SCBdSimplex(4);; gap> ball:=SCDifference(sphere,SC([sphere.Facets[1]]));; gap> coll:=SCCollapseRevLex(ball); [SimplicialComplex Properties known: Dim, FVector, FacetsEx, IsPure, Name, NumFaces[], SkelExs[], Vertices. Name="collapsed version of S^3_5 \ unnamed complex 32" Dim=0 FVector=[ 1 ] IsPure=true /SimplicialComplex] gap> coll.Facets; [ [ 1 ] ]

`‣ SCHasseDiagram` ( c ) | ( function ) |

Returns: two lists of lists upon success, `fail`

otherweise.

Computes the Hasse diagram of `SCSimplicialComplex`

object `c`. The Hasse diagram is returned as two sets of lists. The first set of lists contains the upward part of the Hasse diagram, the second set of lists contains the downward part of the Hasse diagram.

The i-th list of each set of lists represents the incidences between the (i-1)-faces and the i-faces. The faces are given by their indices of the face lattice.

gap> c:=SCBdSimplex(3);; gap> HD:=SCHasseDiagram(c); [ [ [ [ 1, 2, 3 ], [ 1, 4, 5 ], [ 2, 4, 6 ], [ 3, 5, 6 ] ], [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ], [ 1, 4 ], [ 2, 4 ], [ 3, 4 ] ] ], [ [ [ 2, 1 ], [ 3, 1 ], [ 4, 1 ], [ 3, 2 ], [ 4, 2 ], [ 4, 3 ] ], [ [ 4, 2, 1 ], [ 5, 3, 1 ], [ 6, 3, 2 ], [ 6, 5, 4 ] ] ] ]

`‣ SCMorseEngstroem` ( complex ) | ( function ) |

Returns: two lists of small integer lists upon success, `fail`

otherweise.

Builds a discrete Morse function following the Engstroem method by reducing the input complex to smaller complexes defined by minimal link and deletion operations. See [Eng09] for details.

gap> c:=SCBdSimplex(3);; gap> f:=SCMorseEngstroem(c); [ [ [ 2 ], [ 2, 3 ], [ 2, 4 ], [ 2 .. 4 ], [ ], [ 3 ], [ 4 ], [ 3, 4 ], [ 1, 3 ], [ 1, 3, 4 ], [ 1 ], [ 1, 4 ], [ 1, 2, 4 ], [ 1, 2 ], [ 1 .. 3 ] ], [ [ 2 ], [ 1 .. 3 ] ] ]

`‣ SCMorseRandom` ( complex ) | ( function ) |

Returns: two lists of small integer lists upon success, `fail`

otherweise.

Builds a discrete Morse function following Lutz and Benedetti's random discrete Morse theory approach: Faces are paired with free co-dimension one faces until now free faces remain. Then a critical face is removed at random. See [BL14a] for details.

gap> c:=SCBdSimplex(3);; gap> f:=SCMorseRandom(c);; gap> Size(f[2]); 2

`‣ SCMorseRandomLex` ( complex ) | ( function ) |

Returns: two lists of small integer lists upon success, `fail`

otherweise.

Builds a discrete Morse function following Adiprasito, Benedetti and Lutz' lexicographic random discrete Morse theory approach. See [BL14a], [BL14b] for details.

gap> c := SCSurface(3,true);; gap> f:=SCMorseRandomLex(c);; gap> Size(f[2]); 8

`‣ SCMorseRandomRevLex` ( complex ) | ( function ) |

Returns: two lists of small integer lists upon success, `fail`

otherweise.

Builds a discrete Morse function following Adiprasito, Benedetti and Lutz' reverse lexicographic random discrete Morse theory approach. See [BL14a], [BL14b] for details.

gap> c := SCSurface(5,false);; gap> f:=SCMorseRandomRevLex(c);; gap> Size(f[2]); 7

`‣ SCMorseSpec` ( complex, iter[, morsefunc] ) | ( function ) |

Returns: a list upon success, `fail`

otherweise.

Computes `iter` versions of a discrete Morse function of `complex` using a randomised method specified by `morsefunc` (default choice is `SCMorseRandom`

(12.1-6), other randomised methods available are `SCMorseRandomLex`

(12.1-7) `SCMorseRandomRevLex`

(12.1-8), and `SCMorseUST`

(12.1-10)). The result is referred to by the Morse spectrum of `complex` and is returned in form of a list containing all Morse vectors sorted by number of critical points together with the actual vector of critical points and how often they ocurred (see [BL14a] for details).

gap> c:=SCSeriesTorus(2);; gap> f:=SCMorseSpec(c,30); [ [ 4, [ 1, 2, 1 ], 30 ] ]

gap> c:=SCSeriesHomologySphere(2,3,5);; gap> f:=SCMorseSpec(c,30,SCMorseRandom); [ [ 6, [ 1, 2, 2, 1 ], 27 ], [ 8, [ 1, 3, 3, 1 ], 3 ] ] gap> f:=SCMorseSpec(c,30,SCMorseRandomLex); [ [ 6, [ 1, 2, 2, 1 ], 29 ], [ 8, [ 1, 3, 3, 1 ], 1 ] ] gap> f:=SCMorseSpec(c,30,SCMorseRandomRevLex); [ [ 6, [ 1, 2, 2, 1 ], 7 ], [ 8, [ 1, 3, 3, 1 ], 9 ], [ 8, [ 2, 3, 2, 1 ], 1 ], [ 10, [ 1, 4, 4, 1 ], 11 ], [ 12, [ 1, 5, 5, 1 ], 1 ], [ 14, [ 1, 6, 6, 1 ], 1 ] ] gap> f:=SCMorseSpec(c,30,SCMorseUST); [ [ 6, [ 1, 2, 2, 1 ], 18 ], [ 8, [ 1, 3, 3, 1 ], 8 ], [ 10, [ 1, 4, 4, 1 ], 3 ], [ 12, [ 1, 5, 5, 1 ], 1 ] ]

`‣ SCMorseUST` ( complex ) | ( function ) |

Returns: a random Morse function of a simplicial complex and a list of critical faces.

Builds a random Morse function by removing a uniformly sampled spanning tree from the dual 1-skeleton followed by a collapsing approach. `complex` needs to be a closed weak pseudomanifold for this to work. For details of the algorithm, see [PS15].

gap> c:=SCBdSimplex(3);; gap> f:=SCMorseUST(c);; gap> Size(f[2]); 2

`‣ SCSpanningTreeRandom` ( HD, top ) | ( function ) |

Returns: a list of edges upon success, `fail`

otherweise.

Computes a uniformly sampled spanning tree of the complex belonging to the Hasse diagram `HD` using Wilson's algorithm (see [Wil96]). If `top = true` the output is a spanning tree of the dual graph of the underlying complex. If `top = false` the output is a spanning tree of the primal graph (i.e., the 1-skeleton.

gap> c:=SCSurface(1,false);; gap> HD:=SCHasseDiagram(c);; gap> stTop:=SCSpanningTreeRandom(HD,true); [ 3, 10, 13, 8, 1, 15, 12, 6, 14 ] gap> stBot:=SCSpanningTreeRandom(HD,false); [ 10, 6, 9, 5, 13 ]

`‣ SCHomology` ( complex ) | ( method ) |

Returns: a list of pairs of the form `[ integer, list ]`

upon success

Computes the homology groups of a given simplicial complex `complex` using `SCMorseRandom`

(12.1-6) to obtain a Morse function and `SmithNormalFormIntegerMat`

. Use `SCHomologyEx`

(12.1-13) to use alternative methods to compute discrete Morse functions (such as `SCMorseEngstroem`

(12.1-5), or `SCMorseUST`

(12.1-10)) or the Smith normal form.

The output is a list of homology groups of the form [H_0,....,H_d], where d is the dimension of `complex`. The format of the homology groups H_i is given in terms of their maximal cyclic subgroups, i.e. a homology group H_i≅ Z^f + Z / t_1 Z × dots × Z / t_n Z is returned in form of a list [ f, [t_1,...,t_n] ], where f is the (integer) free part of H_i and t_i denotes the torsion parts of H_i ordered in weakly increasing size.

gap> c:=SCSeriesTorus(2);; gap> f:=SCHomology(c); [ [ 0, [ ] ], [ 2, [ ] ], [ 1, [ ] ] ]

`‣ SCHomologyEx` ( c, morsechoice, smithchoice ) | ( method ) |

Returns: a list of pairs of the form `[ integer, list ]`

upon success, fail otherwise.

Computes the homology groups of a given simplicial complex `c` using the function `morsechoice` for discrete Morse function computations and `smithchoice` for Smith normal form computations.

The output is a list of homology groups of the form [H_0,....,H_d], where d is the dimension of `complex`. The format of the homology groups H_i is given in terms of their maximal cyclic subgroups, i.e. a homology group H_i≅ Z^f + Z / t_1 Z × dots × Z / t_n Z is returned in form of a list [ f, [t_1,...,t_n] ], where f is the (integer) free part of H_i and t_i denotes the torsion parts of H_i ordered in weakly increasing size.

gap> c:=SCSeriesTorus(2);; gap> f:=SCHomology(c); [ [ 0, [ ] ], [ 2, [ ] ], [ 1, [ ] ] ]

gap> c := SCSeriesHomologySphere(2,3,5);; gap> SCHomologyEx(c,SCMorseRandom,SmithNormalFormIntegerMat); time; [ [ 0, [ ] ], [ 0, [ ] ], [ 0, [ ] ], [ 1, [ ] ] ] 60 gap> c := SCSeriesHomologySphere(2,3,5);; gap> SCHomologyEx(c,SCMorseRandomLex,SmithNormalFormIntegerMat); time; [ [ 0, [ ] ], [ 0, [ ] ], [ 0, [ ] ], [ 1, [ ] ] ] 56 gap> c := SCSeriesHomologySphere(2,3,5);; gap> SCHomologyEx(c,SCMorseRandomRevLex,SmithNormalFormIntegerMat); time; [ [ 0, [ ] ], [ 0, [ ] ], [ 0, [ ] ], [ 1, [ ] ] ] 56 gap> c := SCSeriesHomologySphere(2,3,5);; gap> SCHomologyEx(c,SCMorseEngstroem,SmithNormalFormIntegerMat); time; [ [ 0, [ ] ], [ 0, [ ] ], [ 0, [ ] ], [ 1, [ ] ] ] 100 gap> c := SCSeriesHomologySphere(2,3,5);; gap> SCHomologyEx(c,SCMorseUST,SmithNormalFormIntegerMat); time; [ [ 0, [ ] ], [ 0, [ ] ], [ 0, [ ] ], [ 1, [ ] ] ] 136

`‣ SCIsSimplyConnected` ( c ) | ( function ) |

Returns: a boolean value upon success, `fail`

otherweise.

Computes if the `SCSimplicialComplex`

object `c` is simply connected. The algorithm is a heuristic method and is described in [PS15]. Internally calls `SCIsSimplyConnectedEx`

(12.1-15).

gap> rp2:=SCSurface(1,false);; gap> SCIsSimplyConnected(rp2); false gap> c:=SCBdCyclicPolytope(8,18);; gap> SCIsSimplyConnected(c); true

`‣ SCIsSimplyConnectedEx` ( c[, top, tries] ) | ( function ) |

Returns: a boolean value upon success, `fail`

otherweise.

Computes if the `SCSimplicialComplex`

object `c` is simply connected. The optional boolean argument `top` determines whether a spanning graph in the dual or the primal graph of `c` will be used for a collapsing sequence. The optional positive integer argument `tries` determines the number of times the algorithm will try to find a collapsing sequence. The algorithm is a heuristic method and is described in [PS15].

gap> rp2:=SCSurface(1,false);; gap> SCIsSimplyConnectedEx(rp2); false gap> c:=SCBdCyclicPolytope(8,18);; gap> SCIsSimplyConnectedEx(c); true

`‣ SCIsSphere` ( c ) | ( function ) |

Returns: a boolean value upon success, `fail`

otherweise.

Determines whether the `SCSimplicialComplex`

object `c` is a topological sphere. In dimension ≠ 4 the algorithm determines whether `c` is PL-homeomorphic to the standard sphere. In dimension 4 the PL type is not specified. The algorithm uses a result due to [KS77] stating that, in dimension ≠ 4, any simply connected homology sphere with PL structure is a standard PL sphere. The function calls `SCIsSimplyConnected`

(12.1-14) which uses a heuristic method described in [PS15].

gap> c:=SCBdCyclicPolytope(4,20);; gap> SCIsSphere(c); true gap> c:=SCSurface(1,true);; gap> SCIsSphere(c); false

`‣ SCIsManifold` ( c ) | ( function ) |

Returns: a boolean value upon success, `fail`

otherweise.

The algorithm is a heuristic method and is described in [PS15] in more detail. Internally calls `SCIsManifoldEx`

(12.1-18).

gap> c:=SCBdCyclicPolytope(4,20);; gap> SCIsManifold(c); true

`‣ SCIsManifoldEx` ( c[, aut, quasi] ) | ( function ) |

Returns: a boolean value upon success, `fail`

otherweise.

If the boolean argument `aut` is `true`

the automorphism group is computed and only one link per orbit is checked to be a sphere. If `aut` is not provided symmetry information is only used if the automorphism group is already known. If the boolean argument `quasi` is `false`

the algorithm returns whether or not `c` is a combinatorial manifold. If `quasi` is `true`

the 4-dimensional links are not verified to be standard PL 4-spheres and `c` is a combinatorial manifold modulo the smooth Poincare conjecture. By default `quasi` is set to `false`

. The algorithm is a heuristic method and is described in [PS15] in more detail.

See `SCBistellarIsManifold`

(9.2-6) for an alternative method for manifold verification.

gap> c:=SCBdCyclicPolytope(4,20);; gap> SCIsManifold(c); true

generated by GAPDoc2HTML