Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

11 Polyhedral Morse theory
 11.1 Polyhedral Morse theory related functions

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 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.

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 (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
 

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> 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 ] ]
 

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" ] ]
 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 ] ]
 
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Bib Ind

generated by GAPDoc2HTML