The main reference for this section is [Bar11, Section 1.3]. We recall here some important facts and definitions. We consider finite posets as finite topological spaces via the intrinsic topology where the open sets are the downsets. This topology is also known as the Alexandroff topology. A point \(x\in X\) is an up beat point if \(\{y\,:\, y> x\}\) has a minimum. A point \(x\in X\) is a down beat point if \(\{y\,:\, y< x\}\) has a maximum. A point \(x\in X\) is a beat point if it is either an up or a down beat point. A poset is minimal if it has no beat points. A core of a finite poset X is a strong deformation retract which is a minimal poset. The core of a poset is unique up to isomorphism. Moreover, any core of a poset can be reached by exctracting beat points. Two posets are homotopy equivalent if and only if their cores are isomorphic. A poset is contractible if its has only one point. This method of removing beat points to describe the homotopy type of finite posets with the Alexandroff topology was developed by R.E. Stong.
‣ IsBeatPoint( X, x ) | ( operation ) |
Checks if \(x\) is a beat point of \(X\).
gap> P:=PosetByCoveringRelations([1,2,3], [[3,1],[3,2]]); <finite poset of size 3> gap> IsBeatPoint(P,3); false gap> IsBeatPoint(P,1); true
‣ IsUpBeatPoint( X, x ) | ( operation ) |
Checks if \(x\) is an up beat point of \(X\).
gap> P:=PosetByCoveringRelations([1,2,3], [[3,1],[3,2]]); <finite poset of size 3> gap> IsUpBeatPoint(P,1); true
‣ IsDownBeatPoint( X, x ) | ( operation ) |
Checks if \(x\) is a down beat point of \(X\).
gap> P:=PosetByCoveringRelations([1,2,3], [[3,1],[3,2]]); <finite poset of size 3> gap> IsDownBeatPoint(P,1); false
‣ UpBeatPoints( X ) | ( attribute ) |
Returns the list of all the up beat points of the poset.
gap> P:=PosetByCoveringRelations([1,2,3], [[3,1],[3,2]]); <finite poset of size 3> gap> UpBeatPoints(P); [ 1, 2 ]
‣ DownBeatPoints( X ) | ( attribute ) |
Returns the list of all the down beat points of the poset.
gap> P:=PosetByCoveringRelations([1,2,3], [[3,1],[3,2]]); <finite poset of size 3> gap> DownBeatPoints(P); [ ]
‣ BeatPoints( X ) | ( attribute ) |
Returns the list of all the beat points of the poset.
gap> P:=PosetByCoveringRelations([1,2,3], [[3,1],[3,2]]); <finite poset of size 3> gap> BeatPoints(P); [ 1, 2 ]
‣ Core( X ) | ( attribute ) |
Returns the core of \(X\). It also computes the natural inclusion map \(i\colon \mathrm{core}(X) \to X\) and a retraction \(r\colon X \to \mathrm{core}(X)\).
gap> P:=PosetByCoveringRelations([1,2,3], [[3,1],[3,2]]); <finite poset of size 3> gap> Q:=Core(P); <finite poset of size 1> gap> N:=NaturalMaps(Q); [ <order preserving map>, <order preserving map> ] gap> SourceMap(inc) = Q; true gap> TargetMap(inc) = P; true
‣ CoreParallel( X ) | ( attribute ) |
Returns the core of \(X\) by using multiple processor cores. It also computes the natural inclusion map and a retraction. Note: only works on Linux.
gap> G:=AlternatingGroup(8); Alt( [ 1 .. 8 ] ) gap> ApG:=QuillenPoset(G,2); <finite poset of size 2655> gap> start:=Runtime();; Q:=Core(ApG);; Runtime()-start; 90996 gap> start:=Runtime();; R:=CoreParallel(ApG);; Runtime()-start; # Remaining points: 1710 # Remaining points: 1010 184 gap> Set(Q) = Set(R); true
‣ IsContractible( X ) | ( attribute ) |
Checks if the finite poset is contractible.
gap> P:=PosetByCoveringRelations([1,2,3], [[3,1],[3,2]]); <finite poset of size 3> gap> IsContractible(P); true
‣ HomotopyEquivalence( X, Y ) | ( operation ) |
Returns a homotopy equivalence \(X\to Y\) or fail if \(X\) and \(Y\) are not homotopy equivalent.
gap> S:=PosetByCoveringRelations([1,2,3,4], [[3,1],[3,2],[4,1],[4,2]]); <finite poset of size 4> gap> S1:=MinimalFiniteModelSphere(1); <finite poset of size 4> gap> HomotopyEquivalence(S,S1); <order preserving map> gap> P:=PosetByCoveringRelations([1,2,3], [[3,1],[3,2]]); <finite poset of size 3> gap> HomotopyEquivalence(S,P); fail
The reference for this section is [Bar11, Section 4.2]. As before, we consider finite posets with the Alexandroff topology. A point \(x\in X\) is an up weak point if \(\{y\,:\, y> x\}\) is contractible. A point \(x\in X\) is a down weak point if \(\{y\,:\, y< x\}\) is contractible. A point \(x\in X\) is a weak point if it is either an up or a down weak point. A weak core for \(X\) is a subposet of \(X\) without weak poitns and obtained from \(X\) by removing weak points. The poset \(X\) is collapsible if it admits a weak core with only one point. The weak cores of a finite poset do not need to be unique up to isomorphism.
‣ IsWeakPoint( X, x ) | ( operation ) |
Checks if \(x\) is a weak point of \(X\).
gap> P:=PosetByCoveringRelations([1,2,3,4], [[2,1], [3,1], [4,2], [4,3]]); <finite poset of size 4> gap> IsWeakPoint(P,1); true gap> IsBeatPoint(P,1); false
‣ IsUpWeakPoint( X, x ) | ( operation ) |
Checks if \(x\) is an weak point of \(X\).
gap> P:=PosetByCoveringRelations([1,2,3,4], [[2,1], [3,1], [4,2], [4,3]]); <finite poset of size 4> gap> IsUpWeakPoint(P,1); true gap> IsUpBeatPoint(P,1); false
‣ IsDownWeakPoint( X, x ) | ( operation ) |
Checks if \(x\) is a down weak point of \(X\).
gap> P:=PosetByCoveringRelations([1,2,3,4], [[2,1], [3,1], [4,2], [4,3]]); <finite poset of size 4> gap> IsDownWeakPoint(P,4); true gap> IsBeatPoint(P,4); false
‣ WeakPoints( X ) | ( attribute ) |
Return the list of all the weak points of the poset.
gap> P:=PosetByCoveringRelations([1,2,3,4], [[2,1], [3,1], [4,2], [4,3]]); <finite poset of size 4> gap> WeakPoints(P); [ 1, 2, 3, 4 ]
‣ UpWeakPoints( X ) | ( attribute ) |
Return the list of all the up weak points of the poset.
gap> P:=PosetByCoveringRelations([1,2,3,4], [[2,1], [3,1], [4,2], [4,3]]); <finite poset of size 4> gap> UpWeakPoints(P); [ 1, 2, 3 ]
‣ DownWeakPoints( X ) | ( attribute ) |
Return the list of all the down weak points of the poset.
gap> P:=PosetByCoveringRelations([1,2,3,4], [[2,1], [3,1], [4,2], [4,3]]); <finite poset of size 4> gap> DownWeakPoints(P); [ 2, 3, 4 ]
‣ WeakCore( X ) | ( operation ) |
A subposet of \(X\) without weak points obtained from \(X\) by removing weak points. Note that this subposet does not need to be unique up to isomorphism.
gap> P:=PosetByCoveringRelations([1,2,3,4], [[2,1], [3,1], [4,2], [4,3]]); <finite poset of size 4> gap> WeakCore(P); <finite poset of size 1>
‣ MinWeakCore( X ) | ( operation ) |
Returns a weak core of the poset with the minimum possible size. Again, this subposet does not need to be unique up to isomorphism.
gap> W:=TheWallet(); <finite poset of size 11> gap> MinWeakCore(W); <finite poset of size 1>
‣ IsCollapsible( X ) | ( attribute ) |
Checks if the poset is collapsible.
gap> W:=TheWallet(); <finite poset of size 11> gap> IsCollapsible(W); true gap> IsCollapsible(MinimalFiniteModelSphere(2)); false
Colorings were introduced by Barmak and Minian in [BM14]. Given \(X\) a poset and \(A\) an (appropriate) coloring of the Hasse diagram of \(X\), they propose a technique to compute a presentation of the fundamental group of \(X\) (see Theorem 4.4). A \(\textit{coloring}\) or \(\textit{subdiagram}\) \(A\) of \(X\) is a subgraph of the Hasse diagram of \(X\). \(A\) has to satisfy some hypothesis to recover the fundamental group of \(X\). For instance, \(A\) could be a simple-connected diagram containing all the vertices of \(X\). Using colorings, they give a presentation of the fundamental group of \(X\) whose generators are the edges which are not in \(A\) and the relators are given by the \(\textit{digons}\). A digon in a poset \(X\) is a subdiagram which is the union of two different \(\textit{monotonic}\) (or directed) edge-paths from a point \(x\) to a point \(y\) of \(X\). This method can be applied to compute the fundamental group of any regular finite CW-complex by means of its face poset.
‣ FundamentalGroupByColoring( X ) | ( operation ) |
‣ FundamentalGroupByColoring( X, A ) | ( operation ) |
Computes a presentation of the fundamental group of a connected poset X. If specified, A must be a simply-connected subdiagram of X. When A is not specified, a spanning tree in X is chosen arbitrarily. Returns an FpGroup isomorphic to \(\pi_1(X)\). This method is implemented according to the optimized Definition 6.2.1 of [Fer17], to also apply this algorithm to the Andrews-Curtis Conjecture.
gap> W:=TheWallet();; gap> FundamentalGroupByColoring(W); <fp group on the generators [ f1, f2, f3, f4, f5, f6 ]> gap> RelatorsOfFpGroup(G); [ f2, f3, f4, f5*f3^-1, f1*f5*f4^-1, f1*f6 ] gap> SimplifiedFpGroup(G); <fp group on the generators [ ]> gap> A:=SpanningCollapsibleSubdiagram(W);; gap> FundamentalGroupByColoring(W,A); <fp group on the generators [ ]>
‣ SpanningForestHasseDiagram( X ) | ( operation ) |
A spanning forest of the Hasse diagram of X.
‣ RandomSpanningForestHasseDiagram( X ) | ( operation ) |
A random spanning forest of the Hasse diagram of X.
‣ SpanningTreeHasseDiagram( X ) | ( operation ) |
A spanning tree of the Hasse diagram of X. Returns fail if the poset is not connected.
‣ RandomSpanningTreeHasseDiagram( X ) | ( operation ) |
A random spanning tree of the Hasse diagram of X. Returns fail if the poset is not connected.
‣ SpanningCollapsibleSubdiagram( X ) | ( operation ) |
A spanning collapsible subdiagram of the Hasse diagram of X which is maximal (i.e. any addition of a single edge in the subdiagram corresponds to a non-collapsible poset).
‣ RandomSpanningCollapsibleSubdiagram( X ) | ( operation ) |
A random maximal spanning collapsible subdiagram of the Hasse diagram of X.
‣ PathInPoset( X, x, y ) | ( operation ) |
A path from \(x\) to \(y\) in \(X\) of the minimum possible length. Returns fail if \(x\) and \(y\) are not in the same connected component of \(X\).
gap> A:=PosetByCoveringRelations([1..8], [[5,1], [5,2], [6,2], [6,3], [7,3], [7,4], [8,4], [8,1]]); <finite poset of size 8> gap> PathInPoset(A,1,4); [ 1, 8, 4 ] gap> PathInPoset(A,2,4); [ 2, 5, 1, 8, 4 ] gap> B:=PosetByCoveringRelations([1,2],[]); <finite poset of size 2> gap> PathInPoset(B,1,2); fail
‣ ConnectedComponents( X ) | ( operation ) |
The connected components of \(X\), given as a list of subposets.
gap> S1:=MinimalFiniteModelSphere(1);; gap> S2:=MinimalFiniteModelSphere(2);; gap> C:=Coproduct(S1,S2); <finite poset of size 10> gap> pi0:=ConnectedComponents(C); [ <finite poset of size 4>, <finite poset of size 6> ] gap> IsomorphismPosets(S1,pi0[1]); <order preserving map> gap> IsomorphismPosets(S2,pi0[2]); <order preserving map>
Two maps \(f,g\colon X\to Y\) are homotopic if and only if they are in the same connected component of \(Y^X\) which is equivalent to the existence of a fence \(f=h_0\leq h_1 \geq h_2\leq \cdots \geq h_n=g\), see [Bar11, Section 1.2].
‣ Fence( f, g ) | ( operation ) |
Given \(f,g\colon X\to Y\), if \(f\) and \(g\) are homotopic returns a fence (a path in \(Y^X\)) between \(f\) and \(g\) of the minimum possible length. Otherwise it returns fail.
gap> S1:=MinimalFiniteModelSphere(1);; gap> point:=Set(S1)[1];; gap> f:=PosetHomomorphismByImages(S1, S1, List(Set(S1),x->point)); <order preserving map> gap> Fence(f,IdentityMap(S1)); fail gap> A:=ConePoset(S1); <finite poset of size 5> gap> p:=MaximumPoset(A);; gap> g:=PosetHomomorphismByImages(A, A, List(Set(A),x->p)); <order preserving map> gap> Fence(g,IdentityMap(A)); [ <order preserving map>, <order preserving map> ]
‣ AreHomotopic( f, g ) | ( operation ) |
Given \(f,g\colon X\to Y\), returns true if \(f\simeq g\), false otherwise.
gap> S1:=MinimalFiniteModelSphere(1);; gap> point:=Set(S1)[1];; gap> f:=PosetHomomorphismByImages(S1, S1, List(Set(S1),x->point)); <order preserving map> gap> AreHomotopic(f,IdentityMap(S1)); false gap> A:=ConePoset(S1); <finite poset of size 5> gap> p:=MaximumPoset(A);; gap> g:=PosetHomomorphismByImages(A, A, List(Set(A),x->p)); <order preserving map> gap> AreHomotopic(g,IdentityMap(A)); true
generated by GAPDoc2HTML