Pseudo Unique Sink Orientations

arXiv1704.08481MaRDI QIDQ6286012FDOQ6286012

Authors: Vitor Bosshard, B. Gärtner 

Publication date: 27 April 2017

Abstract: A unique sink orientation (USO) is an orientation of the $n$-dimensional cube graph ($n$-cube) such that every face (subcube) has a unique sink. The number of unique sink orientations is $n^{Theta(2^n)}$. If a cube orientation is not a USO, it contains a pseudo unique sink orientation (PUSO): an orientation of some subcube such that every proper face of it has a unique sink, but the subcube itself hasn't. In this paper, we characterize and count PUSOs of the $n$-cube. We show that PUSOs have a much more rigid structure than USOs and that their number is between $2^{Omega(2^{n-logn})}$ and $2^{O(2^n)}$ which is negligible compared to the number of USOs. As tools, we introduce and characterize two new classes of USOs: border USOs (USOs that appear as facets of PUSOs), and odd USOs which are dual to border USOs but easier to understand.

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Asymptotic enumeration (05A16)

This page was built for publication: Pseudo Unique Sink Orientations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6286012)