# 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.