depth (to backtrack)

By default, \(\text{depth} = \infty\), meaning that the algorithm only backtracks one branching stage each time. Otherwise, if at some stage we need to backtrack, the algorithm will “backjump” to the specified \(\text{depth}\).

How to set depth?

There is one known situation where setting depth to a smaller number would greatly help. That is, when degree_list is highly skewed and size_list is rather uniform.

Let’s pick:

• degree_list = [17, 17, 16, 16, 16, 16, 16, 2, 1, 1, 1, 1]

• size_list = [3] * 40

This is a degree sequence generated by the (undocumented) simplicial_test.sample module:

size_list, degree_list, facets = gen_joint_sequence_from_sizes([3] * 40, p=0.001)

Here, you get the sizes exactly as [3] * 40, and with degs sampled as some sequence, which altogether realizes as the joint degree sequence of the facets. Try it. You’ll know what I mean.

If we do:

st = Test([17, 17, 16, 16, 16, 16, 16, 2, 1, 1, 1, 1], [3] * 40, verbose=False, depth=1e5, width=1e5, cutoff=1e5)
is_simplicial, facets = st.is_simplicial()

It will take a long time (depending on your cutoff) and then tell you that it is not simplicial, which is wrong (because it can be realized by facets). If you increase cutoff to, say, 1e7, it doesn’t help either.

Now let’s set depth=2,

st = Test([17, 17, 16, 16, 16, 16, 16, 2, 1, 1, 1, 1], [3] * 40, verbose=False, depth=2)
is_simplicial, facets_found = st.is_simplicial()

Voila! It takes little time.

print(facets_found)
# Out[*]:
# ((0, 1, 8), (0, 1, 9), (0, 3, 10), (0, 2, 3), (1, 2, 6), (0, 4, 5), (3, 5, 6), (0, 2, 5), (2, 5, 6), (2, 6, 7),
# (0, 1, 4), (0, 1, 5), (2, 3, 6), (0, 3, 6), (1, 3, 6), (4, 5, 6), (2, 4, 6), (1, 4, 6), (1, 5, 6), (1, 4, 5),
# (0, 4, 6), (1, 2, 4), (0, 1, 2), (1, 3, 5), (0, 3, 5), (3, 4, 5), (2, 3, 5), (1, 2, 5), (0, 2, 4), (2, 3, 4),
# (1, 3, 4), (3, 6, 7), (0, 1, 3), (0, 1, 6), (0, 1, 7), (0, 2, 6), (0, 3, 4), (2, 4, 5), (2, 3, 11), (4, 5, 12))