Symmetric Lexicographic Symmetric-Subset Reverse Search for the Enumeration of Circuits, Cocircuits, and Triangulations up to Symmetry

Jul 16, 2026

Upload by Miles

This paper introduces and analyzes variants of the symmetric lexicographic symmetric-subset reverse search framework for enumerating symmetric feasible subsets of a finite set up to symmetry. The framework is implemented in TOPCOM for cocircuits, circuits, and triangulations of point configurations. Two new lexicographic minimality checks are proposed—critical-element and modified switch-table—and two pruning strategies are added: rank-pruning for cocircuits and lex-pruning for triangulations, enabling substantially faster benchmark computations.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages101

Reading Time4 h 15 min

Introduction

Preliminaries

On Lexicographically Minimal Elements in Subset-Orbits

Algorithms

Variants of Symmetric Lexicographic Subset Reverse Search

New Checks for the Lexicographic Minimality of Subsets

Parallelization

Applications: Common Preliminaries

Applications: Computational Environment

Application I: Cocircuits

Results

Application II: Circuits

Results

Application III: Triangulations

Results

Enhancements

Conclusions

arXiv :2607 .05967v1 [math .CO] 7 Jul 2026 Symmetric lexicographic symmetric-subset reverse search for the enumeration of circuits, cocircuits, and triangulations up to symmetry Preprint 2 Jörg Rambau University of Bayreuth Germany July 8, 2026 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 cocircuitsand 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. Acknowledgement The author is very grateful to Michael Joswig and Lars Kastner who provided the exact chirotope of the regular dodecahedron, computed by polymake. Chirotope data makes possible the exact computation of all triangulations of a point configurations even if there are no rational coordinates for it. Moreover, the author thanks Lukas Kühne who brought the importance of central and centrally symmetric triangulations of the centered full root polytope to the author’s attention. The author also thanks Lisa Lamberti and Komei Fukuda for communicating the (at that time open) question about the number of circuits of the 6-cube, which led to the simultaneous consideration of triangulations and circuits, which was beneficial for both applications. A special thanks goes to Francisco Santos who contributed to the resolution of the seemingly contradictory results on his dimension-five 26-points configuration. Some calculations were performed using the festus-cluster of the Bayreuth Centre for High Performance Computing ([https://www. bzhpc. uni-bayreuth. de](https://www. bzhpc. uni-bayreuth. de)), funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation)– 523317330. The author thanks for the ressources and, in particular, René Meißner for his excellent user support. Contents 1 Introduction 4 2 Preliminaries 9 3 On Lexicographically Minimal Elements in Subset-Orbits 16 4 Algorithms 21 4.1 Variants of Symmetric Lexicographic Subset Reverse Search ........... 22 4.2 New Checks for the Lexicographic Minimality of Subsets ............. 28 4.3 Parallelization ....................................... 48 5 Applications: Common Preliminaries 49 6 Applications: Computational Environment 55 7 Application I: Cocircuits 55 7.1 Specializations ....................................... 56 7.2 Analysis ........................................... 58 7.3 Results ...........................

FAQs

What enumeration problem does the paper target and how is symmetry handled?

The paper targets the enumeration of symmetric feasible subsets of a finite set, treating solutions up to symmetry using a symmetric lexicographic symmetric-subset reverse search framework.

What are the two new methods introduced to verify lexicographic minimality within an orbit?

It presents the critical-element method and a modified switch-table method to check lexicographic minimality of a subset in its orbit.

How does the framework improve performance in the three applications (cocircuits, circuits, triangulations)?

The approach adds pruning strategies—rank-pruning for cocircuits and lex-pruning for triangulations—and uses a C++ implementation in TOPCOM, yielding significantly faster computations on known benchmarks.

Jul 16, 2026

Upload by Miles