## Reverse Search Shellability checker ver 0.52

( -> 0.52b is a bug fix from 0.52a. Removed compling errors.)

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:

• How to compile.
• Usage.
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.)

To work within a constant size of memory, our method uses a reverse search. It uses very small memory. It computes exact answer for our question of asking the shellability of simplicial complexes.

Basically, we search an h-assignment (which is equivalent to a shelling) by a depth-first-search like:

• Start from an empty assignment ``* * * ... *''.
• If there is a facet F with k ridges adjacent to the boundary and current hd+1-k is larger than 0, then
• assign d+1-k  to F,
• remove F,
• hd+1-k := hd+1-k-1.
• 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.
(That is, we search a shelling in a backward manner: successively remove a candidate facet for the last one in a shelling.)
We use the reverse search in 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 do as following.
• Set some ordering of facets: F1, F2, ...,Ft.
• Start from an empty assignment ``* * * ... *''.
• Look for a facet F with k ridges adjacent to the boundary and current hd+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,
• hd+1-k := hd+1-k-1.
After this modification, we check which way we can go backwards, that is, look for facets G with
• G is already removed and assigned a label k,
• G intersects with current complex with k ridges,
• current hd+1-k is smaller than the original hd+1-k. (This last condition is always satisfied.)
If there is a facet 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.)
• 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.

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]
In order for the pre-computation part, the maximum dimension for the input complex is fixed and the default of the maximum dimension is 10. This number can be changed by editing the parameter in s_complex.h, if needed.
Masahiro Hachimori
hachi@sk.tsukuba.ac.jp