论文标题
独特的下沉方向的通用结构
A Universal Construction for Unique Sink Orientations
论文作者
论文摘要
立方体的独特下沉方向（USO）可用于捕获许多基本代数和几何问题的组合结构。对于各种结构和算法问题，包括对USOS的列举和算法分析，具有系统的系统结构至关重要。虽然已经存在一些USO的施工方法，但每个方法都有一些显着的缺点。大多数施工方法具有有限的表达性 - 无法构建具有一些理想特性的USO。相比之下，Schurr的相位翻转可以构建所有USO，但是该操作尚未得到充分理解。我们的灵感来自空间立方体瓷砖的技术。我们扩展了该领域的现有技术，以制定USOS的广义重写规则。这些重写规则是一个新的施工框架，可以应用于所有USOS。重写规则可以仅使用较低维度的USO生成每个USO。任何特定的重写规则对USO的影响都很容易理解。我们建筑的一种特殊情况会产生USOS的新基本转型，我们称之为部分交换。我们进一步研究了部分掉期和相位翻转之间的关系，并将部分互换推广到相位互换。
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.
