In this chapter we present some useful functions dealing with polyhedral Morse theory. See Section 2.5 for a very short introduction to the field, see [K\t95] for more information. Note: this is not to be confused with Robin Forman's discrete Morse theory for cell complexes which is described in Chapter 12.
If \(M\) is a combinatorial \(d\)-manifold with \(n\)-vertices a rsl-function will be represented as an ordering on the set of vertices, i. e. a list of length \(n\) containing all vertex labels of the corresponding simplicial complex.
‣ SCIsTight( complex ) | ( method ) |
Returns: true or false upon success, fail otherwise.
Checks whether a simplicial complex complex (complex must satisfy the weak pseudomanifold property and must be closed) is a tight triangulation (with respect to the field with two elements) or not. A simplicial complex with \(n\) vertices is said to be a tight triangulation if it can be tightly embedded into the \((n-1)\)-simplex. See Section 2.7 for a short introduction to the field of tightness.
First, if complex is a \((k+1)\)-neighborly \(2k\)-manifold (cf. [K\t95], Corollary 4.7), or complex is of dimension \(d\geq 4\), \(2\)-neighborly and all its vertex links are stacked spheres (i.e. the complex is in Walkup's class \(K(d)\), see [Eff11b]) true is returned as the complex is a tight triangulation in these cases. If complex is of dimension \(d = 3\), true is returned if and only if complex is \(2\)-neighborly and stacked (i.e. tight-neighbourly, see [BDSS15]), otherwise false is returned, see [BDS16].
Note that, for dimension \(d \geq 4\), it is not computed whether or not complex is a combinatorial manifold as this computation might take a long time. Hence, only if the manifold flag of the complex is set (this can be achieved by calling SCIsManifold (12.1-17) and the complex indeed is a combinatorial manifold) these checks are performed.
In a second step, the algorithm first checks certain rsl-functions allowing slicings between minimal non faces and the rest of the complex. In most cases where complex is not tight at least one of these rsl-functions is not perfect and thus false is returned as the complex is not a tight triangulation.
If the complex passed all checks so far, the remaining rsl-functions are checked for being perfect functions. As there are ``only'' \(2^n\) different multiplicity vectors, but \(n!\) different rsl-functions, a lookup table containing all possible multiplicity vectors is computed first. Note that nonetheless the complexity of this algorithm is \(O(n!)\).
In order to reduce the number of rsl-functions that need to be checked, the automorphism group of complex is computed first using SCAutomorphismGroup (6.9-2). In case it is \(k\)-transitive, the complexity is reduced by the factor of \(n \cdot (n-1) \cdot \dots \cdot (n-k+1)\).
gap> list:=SCLib.SearchByName("S^2~S^1 (VT)"){[1..9]};;
gap> s2s1:=SCLib.Load(list[1][1]);
<SimplicialComplex: S^2~S^1 (VT) | dim = 3 | n = 9>
gap> SCInfoLevel(2); # print information while running
true
gap> SCIsTight(s2s1); time;
#I SCIsTight: complex is 3-dimensional and tight neighbourly, and thus tight.
true
2
gap> SCLib.SearchByAttribute("F[1] = 120");
[ [ 648, "Bd(600-cell)" ] ]
gap> id:=last[1][1];;
gap> c:=SCLib.Load(id);;
gap> SCIsTight(c); time;
#I SCIsTight: complex is connected but not 2-neighbourly, and thus not tight.
false
194392
gap> SCInfoLevel(0);
true
gap> SCLib.SearchByName("K3");
[ [ 520, "K3_16" ], [ 539, "K3_17" ] ]
gap> c:=SCLib.Load(last[1][1]);;
gap> SCIsManifold(c);
true
gap> SCInfoLevel(1);
true
gap> c.IsTight;
#I SCIsTight: complex is (k+1)-neighborly 2k-manifold and thus tight.
true
gap> SCInfoLevel(1); true gap> dc:=[ [ 1, 1, 1, 1, 45 ], [ 1, 2, 1, 27, 18 ], [ 1, 27, 9, 9, 3 ], > [ 4, 7, 20, 9, 9 ], [ 9, 9, 11, 9, 11 ], [ 6, 9, 9, 17, 8 ], > [ 6, 10, 8, 17, 8 ], [ 8, 8, 8, 8, 17 ], [ 5, 6, 9, 9, 20 ] ];; gap> c:=SCBoundary(SCFromDifferenceCycles(dc));; gap> SCAutomorphismGroup(c);; gap> SCIsTight(c); #I SCIsTight: complex is (k+1)-neighborly 2k-manifold and thus tight. true
gap> list:=SCLib.SearchByName("S^3xS^1");;
gap> c:=SCLib.Load(list[1][1]);
<SimplicialComplex: S^3xS^1 (VT) | dim = 4 | n = 11>
gap> SCInfoLevel(0);
true
gap> SCIsManifold(c);
true
gap> SCInfoLevel(2);
true
gap> c.IsTight;
#I SCIsInKd: checking link 1/11
#I SCIsKStackedSphere: checking if complex is a 1-stacked sphere...
#I SCIsKStackedSphere: try 1/1
#I round 0
Reduced complex, F: [ 9, 26, 34, 17 ]
#I round 1
Reduced complex, F: [ 8, 22, 28, 14 ]
#I round 2
Reduced complex, F: [ 7, 18, 22, 11 ]
#I round 3
Reduced complex, F: [ 6, 14, 16, 8 ]
#I round 4
Reduced complex, F: [ 5, 10, 10, 5 ]
#I SCReduceComplexEx: computed locally minimal complex after 5 rounds.
#I SCIsKStackedSphere: complex is a 1-stacked sphere.
#I SCIsInKd: checking link 2/11
#I SCIsKStackedSphere: checking if complex is a 1-stacked sphere...
#I SCIsKStackedSphere: try 1/1
#I round 0
Reduced complex, F: [ 9, 26, 34, 17 ]
#I round 1
Reduced complex, F: [ 8, 22, 28, 14 ]
#I round 2
Reduced complex, F: [ 7, 18, 22, 11 ]
#I round 3
Reduced complex, F: [ 6, 14, 16, 8 ]
#I round 4
Reduced complex, F: [ 5, 10, 10, 5 ]
#I SCReduceComplexEx: computed locally minimal complex after 5 rounds.
#I SCIsKStackedSphere: complex is a 1-stacked sphere.
#I SCIsInKd: checking link 3/11
#I SCIsKStackedSphere: checking if complex is a 1-stacked sphere...
#I SCIsKStackedSphere: try 1/1
#I round 0
Reduced complex, F: [ 9, 26, 34, 17 ]
#I round 1
Reduced complex, F: [ 8, 22, 28, 14 ]
#I round 2
Reduced complex, F: [ 7, 18, 22, 11 ]
#I round 3
Reduced complex, F: [ 6, 14, 16, 8 ]
#I round 4
Reduced complex, F: [ 5, 10, 10, 5 ]
#I SCReduceComplexEx: computed locally minimal complex after 5 rounds.
#I SCIsKStackedSphere: complex is a 1-stacked sphere.
#I SCIsInKd: checking link 4/11
#I SCIsKStackedSphere: checking if complex is a 1-stacked sphere...
#I SCIsKStackedSphere: try 1/1
#I round 0
Reduced complex, F: [ 9, 26, 34, 17 ]
#I round 1
Reduced complex, F: [ 8, 22, 28, 14 ]
#I round 2
Reduced complex, F: [ 7, 18, 22, 11 ]
#I round 3
Reduced complex, F: [ 6, 14, 16, 8 ]
#I round 4
Reduced complex, F: [ 5, 10, 10, 5 ]
#I SCReduceComplexEx: computed locally minimal complex after 5 rounds.
#I SCIsKStackedSphere: complex is a 1-stacked sphere.
#I SCIsInKd: checking link 5/11
#I SCIsKStackedSphere: checking if complex is a 1-stacked sphere...
#I SCIsKStackedSphere: try 1/1
#I round 0
Reduced complex, F: [ 9, 26, 34, 17 ]
#I round 1
Reduced complex, F: [ 8, 22, 28, 14 ]
#I round 2
Reduced complex, F: [ 7, 18, 22, 11 ]
#I round 3
Reduced complex, F: [ 6, 14, 16, 8 ]
#I round 4
Reduced complex, F: [ 5, 10, 10, 5 ]
#I SCReduceComplexEx: computed locally minimal complex after 5 rounds.
#I SCIsKStackedSphere: complex is a 1-stacked sphere.
#I SCIsInKd: checking link 6/11
#I SCIsKStackedSphere: checking if complex is a 1-stacked sphere...
#I SCIsKStackedSphere: try 1/1
#I round 0
Reduced complex, F: [ 9, 26, 34, 17 ]
#I round 1
Reduced complex, F: [ 8, 22, 28, 14 ]
#I round 2
Reduced complex, F: [ 7, 18, 22, 11 ]
#I round 3
Reduced complex, F: [ 6, 14, 16, 8 ]
#I round 4
Reduced complex, F: [ 5, 10, 10, 5 ]
#I SCReduceComplexEx: computed locally minimal complex after 5 rounds.
#I SCIsKStackedSphere: complex is a 1-stacked sphere.
#I SCIsInKd: checking link 7/11
#I SCIsKStackedSphere: checking if complex is a 1-stacked sphere...
#I SCIsKStackedSphere: try 1/1
#I round 0
Reduced complex, F: [ 9, 26, 34, 17 ]
#I round 1
Reduced complex, F: [ 8, 22, 28, 14 ]
#I round 2
Reduced complex, F: [ 7, 18, 22, 11 ]
#I round 3
Reduced complex, F: [ 6, 14, 16, 8 ]
#I round 4
Reduced complex, F: [ 5, 10, 10, 5 ]
#I SCReduceComplexEx: computed locally minimal complex after 5 rounds.
#I SCIsKStackedSphere: complex is a 1-stacked sphere.
#I SCIsInKd: checking link 8/11
#I SCIsKStackedSphere: checking if complex is a 1-stacked sphere...
#I SCIsKStackedSphere: try 1/1
#I round 0
Reduced complex, F: [ 9, 26, 34, 17 ]
#I round 1
Reduced complex, F: [ 8, 22, 28, 14 ]
#I round 2
Reduced complex, F: [ 7, 18, 22, 11 ]
#I round 3
Reduced complex, F: [ 6, 14, 16, 8 ]
#I round 4
Reduced complex, F: [ 5, 10, 10, 5 ]
#I SCReduceComplexEx: computed locally minimal complex after 5 rounds.
#I SCIsKStackedSphere: complex is a 1-stacked sphere.
#I SCIsInKd: checking link 9/11
#I SCIsKStackedSphere: checking if complex is a 1-stacked sphere...
#I SCIsKStackedSphere: try 1/1
#I round 0
Reduced complex, F: [ 9, 26, 34, 17 ]
#I round 1
Reduced complex, F: [ 8, 22, 28, 14 ]
#I round 2
Reduced complex, F: [ 7, 18, 22, 11 ]
#I round 3
Reduced complex, F: [ 6, 14, 16, 8 ]
#I round 4
Reduced complex, F: [ 5, 10, 10, 5 ]
#I SCReduceComplexEx: computed locally minimal complex after 5 rounds.
#I SCIsKStackedSphere: complex is a 1-stacked sphere.
#I SCIsInKd: checking link 10/11
#I SCIsKStackedSphere: checking if complex is a 1-stacked sphere...
#I SCIsKStackedSphere: try 1/1
#I round 0
Reduced complex, F: [ 9, 26, 34, 17 ]
#I round 1
Reduced complex, F: [ 8, 22, 28, 14 ]
#I round 2
Reduced complex, F: [ 7, 18, 22, 11 ]
#I round 3
Reduced complex, F: [ 6, 14, 16, 8 ]
#I round 4
Reduced complex, F: [ 5, 10, 10, 5 ]
#I SCReduceComplexEx: computed locally minimal complex after 5 rounds.
#I SCIsKStackedSphere: complex is a 1-stacked sphere.
#I SCIsInKd: checking link 11/11
#I SCIsKStackedSphere: checking if complex is a 1-stacked sphere...
#I SCIsKStackedSphere: try 1/1
#I round 0
Reduced complex, F: [ 9, 26, 34, 17 ]
#I round 1
Reduced complex, F: [ 8, 22, 28, 14 ]
#I round 2
Reduced complex, F: [ 7, 18, 22, 11 ]
#I round 3
Reduced complex, F: [ 6, 14, 16, 8 ]
#I round 4
Reduced complex, F: [ 5, 10, 10, 5 ]
#I SCReduceComplexEx: computed locally minimal complex after 5 rounds.
#I SCIsKStackedSphere: complex is a 1-stacked sphere.
#I SCIsInKd: all links are 1-stacked.
#I SCIsTight: complex is in class K(1) and 2-neighborly, thus tight.
true
‣ SCMorseIsPerfect( c, f ) | ( method ) |
Returns: true or false upon success, fail otherwise.
Checks whether the rsl-function f is perfect on the simplicial complex c or not. A rsl-function is said to be perfect, if it has the minimum number of critical points, i. e. if the sum of its critical points equals the sum of the Betti numbers of c.
gap> c:=SCBdCyclicPolytope(4,6);; gap> SCMinimalNonFaces(c); [ [ ], [ ], [ [ 1, 3, 5 ], [ 2, 4, 6 ] ] ] gap> SCMorseIsPerfect(c,[1..6]); true gap> SCMorseIsPerfect(c,[1,3,5,2,4,6]); false
‣ SCSlicing( complex, slicing ) | ( method ) |
Returns: a facet list of a polyhedral complex or a SCNormalSurface object upon success, fail otherwise.
Returns the pre-image \(f^{-1} (\alpha )\) of a rsl-function \(f\) on the simplicial complex complex where \(f\) is given in the second argument slicing by a partition of the set of vertices slicing\(=[ V_1 , V_2 ]\) such that \(f(v_1)\) (\(f(v_2)\)) is smaller (greater) than \(\alpha\) for all \(v_1 \in V_1\) (\(v_2 \in V_2\)).
If complex is of dimension \(3\), a GAP object of type SCNormalSurface is returned. Otherwise only the facet list is returned. See also SCNSSlicing (7.1-4).
The vertex labels of the returned slicing are of the form \((v_1 , v_2)\) where \(v_1 \in V_1\) and \(v_2 \in V_2\). They represent the center points of the edges \(\rangle v_1 , v_2 \langle \) defined by the intersection of slicing with complex.
gap> c:=SCBdCyclicPolytope(4,6);;
gap> v:=SCVertices(c);
[ 1 .. 6 ]
gap> SCMinimalNonFaces(c);
[ [ ], [ ], [ [ 1, 3, 5 ], [ 2, 4, 6 ] ] ]
gap> ns:=SCSlicing(c,[v{[1,3,5]},v{[2,4,6]}]);
<NormalSurface: slicing [ [ 1, 3, 5 ], [ 2, 4, 6 ] ] of Bd(C_4(6)) | dim = 2>
gap> c:=SCBdSimplex(5);;
gap> v:=SCVertices(c);
[ 1 .. 6 ]
gap> slicing:=SCSlicing(c,[v{[1,3,5]},v{[2,4,6]}]);
[ [ [ 1, 2 ], [ 1, 4 ], [ 3, 2 ], [ 3, 4 ], [ 5, 2 ], [ 5, 4 ] ],
[ [ 1, 2 ], [ 1, 4 ], [ 1, 6 ], [ 3, 2 ], [ 3, 4 ], [ 3, 6 ] ],
[ [ 1, 2 ], [ 1, 6 ], [ 3, 2 ], [ 3, 6 ], [ 5, 2 ], [ 5, 6 ] ],
[ [ 1, 2 ], [ 1, 4 ], [ 1, 6 ], [ 5, 2 ], [ 5, 4 ], [ 5, 6 ] ],
[ [ 1, 4 ], [ 1, 6 ], [ 3, 4 ], [ 3, 6 ], [ 5, 4 ], [ 5, 6 ] ],
[ [ 3, 2 ], [ 3, 4 ], [ 3, 6 ], [ 5, 2 ], [ 5, 4 ], [ 5, 6 ] ] ]
‣ SCMorseMultiplicityVector( c, f ) | ( method ) |
Returns: a list of \((d+1)\)-tuples if c is a \(d\)-dimensional simplicial complex upon success, fail otherwise.
Computes all multiplicity vectors of a rsl-function f on a simplicial complex c. f is given as an ordered list \((v_1 , \ldots v_n)\) of all vertices of c where f is defined by f\((v_i) = \frac{i-1}{n-1}\). The \(i\)-th entry of the returned list denotes the multiplicity vector of vertex \(v_i\).
gap> SCLib.SearchByName("K3");
[ [ 520, "K3_16" ], [ 539, "K3_17" ] ]
gap> c:=SCLib.Load(last[1][1]);;
gap> f:=SCVertices(c);
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ]
gap> SCMorseMultiplicityVector(c,f);
[ [ 1, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ],
[ 0, 0, 2, 0, 0 ], [ 0, 0, 1, 0, 0 ], [ 0, 0, 4, 0, 0 ], [ 0, 0, 3, 0, 0 ],
[ 0, 0, 3, 0, 0 ], [ 0, 0, 4, 0, 0 ], [ 0, 0, 1, 0, 0 ], [ 0, 0, 2, 0, 0 ],
[ 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 1 ] ]
‣ SCMorseNumberOfCriticalPoints( c, f ) | ( method ) |
Returns: an integer and a list upon success, fail otherwise.
Computes the number of critical points of each index of a rsl-function f on a simplicial complex c as well as the total number of critical points.
gap> SCLib.SearchByName("K3");
[ [ 520, "K3_16" ], [ 539, "K3_17" ] ]
gap> c:=SCLib.Load(last[1][1]);;
gap> f:=SCVertices(c);
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ]
gap> SCMorseNumberOfCriticalPoints(c,f);
[ 24, [ 1, 0, 22, 0, 1 ] ]
generated by GAPDoc2HTML