A Universal Construction for Unique Sink Orientations
METADATA ONLY
Loading...
Author / Producer
Date
2022-11-11
Publication Type
Working Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
Unique Sink Orientations (USOs) of cubes can be used to capture the combinatorial structure of many essential algebraic and geometric problems. For various structural and algorithmic questions, including enumeration of USOs and algorithm analysis, it is crucial to have systematic constructions of USOs. While some construction methods for USOs already exist, each one of them has some significant downside. Most of the construction methods have limited expressivity -- USOs with some desired properties cannot be constructed. In contrast, the phase flips of Schurr can construct all USOs, but the operation is not well understood. We were inspired by techniques from cube tilings of space; we expand upon existing techniques in the area to develop generalized rewriting rules for USOs. These rewriting rules are a new construction framework which can be applied to all USOs. The rewriting rules can generate every USO using only USOs of lower dimension. The effect of any specific rewriting rule on an USO is simple to understand. A special case of our construction produces a new elementary transformation of USOs, which we call a partial swap. We further investigate the relationship between partial swaps and phase flips and generalize partial swaps to phase swaps.
Permanent link
Publication status
published
Editor
Book title
Journal / series
Volume
Pages / Article No.
2211.06072
Publisher
Cornell University
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Combinatorics
Organisational unit
08817 - Gärtner, Bernd (Tit.-Prof.) / Gärtner, Bernd (Tit.-Prof.)
Notes
Funding
204320 - Unique Sink Orientations (SNF)