( -> 0.52a is a small fix from 0.52, just for letting new versions of gcc work.)

This version implemented M-sequence check in each step.

In most case in dimensions larger than 4 this makes the running time tremendously shorter, but in dimension 3 or smaller cases Ver.0.43 works faster than this version.

Here is an old version:

rsshell-0.43.tar.gz

- How to compile.

Untar the downloaded file and just type`make`, then you will have the binary`rsshell`. - Usage.

`% ./rsshell <datafile>`

Current implementation contains only pure cases. So you can try this checker only with datafiles of pure simplicial complexes. - Data file.

In the data file, we express the simplicial complex by a list of simplices. The vertices are numbered by integers. For example, a face with four vertices 1, 3, 4, 5 is expressed as follows.1 3 4 5

An example of a simplicial complex is as follows.1 2 3 4 1 3 5 4 1 4 5 8 2 3 5 4 3 5 4 9

The example above shows a 3-dimensional simplicial complex with 5 facets. (This example is shellable.)

[Brief description]

The program `rsshell` is a program (written in C)
to check shellability of
a given (pure) simplicial complex.

The method is to search a ``shellable *h*-assignment''
(discussed by Sonoko Moriyama)
by using a kind of reverse search.
(This idea is essentially suggested by Jörg Rambau in a short conversation during ICM2002.
I thank him very much.)

Primitive simple-minded implementation of ``finding shellable *h*-assignments'' method
is done by Moriyama-Nagai-Imai (presented at ICMS2002), which in a search tree trys to keep all
intermediate steps in a hash table in order to avoid re-searching.
(Of course it is impossible to keep all intermediate steps because the
size of the memory is finite.
To keep the table small enough, they used some heuristical methods to discard
some information of already-checked nodes, that is, their atempt of
avoiding re-searching is imperfect.
By this they dared claim their implementation is ``space-efficient''
although it involves a quite large (c.a.64M) hash table!)

Moreover, their implementation uses a random-number table for the coding
of the entries of the hash-table.
In short, in their implementation
each h-assignment is encoded into a constant-bit number so that,
*they expect*, different ones are encoded into different numbers.
Of course this makes their implementation to be just a probabilistic checker:
If it answers nonshellable, it means that it is nonshellable ** in high
probability**.

(I don't know for what reason they gave up to be exact. Maybe in order to reduce the size of the hash table, or to make the computation faster and easier. This is not a good idea at all if one really wants to know the shellability of the examples he constructed, even if the probability of error is very small. The probability of error is not estimated in their paper (even no mentioning that it is probabilistic). If the size of the complex is small, it is very small. If the size gets larger, it tends to 1.)

On the other hand, our method uses no such tables during the searching. Instead it just uses a reverse search. It uses very small memory. Of course it computes exact answer for our question of asking the shellability of simplicial complexes.

The search method used in M-N-I implementation is a depth-first-search as follows. (Although their description has a little bit different look.)

- Start from an empty assignment ``* * * ... *''.
- If there is a facet
*F*with*k*ridges adjacent to the boundary and current*h*_{d+1-k}is larger than 0, then- assign
*d*+1-*k*to*F*, - remove
*F*, *h*_{d+1-k}:=*h*_{d+1-k}-1.

- assign
- If all facets are assigned, the assignment we get is a shellable
*h*-assignment. This mean the simplicial complex is shellable.

If we get stuck before it (i.e., if current assignment is*inappropriate*), backtrack one step.

If no shellable assignment is found, the complex is nonshellable.

In this depth-first searching, the M-N-I implementation tries to keep all inappropriate assignments in a hash table to avoid re-checking of already-checked nodes during the search.

What we propose is that there is no need of using such a heuristical
way at all if we use the *reverse search* for this depth-first search.
For this we assume some fixed ordering of facets and for each assignment
we define its real parent to be the lexicographically smallest assignment.
(Here lexicographic ordering is based on an order relation `assigned'<`not assigned'.)

In precise, what we need to do is the following.

- Set some ordering of facets:
*F*_{1},*F*_{2}, ...,*F*._{t} - Start from an empty assignment ``* * * ... *''.
- Look for a facet
*F*with*k*ridges adjacent to the boundary and current*h*_{d+1-k}is larger than 0. If there are more than one candidates, we check them from the smallest one. Then- assign
*d*+1-*k*to*F*, - remove
*F*, *h*_{d+1-k}:=*h*_{d+1-k}-1.

*G*with*G*is already removed and assigned a label*k*,*G*intersects with current complex with*k*ridges,- current
*h*_{d+1-k}is smaller than the original*h*_{d+1-k}. (This last condition is always satisfied.)

*G*satisfying these condition and larger than*F*, we conclude that we already check this situation, so cancell the removal of*F*and check the next candidate.

(In short, we check the old assignment is the lexicographically smallest parent of the new or not.) - assign
- If all facets are assigned, the assignment we get is a shellable
*h*-assignment. This mean the simplicial complex is shellable.

If we get stuck before it (i.e., if current assignment is*inappropriate*), backtrack one step. For this we cancell the largest facet among candidates to be cancelled.

If no shellable assignment is found, the complex is nonshellable.

In this searching method, what we need to keep is only the current assignment,
thus we need no hash table nor search path to the current status.
That is, this method is *really* ``space-efficient''.

In the implementation of `rsshell`, we keep a list of
cancellable facets and the maximum one among them in each step in order
to make the computation efficient.

[Remark]

Currently

This restriction will be fixed in some later version.

Masahiro Hachimori