On the number of term orders (Q1177866)

An admissible order on a finite subset \(Q\subset\mathbb{Q}^ n\) is the restriction to \(Q\) of a linear order on the group \(\mathbb{Q}^ n\). Upper and lower bounds on the number \(\alpha(q)\) of admissible orders on a set \(Q\) are derived, e.g., \[ \alpha(Q)\leq {(\# Q)^{2^ n-2} \over 2^{n- 1}}, \] better estimates are found for special sets like hyperboxes. Algorithms which compute all admissible orders that extend a given binary relation on \(Q\) and their number are presented.