randomShelling -- produces a random chain of shellable complexes

Synopsis

Usage:

P=randomShelling(n,m)

P=randomShelling(n,m,k)

P=randomShelling(R,m)

P=randomShelling(R,m,k)
Inputs:
- n, an integer, the number of vertices
- R, a ring, a polynomial ring with a variable for each vertex
- m, an integer, the dimension of the facets
- k, an integer, the number of facets (if omitted, the number will be n choose m+1)
Outputs:
- P, a list, A list of lists of integers. Each list of integers is a facet of the complex and the order is a shelling. If called with a Ring R instead of an integer n, each facet is represented by a square-free monomial instead of a list.

Description

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

The algorithm 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.

Ways to use randomShelling:

randomShelling(Ring,ZZ)
randomShelling(Ring,ZZ,ZZ)
randomShelling(ZZ,ZZ)
randomShelling(ZZ,ZZ,ZZ)

For the programmer

The object randomShelling is a method function.