Since two combinatorial manifolds are already considered distinct to each other as soon as they are not combinatorially isomorphic, a topological PL-manifold is represented by a whole class of combinatorial manifolds. Thus, a frequent question when working with combinatorial manifolds is whether two such objects are PL-homeomorphic or not. One possibility to approach this problem, i. e. to find combinatorially distinct members of the class of a PL-manifold, is a heuristic algorithm using the concept of bistellar moves.
Definition (Bistellar moves [Pac87])
Let M be a combinatorial d-manifold (d-pseudomanifold), γ = ⟨ v_0 , ... , v_k ⟩ a k-face and δ = ⟨ w_0 , ... , w_d-k ⟩ a (d-k+1)-tuple of vertices of M that does not span a (d-k)-face in M, 0 ≤ k ≤ d, such that { v_0 , ..., v_k } ∩ { w_0 , ... , w_d-k } = ∅ and { v_0 , ... , v_k, w_0 , ... w_k-d } spans exactly d-k+1 facets. Then the operation
κ_(γ,δ) ( M ) = M ∖ (γ ⋆ ∂ δ) ∪ (∂ γ ⋆ δ)
is called a bistellar (d-k)-move.
In other words: If there exists a bouquet D ⊂ M of d-k+1 facets on a subset of vertices W ⊂ V of order d+2 with a common k-face γ and the complement δ of the vertices of γ in W does not span a (d-k)-face in M we can remove D and replace it by a bouquet of k+1 facets E ⊂ M with vertex set W with a common face spanned by δ. By construction ∂ D = ∂ E and the altered complex is again a combinatorial d-manifold (d-pseudomanifold). See Fig. 11 for a bistellar 1-move of a 2-dimensional complex, see Fig. 12 for all bistellar moves in dimension 3.
A bistellar 0-move is a stellar subdivision, i. e. the subdivision of a facet δ into d+1 new facets by introducing a new vertex at the center of δ (cf. Fig. 12 on the left). In particular, the vertex set of a combinatorial manifold (pseudomanifold) is not invariant under bistellar moves. For any bistellar (d-k)-move κ_(γ,δ) we have an inverse bistellar k-move κ^-1_(γ,δ) = κ_(δ,γ) such that κ_(δ,γ) ( κ_(γ,δ) (M)) = M. If for two combinatorial manifolds M and N there exist a sequence of bistellar moves that transforms one into the other, M and N are called bistellarly equivalent. So far bistellar moves are local operations on combinatorial manifolds that change its combinatorial type. However, the strength of the concept in combinatorial topology is a consequence of the following
Theorem (Bistellar moves [Pac87])
Two combinatorial manifolds (pseudomanifolds) M and N are PL homeomorphic if and only if they are bistellarly equivalent.
Unfortunately Pachners theorem does not guarantee that the search for a connecting sequence of bistellar moves between M and N terminates. Hence, using bistellar moves, we can not prove that M and N are not PL-homeomorphic. However, there is a very effective simulated annealing approach that is able to give a positive answer in a lot of cases. The heuristic was first implemented by Bjoerner and Lutz in [BL00]. The functions presented in this chapter are based on this code which can be used for several tasks:
In many cases the heuristic reduces a given triangulation but does not reach a minimal triangulation after a reasonable amount of flips. Thus, we usually can not expect the algorithm to terminate. However, in some cases the program normally stops after a small number of flips:
Technical note: Since bistellar flips do not respect the combinatorial properties of a complex, no attention to the original vertex labels is payed, i. e. the flipped complex will be relabeled whenever its vertex labels become different from the standard labeling (for example after every reverse 0-move).
‣ SCBistellarOptions | ( global variable ) |
Record of global variables to adjust output an behavior of bistellar moves in SCIntFunc.SCChooseMove (9.2-4) and SCReduceComplexEx (9.2-14) respectively.
BaseRelaxation: determines the length of the relaxation period. Default: 3
BaseHeating: determines the length of the heating period. Default: 4
Relaxation: value of the current relaxation period. Default: 0
Heating: value of the current heating period. Default: 0
MaxRounds: maximal over all number of bistellar flips that will be performed. Default: 500000
MaxInterval: maximal number of bistellar flips that will be performed without a change of the f-vector of the moved complex. Default: 100000
Mode: flip mode, 0=reducing, 1=comparing, 2=reduce as sub-complex, 3=randomize. Default: 0
WriteLevel: 0=no output, 1=storing of every vertex minimal complex to user library, 2=e-mail notification. Default: 1
MailNotifyIntervall: (minimum) number of seconds between two e-mail notifications. Default: 24 ⋅ 60 ⋅ 60 (one day)
MaxIntervalIsManifold: maximal number of bistellar flips that will be performed without a change of the f-vector of a vertex link while trying to prove that the complex is a combinatorial manifold. Default: 5000
MaxIntervalRandomize := 50: number of flips performed to create a randomized sphere. Default: 50
gap> SCBistellarOptions.BaseRelaxation; 3 gap> SCBistellarOptions.BaseHeating; 4 gap> SCBistellarOptions.Relaxation; 0 gap> SCBistellarOptions.Heating; 0 gap> SCBistellarOptions.MaxRounds; 500000 gap> SCBistellarOptions.MaxInterval; 100000 gap> SCBistellarOptions.Mode; 0 gap> SCBistellarOptions.WriteLevel; 0 gap> SCBistellarOptions.MailNotifyInterval; 86400 gap> SCBistellarOptions.MaxIntervalIsManifold; 5000 gap> SCBistellarOptions.MaxIntervalRandomize; 50
‣ SCEquivalent( complex1, complex2 ) | ( method ) |
Returns: true or false upon success, fail or a list of type [ fail, SCSimplicialComplex, Integer, facet list] otherwise.
Checks if the simplicial complex complex1 (which has to fulfill the weak pseudomanifold property with empty boundary) can be reduced to the simplicial complex complex2 via bistellar moves, i. e. if complex1 and complex2 are PL-homeomorphic. Note that in general the problem is undecidable. In this case fail is returned.
It is recommended to use a minimal triangulation complex2 for the check if possible.
Internally calls SCReduceComplexEx (9.2-14) (complex1,complex2,1,SCIntFunc.SCChooseMove);
gap> SCBistellarOptions.WriteLevel:=0;; # do not save complexes to disk gap> obj:=SC([[1,2],[2,3],[3,4],[4,5],[5,6],[6,1]]);; # hexagon gap> refObj:=SCBdSimplex(2);; # triangle as a (minimal) reference object gap> SCEquivalent(obj,refObj); #I SCReduceComplexEx: complexes are bistellarly equivalent. true
‣ SCExamineComplexBistellar( complex ) | ( method ) |
Returns: simplicial complex passed as argument with additional properties upon success, fail otherwise.
Computes the face lattice, the f-vector, the AS-determinant, the dimension and the maximal vertex label of complex.
gap> obj:=SC([[1,2],[2,3],[3,4],[4,5],[5,6],[6,1]]); <SimplicialComplex: unnamed complex 7 | dim = 1 | n = 6> gap> SCExamineComplexBistellar(obj); <SimplicialComplex: unnamed complex 7 | dim = 1 | n = 6>
‣ SCIntFunc.SCChooseMove( dim, moves ) | ( function ) |
Returns: a bistellar move, i. e. a pair of lists upon success, fail otherwise.
Since the problem of finding a bistellar flip sequence that reduces a simplicial complex is undecidable, we have to use an heuristic approach to choose the next move.
The implemented strategy SCIntFunc.SCChooseMove first tries to directly remove vertices, edges, i-faces in increasing dimension etc. If this is not possible it inserts high dimensional faces in decreasing co-dimension. To do this in an efficient way a number of parameters have to be adjusted, namely SCBistellarOptions.BaseHeating and SCBistellarOptions.BaseRelaxation. See SCBistellarOptions (9.2-1) for further options.
If this strategy does not work for you, just implement a customized strategy and pass it to SCReduceComplexEx (9.2-14).
See SCRMoves (9.2-10) for further information.
‣ SCIsKStackedSphere( complex, k ) | ( method ) |
Returns: a list upon success, fail otherwise.
Checks, whether the given simplicial complex complex that must be a PL d-sphere is a k-stacked sphere with 1≤ k≤ ⌊fracd+22⌋ using a randomized algorithm based on bistellar moves (see [Eff11b], [Eff11a]). Note that it is not checked whether complex is a PL sphere -- if not, the algorithm will not succeed. Returns a list upon success: the first entry is a boolean, where true means that the complex is k-stacked and false means that the complex cannot be k-stacked. A value of -1 means that the question could not be decided. The second argument contains a simplicial complex that, in case of success, contains the trigangulated (d+1)-ball B with ∂ B=S and operatornameskel_d-k(B)=operatornameskel_d-k(S), where S denotes the simplicial complex passed in complex.
Internally calls SCReduceComplexEx (9.2-14).
gap> SCLib.SearchByName("S^4~S^1");;
gap> c:=SCLib.Load(last[1][1]);;
gap> l:=SCLink(c,1);
<SimplicialComplex: lk([ 1 ]) in S^4~S^1 (VT) | dim = 4 | n = 12>
gap> SCIsKStackedSphere(l,1);
#I SCIsKStackedSphere: checking if complex is a 1-stacked sphere...
#I SCIsKStackedSphere: try 1/1
#I SCIsKStackedSphere: complex is a 1-stacked sphere.
[ true,
<SimplicialComplex: Filled 1-stacked sphere (lk([ 1 ]) in S^4~S^1 (VT)) | di\
m = 5 | n = 12> ]
‣ SCBistellarIsManifold( complex ) | ( method ) |
Returns: true or false upon success, fail otherwise.
Tries to prove that a closed simplicial d-pseudomanifold is a combinatorial manifold by reducing its vertex links to the boundary of the d-simplex.
false is returned if it can be proven that there exists a vertex link which is not PL-homeomorphic to the standard PL-sphere, true is returned if all vertex links are bistellarly equivalent to the boundary of the simplex, fail is returned if the algorithm does not terminate after the number of rounds indicated by SCBistellarOptions.MaxIntervallIsManifold.
Internally calls SCReduceComplexEx (9.2-14) (link,SCEmpty(),0,SCIntFunc.SCChooseMove); for every link of complex. Note that false is returned in case of a bounded manifold.
See SCIsManifoldEx (12.1-18) and SCIsManifold (12.1-17) for alternative methods for manifold verification.
gap> c:=SCBdCrossPolytope(3);; gap> SCBistellarIsManifold(c); true
‣ SCIsMovableComplex( complex ) | ( method ) |
Returns: true or false upon success, fail otherwise.
Checks if a simplicial complex complex can be modified by bistellar moves, i. e. if it is a pure simplicial complex which fulfills the weak pseudomanifold property with empty boundary.
gap> c:=SCBdCrossPolytope(3);; gap> SCIsMovableComplex(c); true
Complex with non-empty boundary:
gap> c:=SC([[1,2],[2,3],[3,4],[3,1]]);; gap> SCIsMovableComplex(c); false
‣ SCMove( c, move ) | ( method ) |
Returns: simplicial complex of type SCSimplicialComplex upon success, fail otherwise.
Applies the bistellar move move to a simplicial complex c. move is given as a (r+1)-tuple together with a (d+1-r)-tuple if d is the dimension of c and if move is a r-move. See SCRMoves (9.2-10) for detailed information about bistellar r-moves.
Note: move and c should be given in standard labeling to ensure a correct result.
gap> obj:=SC([[1,2],[2,3],[3,4],[4,1]]);
<SimplicialComplex: unnamed complex 5 | dim = 1 | n = 4>
gap> moves:=SCMoves(obj);
[ [ [ [ 1, 2 ], [ ] ], [ [ 1, 4 ], [ ] ], [ [ 2, 3 ], [ ] ],
[ [ 3, 4 ], [ ] ] ],
[ [ [ 1 ], [ 2, 4 ] ], [ [ 2 ], [ 1, 3 ] ], [ [ 3 ], [ 2, 4 ] ],
[ [ 4 ], [ 1, 3 ] ] ] ]
gap> obj:=SCMove(obj,last[2][1]);
<SimplicialComplex: unnamed complex 6 | dim = 1 | n = 3>
‣ SCMoves( complex ) | ( method ) |
Returns: a list of list of pairs of lists upon success, fail otherwise.
See SCRMoves (9.2-10) for further information.
gap> c:=SCBdCrossPolytope(3);;
gap> moves:=SCMoves(c);
[ [ [ [ 1, 3, 5 ], [ ] ], [ [ 1, 3, 6 ], [ ] ], [ [ 1, 4, 5 ], [ ] ],
[ [ 1, 4, 6 ], [ ] ], [ [ 2, 3, 5 ], [ ] ], [ [ 2, 3, 6 ], [ ] ],
[ [ 2, 4, 5 ], [ ] ], [ [ 2, 4, 6 ], [ ] ] ],
[ [ [ 1, 3 ], [ 5, 6 ] ], [ [ 1, 4 ], [ 5, 6 ] ], [ [ 1, 5 ], [ 3, 4 ] ],
[ [ 1, 6 ], [ 3, 4 ] ], [ [ 2, 3 ], [ 5, 6 ] ], [ [ 2, 4 ], [ 5, 6 ] ],
[ [ 2, 5 ], [ 3, 4 ] ], [ [ 2, 6 ], [ 3, 4 ] ], [ [ 3, 5 ], [ 1, 2 ] ],
[ [ 3, 6 ], [ 1, 2 ] ], [ [ 4, 5 ], [ 1, 2 ] ], [ [ 4, 6 ], [ 1, 2 ] ] ]
, [ ] ]
‣ SCRMoves( complex, r ) | ( method ) |
Returns: a list of pairs of the form [ list, list ], fail otherwise.
A bistellar r-move of a d-dimensional combinatorial manifold complex is a r-face m_1 together with a d-r-tuple m_2 where m_1 is a common face of exactly (d+1-r) facets and m_2 is not a face of complex.
The r-move removes all facets containing m_1 and replaces them by the (r+1) faces obtained by uniting m_2 with any subset of m_1 of order r.
The resulting complex is PL-homeomorphic to complex.
gap> c:=SCBdCrossPolytope(3);; gap> moves:=SCRMoves(c,1); [ [ [ 1, 3 ], [ 5, 6 ] ], [ [ 1, 4 ], [ 5, 6 ] ], [ [ 1, 5 ], [ 3, 4 ] ], [ [ 1, 6 ], [ 3, 4 ] ], [ [ 2, 3 ], [ 5, 6 ] ], [ [ 2, 4 ], [ 5, 6 ] ], [ [ 2, 5 ], [ 3, 4 ] ], [ [ 2, 6 ], [ 3, 4 ] ], [ [ 3, 5 ], [ 1, 2 ] ], [ [ 3, 6 ], [ 1, 2 ] ], [ [ 4, 5 ], [ 1, 2 ] ], [ [ 4, 6 ], [ 1, 2 ] ] ]
‣ SCRandomize( complex[[, rounds][, allowedmoves]] ) | ( function ) |
Returns: a simplicial complex upon success, fail otherwise.
Randomizes the given simplicial complex complex via bistellar moves chosen at random. By passing the optional array allowedmoves, which has to be a dense array of integer values of length SCDim(complex), certain moves can be allowed or forbidden in the proccess. An entry allowedmoves[i]=1 allows (i-1)-moves and an entry allowedmoves[i]=0 forbids (i-1)-moves in the randomization process.
With optional positive integer argument rounds, the amount of randomization can be controlled. The higher the value of rounds, the more bistellar moves will be randomly performed on complex. Note that the argument rounds overrides the global setting SCBistellarOptions.MaxIntervalRandomize (this value is used, if rounds is not specified). Internally calls SCReduceComplexEx (9.2-14).
gap> c:=SCRandomize(SCBdSimplex(4)); <SimplicialComplex: Randomized S^3_5 | dim = 3 | n = 16> gap> c.F; [ 16, 65, 98, 49 ]
‣ SCReduceAsSubcomplex( complex1, complex2 ) | ( method ) |
Returns: SCBistellarOptions.WriteLevel=0: a triple of the form [ boolean, simplicial complex, rounds performed ] upon termination of the algorithm.
SCBistellarOptions.WriteLevel=1: A library of simplicial complexes with a number of complexes from the reducing process and (upon termination) a triple of the form [ boolean, simplicial complex, rounds performed ].
SCBistellarOptions.WriteLevel=2: A mail in case a smaller version of complex1 was found, a library of simplicial complexes with a number of complexes from the reducing process and (upon termination) a triple of the form [ boolean, simplicial complex, rounds performed ].
Returns fail upon an error.
Reduces a simplicial complex complex1 (satisfying the weak pseudomanifold property with empty boundary) as a sub-complex of the simplicial complex complex2.
Main application: Reduce a sub-complex of the cross polytope without introducing diagonals.
Internally calls SCReduceComplexEx (9.2-14) (complex1,complex2,2,SCIntFunc.SCChooseMove);
gap> c:=SCFromFacets([[1,3],[3,5],[4,5],[4,1]]);; gap> SCBistellarOptions.WriteLevel:=0;; # do not save any complexes gap> SCReduceAsSubcomplex(c,SCBdCrossPolytope(3)); [ true, <SimplicialComplex: unnamed complex 36 | dim = 1 | n = 3>, 1 ]
‣ SCReduceComplex( complex ) | ( method ) |
Returns: SCBistellarOptions.WriteLevel=0: a triple of the form [ boolean, simplicial complex, rounds performed ] upon termination of the algorithm.
SCBistellarOptions.WriteLevel=1: A library of simplicial complexes with a number of complexes from the reducing process and (upon termination) a triple of the form [ boolean, simplicial complex, rounds performed ].
SCBistellarOptions.WriteLevel=2: A mail in case a smaller version of complex1 was found, a library of simplicial complexes with a number of complexes from the reducing process and (upon termination) a triple of the form [ boolean, simplicial complex, rounds performed ].
Returns fail upon an error..
Reduces a pure simplicial complex complex satisfying the weak pseudomanifold property via bistellar moves. Internally calls SCReduceComplexEx (9.2-14) (complex,SCEmpty(),0,SCIntFunc.SCChooseMove);
gap> obj:=SC([[1,2],[2,3],[3,4],[4,5],[5,6],[6,1]]);; # hexagon gap> SCBistellarOptions.WriteLevel:=0;; # do not save complexes gap> tmp := SCReduceComplex(obj); [ true, <SimplicialComplex: unnamed complex 27 | dim = 1 | n = 3>, 3 ]
‣ SCReduceComplexEx( complex, refComplex, mode, choosemove ) | ( function ) |
Returns: SCBistellarOptions.WriteLevel=0: a triple of the form [ boolean, simplicial complex, rounds ] upon termination of the algorithm.
SCBistellarOptions.WriteLevel=1: A library of simplicial complexes with a number of complexes from the reducing process and (upon termination) a triple of the form [ boolean, simplicial complex, rounds ].
SCBistellarOptions.WriteLevel=2: A mail in case a smaller version of complex1 was found, a library of simplicial complexes with a number of complexes from the reducing process and (upon termination) a triple of the form [ boolean, simplicial complex, rounds ].
Returns fail upon an error.
Reduces a pure simplicial complex complex satisfying the weak pseudomanifold property via bistellar moves mode = 0, compares it to the simplicial complex refComplex (mode = 1) or reduces it as a sub-complex of refComplex (mode = 2).
choosemove is a function containing a flip strategy, see also SCIntFunc.SCChooseMove (9.2-4).
The currently smallest complex is stored to the variable minComplex, the currently smallest f-vector to minF. Note that in general the algorithm will not stop until the maximum number of rounds is reached. You can adjust the maximum number of rounds via the property SCBistellarOptions (9.2-1). The number of rounds performed is returned in the third entry of the triple returned by this function.
This function is called by
SCReduceComplex (9.2-13),
SCEquivalent (9.2-2),
SCReduceAsSubcomplex (9.2-12),
SCBistellarIsManifold (9.2-6).
SCRandomize (9.2-11).
Please see SCMailIsPending (15.2-3) for further information about the email notification system in case SCBistellarOptions.WriteLevel is set to 2.
gap> c:=SCBdCrossPolytope(4);;
gap> SCBistellarOptions.WriteLevel:=0;; # do not save complexes
gap> SCReduceComplexEx(c,SCEmpty(),0,SCIntFunc.SCChooseMove);
[ true, <SimplicialComplex: unnamed complex 13 | dim = 3 | n = 5>, 7 ]
gap> SCReduceComplexEx(c,SCEmpty(),0,SCIntFunc.SCChooseMove);
[ true, <SimplicialComplex: unnamed complex 18 | dim = 3 | n = 5>, 9 ]
gap> SCMailSetAddress("johndoe@somehost");
true
gap> SCMailIsEnabled();
true
gap> SCReduceComplexEx(c,SCEmpty(),0,SCIntFunc.SCChooseMove);
[ true, <SimplicialComplex: unnamed complex 23 | dim = 3 | n = 5>, 7 ]
Content of sent mail:
Greetings master, this is simpcomp 0.0.0 running on comp01.maths.fancytown.edu I have been working hard for 0 seconds and have a message for you, see below. #### START MESSAGE #### SCReduceComplex: Computed locally minimal complex after 7 rounds: [SimplicialComplex Properties known: Boundary, Chi, Date, Dim, F, Faces, Facets, G, H, HasBoundary, Homology, IsConnected, IsManifold, IsPM, Name, SCVertices, Vertices. Name="ReducedComplex_5_vertices_7" Dim=3 Chi=0 F=[ 5, 10, 10, 5 ] G=[ 0, 0 ] H=[ 1, 1, 1, 1 ] HasBoundary=false Homology=[ [ 0, [ ] ], [ 0, [ ] ], [ 0, [ ] ], [ 1, [ ] ] ] IsConnected=true IsPM=true /SimplicialComplex] ##### END MESSAGE ##### That's all, I hope this is good news! Have a nice day.
‣ SCReduceComplexFast( complex ) | ( function ) |
Returns: a simplicial complex upon success, fail otherwise.
Same as SCReduceComplex (9.2-13), but calls an external binary provided with the simpcomp package.
generated by GAPDoc2HTML