chap11.txt

  
  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).
  
    Example  
     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
     
  
  
    Example  
     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
     12
     
  
  
    Example  
     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
     
  
  
    Example  
     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);
     true
     
  
  
    Example  
     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/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: 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.
  
    Example  
     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.
  
    Example  
     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]
     
  
  
    Example  
     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.
  
    Example  
     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.
  
    Example  
     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 ] ]