next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
SimplicialDecomposability :: shellingOrder

shellingOrder -- finds a shelling of a simplicial complex, if one exists

Synopsis

Description

If S is pure, then definition III.2.1 in [St] is used. That is, S is shellable if its facets can be ordered F1, .., Fn so that the difference in the j-th and j-1-th subcomplex has a unique minimal face, for 2 ≤j ≤n.

If S is non-pure, then definition 2.1 in [BW-1] is used. That is, a simplicial complex S is shellable if the facets of S can be ordered F1, .., Fn such that the intersection of the faces of the first j-1 with the faces of the Fj is pure and dim Fj - 1-dimensional.

This function attempts to build up a shelling order of S recursively. In particular, a depth-first search is used to attempt to build up a shelling order from the bottom, that is, from the first facet in the order.

In the case when S is non-pure, then the search is restricted to the maximal dimension facets remaining to be added. This allows a shelling order in reverse dimension order to be returned whenever S is indeed shellable.

i1 : R = QQ[a..f];
i2 : shellingOrder simplicialComplex {a*b*c*d*e}

o2 = {a*b*c*d*e}

o2 : List
i3 : shellingOrder simplicialComplex {a*b*c, b*c*d, c*d*e}

o3 = {c*d*e, b*c*d, a*b*c}

o3 : List
i4 : shellingOrder simplicialComplex {a*b*c, c*d*e}

o4 = {}

o4 : List
i5 : shellingOrder simplicialComplex {a*b*c, c*d, d*e, e*f, d*f}

o5 = {a*b*c, c*d, d*e, d*f, e*f}

o5 : List
i6 : shellingOrder simplicialComplex {a*b*c, c*d, d*e*f}

o6 = {}

o6 : List

The options Random and Permutation can be used to try to find alternate shelling orders. Random applies a random permutation to the facet list and Permutation applies a supplied permutation to the list. In the non-pure case, the facets are subsequently ordered in reverse dimension order but retaining the ordering within dimensions.

The options Random and Permutation are mutually exclusive.

i7 : S = simplicialComplex {a*b*c, b*c*d, c*d*e, d*e*f};
i8 : shellingOrder S

o8 = {d*e*f, c*d*e, b*c*d, a*b*c}

o8 : List
i9 : shellingOrder(S, Random => true)

o9 = {a*b*c, b*c*d, c*d*e, d*e*f}

o9 : List
i10 : shellingOrder(S, Permutation => {3,2,1,0})

o10 = {a*b*c, b*c*d, c*d*e, d*e*f}

o10 : List

The shelling order is cached if it exists, however, if either option is used, then the cache is ignored.

See also

Ways to use shellingOrder :