Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Bib Ind

### 11 Polyhedral Morse theory

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{\95] for more information. Note: this is not to be confused with Robin Forman's discrete Morse theory for cell complexes [For95].

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.

#### 11.1 Polyhedral Morse theory related functions

##### 11.1-1 SCIsTight
 `‣ SCIsTight`( complex ) ( method )

Returns: `true` or `false` upon success, `fail` otherwise.

Checks whether a simplicial complex `complex` is a tight triangulation 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.6 for a short introduction to the field of tightness.

First, if `complex` is a (k+1)-neighborly 2k-manifold (cf. [K{\95], Corollary 4.7) or if `complex` is of dimension d≥ 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. Note that 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` (9.2-6) 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.8-2). In case it is k-transitive, the complexity is reduced by the factor of n ⋅ (n-1) ⋅ dots ⋅ (n-k+1).

``` gap> list:=SCLib.SearchByName("S^2~S^1 (VT)");
[ [ 12, "S^2~S^1 (VT)" ], [ 27, "S^2~S^1 (VT)" ], [ 28, "S^2~S^1 (VT)" ],
[ 43, "S^2~S^1 (VT)" ], [ 47, "S^2~S^1 (VT)" ], [ 49, "S^2~S^1 (VT)" ],
[ 89, "S^2~S^1 (VT)" ], [ 90, "S^2~S^1 (VT)" ], [ 111, "S^2~S^1 (VT)" ],
[ 140, "S^2~S^1 (VT)" ], [ 146, "S^2~S^1 (VT)" ], [ 147, "S^2~S^1 (VT)" ],
[ 148, "S^2~S^1 (VT)" ], [ 149, "S^2~S^1 (VT)" ], [ 150, "S^2~S^1 (VT)" ],
[ 156, "S^2~S^1 (VT)" ], [ 157, "S^2~S^1 (VT)" ], [ 391, "S^2~S^1 (VT)" ],
[ 393, "S^2~S^1 (VT)" ], [ 394, "S^2~S^1 (VT)" ], [ 396, "S^2~S^1 (VT)" ],
[ 407, "S^2~S^1 (VT)" ], [ 408, "S^2~S^1 (VT)" ], [ 410, "S^2~S^1 (VT)" ],
[ 412, "S^2~S^1 (VT)" ], [ 413, "S^2~S^1 (VT)" ], [ 578, "S^2~S^1 (VT)" ],
[ 579, "S^2~S^1 (VT)" ], [ 582, "S^2~S^1 (VT)" ], [ 596, "S^2~S^1 (VT)" ],
[ 597, "S^2~S^1 (VT)" ], [ 598, "S^2~S^1 (VT)" ], [ 640, "S^2~S^1 (VT)" ],
[ 642, "S^2~S^1 (VT)" ], [ 644, "S^2~S^1 (VT)" ], [ 645, "S^2~S^1 (VT)" ],
[ 769, "S^2~S^1 (VT)" ], [ 770, "S^2~S^1 (VT)" ], [ 774, "S^2~S^1 (VT)" ],
[ 775, "S^2~S^1 (VT)" ], [ 776, "S^2~S^1 (VT)" ], [ 2401, "S^2~S^1 (VT)" ],
[ 2409, "S^2~S^1 (VT)" ], [ 2410, "S^2~S^1 (VT)" ],
[ 2411, "S^2~S^1 (VT)" ], [ 2428, "S^2~S^1 (VT)" ],
[ 2429, "S^2~S^1 (VT)" ], [ 2430, "S^2~S^1 (VT)" ],
[ 2431, "S^2~S^1 (VT)" ], [ 2432, "S^2~S^1 (VT)" ],
[ 2433, "S^2~S^1 (VT)" ], [ 2434, "S^2~S^1 (VT)" ],
[ 2435, "S^2~S^1 (VT)" ], [ 2500, "S^2~S^1 (VT)" ],
[ 2501, "S^2~S^1 (VT)" ], [ 2504, "S^2~S^1 (VT)" ],
[ 2505, "S^2~S^1 (VT)" ], [ 2506, "S^2~S^1 (VT)" ],
[ 2510, "S^2~S^1 (VT)" ], [ 2511, "S^2~S^1 (VT)" ],
[ 2512, "S^2~S^1 (VT)" ], [ 2513, "S^2~S^1 (VT)" ],
[ 2514, "S^2~S^1 (VT)" ], [ 2515, "S^2~S^1 (VT)" ] ]
[SimplicialComplex

Properties known: AltshulerSteinberg, AutomorphismGroup,
AutomorphismGroupSize, AutomorphismGroupStructure,
AutomorphismGroupTransitivity, ConnectedComponents,
Dim, DualGraph, EulerCharacteristic, FVector,
FacetsEx, GVector, GeneratorsEx, HVector,
HasBoundary, HasInterior, Homology, Interior,
IsCentrallySymmetric, IsConnected,
IsEulerianManifold, IsManifold, IsOrientable,
IsPseudoManifold, IsPure, IsStronglyConnected,
MinimalNonFacesEx, Name, Neighborliness,
NumFaces[], Orientation, Reference, SkelExs[],
Vertices.

Name="S^2~S^1 (VT)"
Dim=3
AltshulerSteinberg=250838208
AutomorphismGroupSize=18
AutomorphismGroupStructure="D18"
AutomorphismGroupTransitivity=1
EulerCharacteristic=0
FVector=[ 9, 36, 54, 27 ]
GVector=[ 4, 10 ]
HVector=[ 5, 15, 5, 1 ]
HasBoundary=false
HasInterior=true
Homology=[ [ 0, [ ] ], [ 1, [ ] ], [ 0, [ 2 ] ], [ 0, [ ] ] ]
IsCentrallySymmetric=false
IsConnected=true
IsEulerianManifold=true
IsOrientable=false
IsPseudoManifold=true
IsPure=true
IsStronglyConnected=true
Neighborliness=2

/SimplicialComplex]
gap> SCInfoLevel(2); # print information while running
true
gap> SCIsTight(s2s1); time;
#I  SCIsTight: checking non faces...
#I  SCIsTight: found no contradiction so far.
#I  SCIsTight: generating lookup table...
#I  SCIsTight: lookup table done, size = 2304.
#I  SCIsTight: computing automorphism group...
#I  SCIsTight: automorphism group done, transitivity = 1.
#I  SCIsTight: checking rsl-functions...
#I  SCIsTight: processed 10000 of 40320 rsl-functions so far, all perfect.
#I  SCIsTight: processed 20000 of 40320 rsl-functions so far, all perfect.
#I  SCIsTight: processed 30000 of 40320 rsl-functions so far, all perfect.
#I  SCIsTight: processed 40000 of 40320 rsl-functions so far, all perfect.
true
5648
```
``` gap> SCLib.SearchByAttribute("F[1] = 120");
[ [ 7647, "Bd(600-cell)" ] ]
gap> id:=last[1][1];;
gap> SCIsTight(c); time;
#I  SCIsTight: checking non faces...
#I  SCIsTight: found non perfect rsl-function: [ 1, 3, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78,
79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97,
98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112,
113, 114, 115, 116, 117, 118, 119, 120 ], complex not tight.
false
4
```
``` gap> SCInfoLevel(0);
true
gap> SCLib.SearchByName("K3");
[ [ 7648, "K3_16" ], [ 7649, "K3_17" ] ]
gap> SCIsManifold(c);
true
gap> SCInfoLevel(2);
true
gap> c.IsTight;
#I  SCIsTight: complex is (k+1)-neighborly 2k-manifold and thus tight.
true
```
``` gap> list:=SCLib.SearchByName("S^3xS^1");
[ [ 55, "S^3xS^1 (VT)" ], [ 128, "S^3xS^1 (VT)" ], [ 399, "S^3xS^1 (VT)" ],
[ 459, "S^3xS^1 (VT)" ], [ 460, "S^3xS^1 (VT)" ], [ 461, "S^3xS^1 (VT)" ],
[ 462, "S^3xS^1 (VT)" ], [ 588, "S^3xS^1 (VT)" ], [ 612, "S^3xS^1 (VT)" ],
[ 699, "S^3xS^1 (VT)" ], [ 700, "S^3xS^1 (VT)" ], [ 701, "S^3xS^1 (VT)" ],
[ 703, "S^3xS^1 (VT)" ], [ 1078, "S^3xS^1 (VT)" ], [ 1080, "S^3xS^1 (VT)" ],
[ 1081, "S^3xS^1 (VT)" ], [ 1082, "S^3xS^1 (VT)" ],
[ 1083, "S^3xS^1 (VT)" ], [ 1084, "S^3xS^1 (VT)" ],
[ 1085, "S^3xS^1 (VT)" ], [ 1086, "S^3xS^1 (VT)" ],
[ 1087, "S^3xS^1 (VT)" ], [ 1088, "S^3xS^1 (VT)" ],
[ 1089, "S^3xS^1 (VT)" ], [ 1091, "S^3xS^1 (VT)" ],
[ 2413, "S^3xS^1 (VT)" ], [ 2470, "S^3xS^1 (VT)" ],
[ 2471, "S^3xS^1 (VT)" ], [ 2472, "S^3xS^1 (VT)" ],
[ 2473, "S^3xS^1 (VT)" ], [ 2474, "S^3xS^1 (VT)" ],
[ 2475, "S^3xS^1 (VT)" ], [ 2476, "S^3xS^1 (VT)" ],
[ 3413, "S^3xS^1 (VT)" ], [ 3414, "S^3xS^1 (VT)" ],
[ 3415, "S^3xS^1 (VT)" ], [ 3416, "S^3xS^1 (VT)" ],
[ 3417, "S^3xS^1 (VT)" ], [ 3418, "S^3xS^1 (VT)" ],
[ 3419, "S^3xS^1 (VT)" ], [ 3420, "S^3xS^1 (VT)" ],
[ 3421, "S^3xS^1 (VT)" ], [ 3422, "S^3xS^1 (VT)" ],
[ 3423, "S^3xS^1 (VT)" ], [ 3424, "S^3xS^1 (VT)" ],
[ 3425, "S^3xS^1 (VT)" ], [ 3426, "S^3xS^1 (VT)" ],
[ 3427, "S^3xS^1 (VT)" ], [ 3428, "S^3xS^1 (VT)" ],
[ 3429, "S^3xS^1 (VT)" ], [ 3430, "S^3xS^1 (VT)" ],
[ 3431, "S^3xS^1 (VT)" ], [ 3432, "S^3xS^1 (VT)" ],
[ 3433, "S^3xS^1 (VT)" ], [ 3434, "S^3xS^1 (VT)" ] ]
[SimplicialComplex

Properties known: AltshulerSteinberg, AutomorphismGroup,
AutomorphismGroupSize, AutomorphismGroupStructure,
AutomorphismGroupTransitivity, ConnectedComponents,
Dim, DualGraph, EulerCharacteristic, FVector,
FacetsEx, GVector, GeneratorsEx, HVector,
HasBoundary, HasInterior, Homology, Interior,
IsCentrallySymmetric, IsConnected,
IsEulerianManifold, IsManifold, IsOrientable,
IsPseudoManifold, IsPure, IsStronglyConnected,
MinimalNonFacesEx, Name, Neighborliness,
NumFaces[], Orientation, Reference, SkelExs[],
Vertices.

Name="S^3xS^1 (VT)"
Dim=4
AltshulerSteinberg=737125273600
AutomorphismGroupSize=22
AutomorphismGroupStructure="D22"
AutomorphismGroupTransitivity=1
EulerCharacteristic=0
FVector=[ 11, 55, 110, 110, 44 ]
GVector=[ 5, 15, -20 ]
HVector=[ 6, 21, 1, 16, -1 ]
HasBoundary=false
HasInterior=true
Homology=[ [ 0, [ ] ], [ 1, [ ] ], [ 0, [ ] ], [ 1, [ ] ], [ 1, [ ] ] ]
IsCentrallySymmetric=false
IsConnected=true
IsEulerianManifold=true
IsOrientable=true
IsPseudoManifold=true
IsPure=true
IsStronglyConnected=true
Neighborliness=2

/SimplicialComplex]
gap> SCInfoLevel(0);
true
gap> SCIsManifold(c);
true
gap> SCInfoLevel(2);
true
gap> c.IsTight;
#I  SCIsInKd: complex has transitive automorphism group, only checking one link.
#I  SCIsKStackedSphere: checking if complex is a 1-stacked sphere...
#I  SCIsKStackedSphere: try 1/50
#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: complex has transitive automorphism group, all links are 1-stacked.
#I  SCIsTight: complex is in class K(1) and 2-neighborly, thus tight.
true
```

##### 11.1-2 SCMorseIsPerfect
 `‣ 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
