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

DOI zum Zitieren der Version auf EPub Bayreuth: https://doi.org/10.15495/EPub_UBT_00009466
URN to cite this document: urn:nbn:de:bvb:703-epub-9466-3

Title data

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.

	Format: PDF Name: SymLexSubsetRS_Preprint.pdf Version: Published Version Available under License Creative Commons BY 4.0: Attribution
	Download (616kB)

Related URLs

• Other URL

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.

Further data

Item Type:	Preprint, postprint
Keywords:	enumeration; subset orbits; symmetry; circuits; cocircuits; triangulations; TOPCOM
Subject classification:	Mathematics Subject Classification Code: 52C35 (05C30)
DDC Subjects:	500 Science > 510 Mathematics
Institutions of the University:	Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematical Economics > Chair Mathematical Economics - Univ.-Prof. Dr. Jörg Rambau Faculties Faculties > Faculty of Mathematics, Physics und Computer Science Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematical Economics
Language:	English
Originates at UBT:	Yes
URN:	urn:nbn:de:bvb:703-epub-9466-3
Date Deposited:	24 Jul 2026 12:41
Last Modified:	28 Jul 2026 05:27
URI:	https://epub.uni-bayreuth.de/id/eprint/9466

Download Statistics

Download Statistics

Download Statistics

Downloads

Downloads per month over past year