chap12.txt

  
  12 Forman's discrete Morse theory
  
  In  this  chapter  a  framework  is  provided to use Forman's discrete Morse
  theory [For95] within simpcomp. See Section 2.6 for a brief introduction.
  
  Note:  this  is  not  to  be  confused  with Banchoff and Kühnel's theory of
  regular simplexwise linear functions which is described in Chapter 11.
  
  
  12.1 Functions using discrete Morse theory
  
  12.1-1 SCCollapseGreedy
  
  SCCollapseGreedy( complex )  method
  Returns:  simplicial  complex of type SCSimplicialComplex upon success, fail
            otherwise.
  
  Employs  a  greedy  collapsing  algorithm to collapse the simplicial complex
  complex. See also SCCollapseLex (12.1-2) and SCCollapseRevLex (12.1-3).
  
    Example  
     gap> SCLib.SearchByName("T^2"){[1..6]}; 
     [ [ 4, "T^2 (VT)" ], [ 5, "T^2 (VT)" ], [ 9, "T^2 (VT)" ], [ 10, "T^2 (VT)" ],
       [ 18, "T^2 (VT)" ], [ 20, "(T^2)#2" ] ]
     gap> torus:=SCLib.Load(last[1][1]);;
     gap> bdtorus:=SCDifference(torus,SC([torus.Facets[1]]));;
     gap> coll:=SCCollapseGreedy(bdtorus);
     [SimplicialComplex
     
      Properties known: Dim, FacetsEx, Name, Vertices.
     
      Name="collapsed version of T^2 (VT) \ unnamed complex 8"
      Dim=1
     
     /SimplicialComplex]
     gap> coll.Facets;
     [ [ 2, 5 ], [ 2, 6 ], [ 2, 7 ], [ 5, 6 ], [ 5, 7 ] ]
     gap> sphere:=SCBdSimplex(4);;                              
     gap> bdsphere:=SCDifference(sphere,SC([sphere.Facets[1]]));;
     gap> coll:=SCCollapseGreedy(bdsphere);
     [SimplicialComplex
     
      Properties known: Dim, FVector, FacetsEx, IsPure, Name, NumFaces[], 
                        SkelExs[], Vertices.
     
      Name="collapsed version of S^3_5 \ unnamed complex 12"
      Dim=0
      FVector=[ 1 ]
      IsPure=true
     
     /SimplicialComplex]
     gap> coll.Facets;                     
     [ [ 2 ] ]
     
  
  
  12.1-2 SCCollapseLex
  
  SCCollapseLex( complex )  method
  Returns:  simplicial  complex of type SCSimplicialComplex upon success, fail
            otherwise.
  
  Employs  a  greedy collapsing algorithm in lexicographical order to collapse
  the  simplicial  complex  complex.  See  also  SCCollapseGreedy (12.1-1) and
  SCCollapseRevLex (12.1-3).
  
    Example  
     gap> s:=SCSurface(1,true);;
     gap> s:=SCDifference(s,SC([SCFacets(s)[1]]));;
     gap> coll:=SCCollapseGreedy(s);
     [SimplicialComplex
     
      Properties known: Dim, FacetsEx, Name, Vertices.
     
      Name="collapsed version of T^2 \ unnamed complex 18"
      Dim=1
     
     /SimplicialComplex]
     gap> coll.Facets;
     [ [ 1, 6 ], [ 1, 7 ], [ 2, 5 ], [ 2, 7 ], [ 5, 7 ], [ 6, 7 ] ]
     gap> sphere:=SCBdSimplex(4);;                              
     gap> ball:=SCDifference(sphere,SC([sphere.Facets[1]]));;
     gap> coll:=SCCollapseLex(ball);
     [SimplicialComplex
     
      Properties known: Dim, FVector, FacetsEx, IsPure, Name, NumFaces[], 
                        SkelExs[], Vertices.
     
      Name="collapsed version of S^3_5 \ unnamed complex 22"
      Dim=0
      FVector=[ 1 ]
      IsPure=true
     
     /SimplicialComplex]
     gap> coll.Facets;                     
     [ [ 5 ] ]
     
  
  
  12.1-3 SCCollapseRevLex
  
  SCCollapseRevLex( complex )  method
  Returns:  simplicial  complex of type SCSimplicialComplex upon success, fail
            otherwise.
  
  Employs  a  greedy  collapsing algorithm in reverse lexicographical order to
  collapse  the simplicial complex complex. See also SCCollapseGreedy (12.1-1)
  and SCCollapseLex (12.1-2).
  
    Example  
     gap> s:=SCSurface(1,true);;
     gap> s:=SCDifference(s,SC([SCFacets(s)[1]]));;
     gap> coll:=SCCollapseGreedy(s);
     [SimplicialComplex
     
      Properties known: Dim, FacetsEx, Name, Vertices.
     
      Name="collapsed version of T^2 \ unnamed complex 28"
      Dim=1
     
     /SimplicialComplex]
     gap> coll.Facets;
     [ [ 1, 3 ], [ 1, 7 ], [ 3, 4 ], [ 3, 5 ], [ 4, 7 ], [ 5, 7 ] ]
     gap> sphere:=SCBdSimplex(4);;                              
     gap> ball:=SCDifference(sphere,SC([sphere.Facets[1]]));;
     gap> coll:=SCCollapseRevLex(ball);
     [SimplicialComplex
     
      Properties known: Dim, FVector, FacetsEx, IsPure, Name, NumFaces[], 
                        SkelExs[], Vertices.
     
      Name="collapsed version of S^3_5 \ unnamed complex 32"
      Dim=0
      FVector=[ 1 ]
      IsPure=true
     
     /SimplicialComplex]
     gap> coll.Facets;                     
     [ [ 1 ] ]
     
  
  
  12.1-4 SCHasseDiagram
  
  SCHasseDiagram( c )  function
  Returns:  two lists of lists upon success, fail otherweise.
  
  Computes  the  Hasse  diagram  of  SCSimplicialComplex  object  c. The Hasse
  diagram  is  returned  as two sets of lists. The first set of lists contains
  the  upward  part of the Hasse diagram, the second set of lists contains the
  downward part of the Hasse diagram.
  
  The  i-th  list  of  each set of lists represents the incidences between the
  (i-1)-faces  and  the  i-faces.  The faces are given by their indices of the
  face lattice.
  
    Example  
     gap> c:=SCBdSimplex(3);;
     gap> HD:=SCHasseDiagram(c);
     [ [ [ [ 1, 2, 3 ], [ 1, 4, 5 ], [ 2, 4, 6 ], [ 3, 5, 6 ] ], 
           [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ], [ 1, 4 ], [ 2, 4 ], [ 3, 4 ] ] ], 
       [ [ [ 2, 1 ], [ 3, 1 ], [ 4, 1 ], [ 3, 2 ], [ 4, 2 ], [ 4, 3 ] ], 
           [ [ 4, 2, 1 ], [ 5, 3, 1 ], [ 6, 3, 2 ], [ 6, 5, 4 ] ] ] ]
     
  
  
  12.1-5 SCMorseEngstroem
  
  SCMorseEngstroem( complex )  function
  Returns:  two lists of small integer lists upon success, fail otherweise.
  
  Builds  a discrete Morse function following the Engstroem method by reducing
  the  input complex to smaller complexes defined by minimal link and deletion
  operations. See [Eng09] for details.
  
    Example  
     gap> c:=SCBdSimplex(3);;
     gap> f:=SCMorseEngstroem(c);
     [ [ [ 2 ], [ 2, 3 ], [ 2, 4 ], [ 2 .. 4 ], [  ], [ 3 ], [ 4 ], [ 3, 4 ], 
           [ 1, 3 ], [ 1, 3, 4 ], [ 1 ], [ 1, 4 ], [ 1, 2, 4 ], [ 1, 2 ], 
           [ 1 .. 3 ] ], [ [ 2 ], [ 1 .. 3 ] ] ]
     
  
  
  12.1-6 SCMorseRandom
  
  SCMorseRandom( complex )  function
  Returns:  two lists of small integer lists upon success, fail otherweise.
  
  Builds  a  discrete  Morse  function  following  Lutz and Benedetti's random
  discrete  Morse theory approach: Faces are paired with free co-dimension one
  faces  until  now  free  faces  remain.  Then  a critical face is removed at
  random. See [BL14a] for details.
  
    Example  
     gap> c:=SCBdSimplex(3);;
     gap> f:=SCMorseRandom(c);;
     gap> Size(f[2]);
     2
     
  
  
  12.1-7 SCMorseRandomLex
  
  SCMorseRandomLex( complex )  function
  Returns:  two lists of small integer lists upon success, fail otherweise.
  
  Builds  a  discrete Morse function following Adiprasito, Benedetti and Lutz'
  lexicographic  random  discrete  Morse theory approach. See [BL14a], [BL14b]
  for details.
  
    Example  
     gap> c := SCSurface(3,true);;
     gap> f:=SCMorseRandomLex(c);;
     gap> Size(f[2]);
     8
     
  
  
  12.1-8 SCMorseRandomRevLex
  
  SCMorseRandomRevLex( complex )  function
  Returns:  two lists of small integer lists upon success, fail otherweise.
  
  Builds  a  discrete Morse function following Adiprasito, Benedetti and Lutz'
  reverse  lexicographic  random  discrete Morse theory approach. See [BL14a],
  [BL14b] for details.
  
    Example  
     gap> c := SCSurface(5,false);;
     gap> f:=SCMorseRandomRevLex(c);;
     gap> Size(f[2]);
     7
     
  
  
  12.1-9 SCMorseSpec
  
  SCMorseSpec( complex, iter[, morsefunc] )  function
  Returns:  a list upon success, fail otherweise.
  
  Computes  iter  versions  of  a  discrete  Morse function of complex using a
  randomised  method  specified  by morsefunc (default choice is SCMorseRandom
  (12.1-6),  other  randomised methods available are SCMorseRandomLex (12.1-7)
  SCMorseRandomRevLex  (12.1-8),  and  SCMorseUST  (12.1-10)).  The  result is
  referred  to  by  the Morse spectrum of complex and is returned in form of a
  list  containing  all  Morse  vectors  sorted  by  number of critical points
  together  with  the  actual  vector  of  critical  points and how often they
  ocurred (see [BL14a] for details).
  
    Example  
     gap> c:=SCSeriesTorus(2);;
     gap> f:=SCMorseSpec(c,30);
     [ [ 4, [ 1, 2, 1 ], 30 ] ]
     
  
  
    Example  
     gap> c:=SCSeriesHomologySphere(2,3,5);;
     gap> f:=SCMorseSpec(c,30,SCMorseRandom);
     [ [ 6, [ 1, 2, 2, 1 ], 25 ], [ 8, [ 1, 3, 3, 1 ], 5 ] ]
     gap> f:=SCMorseSpec(c,30,SCMorseRandomLex);
     [ [ 6, [ 1, 2, 2, 1 ], 30 ] ]
     gap> f:=SCMorseSpec(c,30,SCMorseRandomRevLex);
     [ [ 6, [ 1, 2, 2, 1 ], 7 ], [ 8, [ 1, 3, 3, 1 ], 13 ], 
       [ 10, [ 1, 4, 4, 1 ], 9 ], [ 10, [ 2, 4, 3, 1 ], 1 ] ]
     gap> f:=SCMorseSpec(c,30,SCMorseUST);
     [ [ 6, [ 1, 2, 2, 1 ], 18 ], [ 8, [ 1, 3, 3, 1 ], 8 ], 
       [ 10, [ 1, 4, 4, 1 ], 4 ] ]
     
  
  
  12.1-10 SCMorseUST
  
  SCMorseUST( complex )  function
  Returns:  a  random  Morse  function  of  a simplicial complex and a list of
            critical faces.
  
  Builds a random Morse function by removing a uniformly sampled spanning tree
  from the dual 1-skeleton followed by a collapsing approach. complex needs to
  be  a  closed  weak  pseudomanifold  for  this  to  work. For details of the
  algorithm, see [PS15].
  
    Example  
     gap> c:=SCBdSimplex(3);;
     gap> f:=SCMorseUST(c);;
     gap> Size(f[2]);
     2
     
  
  
  12.1-11 SCSpanningTreeRandom
  
  SCSpanningTreeRandom( HD, top )  function
  Returns:  a list of edges upon success, fail otherweise.
  
  Computes  a  uniformly sampled spanning tree of the complex belonging to the
  Hasse  diagram  HD using Wilson's algorithm (see [Wil96]). If top = true the
  output  is  a  spanning tree of the dual graph of the underlying complex. If
  top  =  false  the  output is a spanning tree of the primal graph (i.e., the
  1-skeleton.
  
    Example  
     gap> c:=SCSurface(1,false);;
     gap> HD:=SCHasseDiagram(c);;
     gap> stTop:=SCSpanningTreeRandom(HD,true);
     [ 15, 2, 6, 12, 7, 8, 1, 3, 11 ]
     gap> stBot:=SCSpanningTreeRandom(HD,false);
     [ 9, 5, 3, 6, 11 ]
     
  
  
  12.1-12 SCHomology
  
  SCHomology( complex )  method
  Returns:  a list of pairs of the form [ integer, list ] upon success
  
  Computes  the  homology  groups  of a given simplicial complex complex using
  SCMorseRandom     (12.1-6)     to    obtain    a    Morse    function    and
  SmithNormalFormIntegerMat.  Use  SCHomologyEx  (12.1-13)  to use alternative
  methods  to  compute  discrete  Morse  functions  (such  as SCMorseEngstroem
  (12.1-5), or SCMorseUST (12.1-10)) or the Smith normal form.
  
  The  output is a list of homology groups of the form [H_0,....,H_d], where d
  is  the dimension of complex. The format of the homology groups H_i is given
  in terms of their maximal cyclic subgroups, i.e. a homology group H_i≅ Z^f +
  Z  /  t_1  Z  ×  dots  ×  Z  /  t_n  Z  is  returned  in form of a list [ f,
  [t_1,...,t_n]  ],  where f is the (integer) free part of H_i and t_i denotes
  the torsion parts of H_i ordered in weakly increasing size.
  
    Example  
     gap> c:=SCSeriesTorus(2);;
     gap> f:=SCHomology(c);
     [ [ 0, [  ] ], [ 2, [  ] ], [ 1, [  ] ] ]
     
  
  
  12.1-13 SCHomologyEx
  
  SCHomologyEx( c, morsechoice, smithchoice )  method
  Returns:  a  list  of pairs of the form [ integer, list ] upon success, fail
            otherwise.
  
  Computes  the  homology  groups  of  a  given simplicial complex c using the
  function   morsechoice   for   discrete   Morse  function  computations  and
  smithchoice for Smith normal form computations.
  
  The  output is a list of homology groups of the form [H_0,....,H_d], where d
  is  the dimension of complex. The format of the homology groups H_i is given
  in terms of their maximal cyclic subgroups, i.e. a homology group H_i≅ Z^f +
  Z  /  t_1  Z  ×  dots  ×  Z  /  t_n  Z  is  returned  in form of a list [ f,
  [t_1,...,t_n]  ],  where f is the (integer) free part of H_i and t_i denotes
  the torsion parts of H_i ordered in weakly increasing size.
  
    Example  
     gap> c:=SCSeriesTorus(2);;
     gap> f:=SCHomology(c);
     [ [ 0, [  ] ], [ 2, [  ] ], [ 1, [  ] ] ]
     
  
  
    Example  
     gap> c := SCSeriesHomologySphere(2,3,5);;
     gap> SCHomologyEx(c,SCMorseRandom,SmithNormalFormIntegerMat); time;
     [ [ 0, [  ] ], [ 0, [  ] ], [ 0, [  ] ], [ 1, [  ] ] ]
     40
     gap> c := SCSeriesHomologySphere(2,3,5);;
     gap> SCHomologyEx(c,SCMorseRandomLex,SmithNormalFormIntegerMat); time;
     [ [ 0, [  ] ], [ 0, [  ] ], [ 0, [  ] ], [ 1, [  ] ] ]
     40
     gap> c := SCSeriesHomologySphere(2,3,5);;
     gap> SCHomologyEx(c,SCMorseRandomRevLex,SmithNormalFormIntegerMat); time;
     [ [ 0, [  ] ], [ 0, [  ] ], [ 0, [  ] ], [ 1, [  ] ] ]
     44
     gap> c := SCSeriesHomologySphere(2,3,5);;
     gap> SCHomologyEx(c,SCMorseEngstroem,SmithNormalFormIntegerMat); time;
     [ [ 0, [  ] ], [ 0, [  ] ], [ 0, [  ] ], [ 1, [  ] ] ]
     92
     gap> c := SCSeriesHomologySphere(2,3,5);;
     gap> SCHomologyEx(c,SCMorseUST,SmithNormalFormIntegerMat); time;
     [ [ 0, [  ] ], [ 0, [  ] ], [ 0, [  ] ], [ 1, [  ] ] ]
     92
     
  
  
  12.1-14 SCIsSimplyConnected
  
  SCIsSimplyConnected( c )  function
  Returns:  a boolean value upon success, fail otherweise.
  
  Computes  if  the  SCSimplicialComplex  object  c  is  simply connected. The
  algorithm is a heuristic method and is described in [PS15]. Internally calls
  SCIsSimplyConnectedEx (12.1-15).
  
    Example  
     gap> rp2:=SCSurface(1,false);;
     gap> SCIsSimplyConnected(rp2);
     false
     gap> c:=SCBdCyclicPolytope(8,18);;
     gap> SCIsSimplyConnected(c);
     true
     
  
  
  12.1-15 SCIsSimplyConnectedEx
  
  SCIsSimplyConnectedEx( c[, top, tries] )  function
  Returns:  a boolean value upon success, fail otherweise.
  
  Computes  if  the  SCSimplicialComplex  object  c  is  simply connected. The
  optional  boolean  argument  top  determines whether a spanning graph in the
  dual  or  the  primal graph of c will be used for a collapsing sequence. The
  optional  positive integer argument tries determines the number of times the
  algorithm  will  try  to  find  a  collapsing  sequence.  The algorithm is a
  heuristic method and is described in [PS15].
  
    Example  
     gap> rp2:=SCSurface(1,false);;
     gap> SCIsSimplyConnectedEx(rp2);
     false
     gap> c:=SCBdCyclicPolytope(8,18);;
     gap> SCIsSimplyConnectedEx(c);
     true
     
  
  
  12.1-16 SCIsSphere
  
  SCIsSphere( c )  function
  Returns:  a boolean value upon success, fail otherweise.
  
  Determines whether the SCSimplicialComplex object c is a topological sphere.
  In  dimension  ≠  4 the algorithm determines whether c is PL-homeomorphic to
  the  standard  sphere.  In  dimension  4  the  PL type is not specified. The
  algorithm  uses  a  result due to [KS77] stating that, in dimension ≠ 4, any
  simply  connected homology sphere with PL structure is a standard PL sphere.
  The  function  calls  SCIsSimplyConnected  (12.1-14)  which uses a heuristic
  method described in [PS15].
  
    Example  
     gap> c:=SCBdCyclicPolytope(4,20);;
     gap> SCIsSphere(c);
     true
     gap> c:=SCSurface(1,true);;
     gap> SCIsSphere(c);
     false
     
  
  
  12.1-17 SCIsManifold
  
  SCIsManifold( c )  function
  Returns:  a boolean value upon success, fail otherweise.
  
  The  algorithm  is  a  heuristic  method  and is described in [PS15] in more
  detail. Internally calls SCIsManifoldEx (12.1-18).
  
    Example  
     gap> c:=SCBdCyclicPolytope(4,20);;
     gap> SCIsManifold(c);
     true
     
  
  
  12.1-18 SCIsManifoldEx
  
  SCIsManifoldEx( c[, aut, quasi] )  function
  Returns:  a boolean value upon success, fail otherweise.
  
  If  the  boolean argument aut is true the automorphism group is computed and
  only  one  link  per orbit is checked to be a sphere. If aut is not provided
  symmetry  information  is  only  used  if  the automorphism group is already
  known.  If the boolean argument quasi is false the algorithm returns whether
  or  not  c  is  a combinatorial manifold. If quasi is true the 4-dimensional
  links  are not verified to be standard PL 4-spheres and c is a combinatorial
  manifold  modulo  the smooth Poincare conjecture. By default quasi is set to
  false.  The  algorithm  is  a heuristic method and is described in [PS15] in
  more detail.
  
  See  SCBistellarIsManifold  (9.2-6)  for  an alternative method for manifold
  verification.
  
    Example  
     gap> c:=SCBdCyclicPolytope(4,20);;
     gap> SCIsManifold(c);
     true