On the number of term orders

By an admissible order on a finite subsetQ of ⁿ we mean the restriction toQ of a linear order on ⁿ compatible with the group structure of ⁿ and such that ⁿ is contained in the positive cone of the order. We first derive upper and lower bounds on the number of admissible orders on a given setQ in terms of the dimensionn and the cardinality ofQ. Better estimates are possible if the setQ enjoys symmetry properties and in the case whereQ is a discrete hyperbox of the form In the latter case, we also give asymptotic results asd_k for fixedn. We finally present algorithms which compute the set of admissible orders that extend a given binary relation onQ and their number. The algorithms are useful in connection with the construction of universal Gröbner bases.AMS Classification: primary 06F20 secondary 06-04, 11N25