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)" ],
[ 17, "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: collapsed version of T^2 (VT) \ unnamed complex 8 | dim = \
1 | n = 4>
gap> coll.Facets;
[ [ 2, 5 ], [ 2, 6 ], [ 2, 7 ], [ 5, 6 ], [ 5, 7 ] ]
gap> sphere:=SCBdSimplex(4);;
gap> bdsphere:=SCDifference(sphere,SC([sphere.Facets[1]]));;
gap> coll:=SCCollapseGreedy(bdsphere);
<SimplicialComplex: collapsed version of S^3_5 \ unnamed complex 12 | dim = 0 \
| n = 1>
gap> coll.Facets;
[ [ 2 ] ]
‣ 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: collapsed version of T^2 \ unnamed complex 18 | dim = 1 | \ n = 5> gap> coll.Facets; [ [ 1, 6 ], [ 1, 7 ], [ 2, 5 ], [ 2, 7 ], [ 5, 7 ], [ 6, 7 ] ] gap> sphere:=SCBdSimplex(4);; gap> ball:=SCDifference(sphere,SC([sphere.Facets[1]]));; gap> coll:=SCCollapseLex(ball); <SimplicialComplex: collapsed version of S^3_5 \ unnamed complex 22 | dim = 0 \ | n = 1> 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: collapsed version of T^2 \ unnamed complex 28 | dim = 1 | \ n = 5> gap> coll.Facets; [ [ 1, 3 ], [ 1, 7 ], [ 3, 4 ], [ 3, 5 ], [ 4, 7 ], [ 5, 7 ] ] gap> sphere:=SCBdSimplex(4);; gap> ball:=SCDifference(sphere,SC([sphere.Facets[1]]));; gap> coll:=SCCollapseRevLex(ball); <SimplicialComplex: collapsed version of S^3_5 \ unnamed complex 32 | dim = 0 \ | n = 1> 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 ], 25 ], [ 8, [ 1, 3, 3, 1 ], 5 ] ] gap> f:=SCMorseSpec(c,30,SCMorseRandomLex); [ [ 6, [ 1, 2, 2, 1 ], 30 ] ] gap> f:=SCMorseSpec(c,30,SCMorseRandomRevLex); [ [ 6, [ 1, 2, 2, 1 ], 7 ], [ 8, [ 1, 3, 3, 1 ], 13 ], [ 10, [ 1, 4, 4, 1 ], 9 ], [ 10, [ 2, 4, 3, 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 ], 4 ] ]
‣ 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); [ 15, 2, 6, 12, 7, 8, 1, 3, 11 ] gap> stBot:=SCSpanningTreeRandom(HD,false); [ 9, 5, 3, 6, 11 ]
‣ 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, [ ] ] ] 31 gap> c := SCSeriesHomologySphere(2,3,5);; gap> SCHomologyEx(c,SCMorseRandomLex,SmithNormalFormIntegerMat); time; [ [ 0, [ ] ], [ 0, [ ] ], [ 0, [ ] ], [ 1, [ ] ] ] 30 gap> c := SCSeriesHomologySphere(2,3,5);; gap> SCHomologyEx(c,SCMorseRandomRevLex,SmithNormalFormIntegerMat); time; [ [ 0, [ ] ], [ 0, [ ] ], [ 0, [ ] ], [ 1, [ ] ] ] 33 gap> c := SCSeriesHomologySphere(2,3,5);; gap> SCHomologyEx(c,SCMorseEngstroem,SmithNormalFormIntegerMat); time; [ [ 0, [ ] ], [ 0, [ ] ], [ 0, [ ] ], [ 1, [ ] ] ] 63 gap> c := SCSeriesHomologySphere(2,3,5);; gap> SCHomologyEx(c,SCMorseUST,SmithNormalFormIntegerMat); time; [ [ 0, [ ] ], [ 0, [ ] ], [ 0, [ ] ], [ 1, [ ] ] ] 74
‣ 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