```

##### 11.1-3 SCSlicing
 `‣ 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 (α ) 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 α for all v_1 ∈ V_1 (v_2 ∈ 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 ∈ V_1 and v_2 ∈ V_2. They represent the center points of the edges ⟩ v_1 , v_2 ⟨ defined by the intersection of slicing with complex.

``` gap> c:=SCBdCyclicPolytope(4,6);;
gap> v:=SCVertices(c);
[ 1, 2, 3, 4, 5, 6 ]
gap> SCMinimalNonFaces(c);
[ [  ], [  ], [ [ 1, 3, 5 ], [ 2, 4, 6 ] ] ]
gap> ns:=SCSlicing(c,[v{[1,3,5]},v{[2,4,6]}]);
[NormalSurface

Properties known: ConnectedComponents, Dim, EulerCharacteristic, FVector, Fac\
etsEx, Genus, IsConnected, IsOrientable, NSTriangulation, Name, TopologicalTyp\
e, Vertices.

Name="slicing [ [ 1, 3, 5 ], [ 2, 4, 6 ] ] of Bd(C_4(6))"
Dim=2
FVector=[ 9, 18, 0, 9 ]
EulerCharacteristic=0
IsOrientable=true
TopologicalType="T^2"

/NormalSurface]
```
``` gap> c:=SCBdSimplex(5);;
gap> v:=SCVertices(c);
[ 1, 2, 3, 4, 5, 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 ] ] ]
```

##### 11.1-4 SCMorseMultiplicityVector
 `‣ 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 , ... v_n) of all vertices of `c` where `f` is defined by `f`(v_i) = fraci-1n-1. The i-th entry of the returned list denotes the multiplicity vector of vertex v_i.

``` gap> SCLib.SearchByName("K3");
[ [ 7648, "K3_16" ], [ 7649, "K3_17" ] ]
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 ] ]
```

##### 11.1-5 SCMorseNumberOfCriticalPoints
 `‣ 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");
[ [ 7648, "K3_16" ], [ 7649, "K3_17" ] ]