next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
RandomIdeals :: randomShelling

randomShelling -- produces a random chain of shellable complexes

Synopsis

Description

The function produces a list of facets of a random shellable simplicial complex. The order of the facets is a shelling.

The alogorithm works by choosing one of the previous facets at random, and replacing one of its vertices with a new vertex chosen at random. If the choice meets the criteria of a shelling, that facet is added to list, otherwise it is discarded and the algorithm tries again. The first facet is chosen uniformly at random.

The call randomShelling(n,m) produces a *complete* chain -- that is, a shelling of the m-skeleton of the (n-1)-simplex, with the simplices listed in order, so that any initial subsequence of length d gives a (random) shellable simplicial complex with d facets.

The probability distribution for this random selection is presumably not the uniform one; it would be nice to write a reversible markov chain that could be used with the Metropolis algorithm to produce the uniform distribution, as is done in randomSquareFreeStep, and the randomSquareFreeMonomialIdeal codes

i1 : P = randomShelling(6,3,10)

o1 = {{1, 2, 4, 5}, {1, 2, 3, 5}, {0, 1, 2, 5}, {2, 3, 4, 5}, {1, 3, 4, 5},
     ------------------------------------------------------------------------
     {0, 2, 4, 5}, {0, 2, 3, 5}, {0, 1, 2, 4}, {0, 3, 4, 5}, {0, 1, 2, 3}}

o1 : List
i2 : Q = randomShelling(6,3)

o2 = {{0, 2, 3, 4}, {0, 1, 3, 4}, {0, 2, 3, 5}, {0, 1, 2, 3}, {0, 1, 3, 5},
     ------------------------------------------------------------------------
     {0, 1, 2, 5}, {0, 1, 2, 4}, {1, 2, 3, 4}, {0, 2, 4, 5}, {0, 3, 4, 5},
     ------------------------------------------------------------------------
     {1, 2, 4, 5}, {1, 2, 3, 5}, {0, 1, 4, 5}, {1, 3, 4, 5}, {2, 3, 4, 5}}

o2 : List

Caveat

No claim is made on the distribution of the random chain.

See also

Ways to use randomShelling :