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 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{\95], Corollary 4.7), or `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. 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 ≥ 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 ⋅ (n-1) ⋅ dots ⋅ (n-k+1).

gap> list:=SCLib.SearchByName("S^2~S^1 (VT)"){[1..9]}; [ [ 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)" ] ] gap> s2s1:=SCLib.Load(list[1][1]); [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: complex is 3-dimensional and tight neighbourly, and thus tight. true 4

gap> SCLib.SearchByAttribute("F[1] = 120"); [ [ 7647, "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 8

gap> SCInfoLevel(0); true gap> SCLib.SearchByName("K3"); [ [ 7648, "K3_16" ], [ 7649, "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 3-dimensional and tight neighbourly, 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)" ] ] gap> c:=SCLib.Load(list[1][1]); [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 SCIsInKd: checking link 1/1 #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

`‣ 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 (α ) 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 ] ] ]

`‣ 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> 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"); [ [ 7648, "K3_16" ], [ 7649, "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