Symmetric lexicographic symmetric-subset reverse search for the enumeration of circuits, cocircuits, and triangulations up to symmetry

Titelangaben

Rambau, Jörg:
Symmetric lexicographic symmetric-subset reverse search for the enumeration of circuits, cocircuits, and triangulations up to symmetry.
University of Bayreuth
Bayreuth , 2026 . - 102 S.
DOI: https://doi.org/10.15495/EPub_UBT_00009466

Volltext

Link zum Volltext (externe URL):

Weitere URLs

Abstract

This paper introduces, analyzes, and applies variants of the
enumeration framework symmetric lexicographic symmetric-subset
reverse search for the enumeration of symmetric feasible subsets of
a finite set up to symmetry. The framework is implemented in detail
for three applications: cocircuits, circuits, and triangulations of
point configurations. There are two new methods presented and
analyzed to check the lexicographic minimality of a subset in its
orbit: the critical-element method and the modified switch-table
method. Moreover, new application-dependent methods to reduce the
number of necessary enumeration nodes are introduced: rank-pruning
for cocircuits and lex-pruning for triangulations. With a
C++-implementation of the ideas in the software package
TOPCOM, in all three applications known benchmarks can be
computed faster by a large margin. The following new numbers could
be computed for the first time (among others): the number of
cocircuits of the 9-cube, the number of circuits of the 8-cube, and
the number of all triangulations of the product of a 5- and a
3-simplex, as well as the number of all triangulations of a point
configuration in dimension six with 17~points with disconnected
flip-graph (constructed by Santos). Moreover, for Santos's
triangulation it has computationally been checked that its
flip-graph component is indeed purely non-regular. Furthermore, in
another instance in dimension five with 26 points (also constructed
by Santos), a flaw has been detected: Santos's triangulation can be
heuristically flipped to a regular triangulation in the original
point configuration. In a mildly modified version of the point
configuration, the heuristics cannot flip Santos's triangulation to
a regular triangulation anymore.