Does this “flipping lexicographic” ordering have a standard name?

2011-02-05T00:34:14Z

I’ve run into the following straightforward variant of lexicographic ordering, and am wondering if it has a standard name. I’ve been calling it the flipping lexicographic ordering, for evident reasons. I could also imagine it getting called the parity lexicographic ordering, but a brief search suggests that that’s used for some slightly different orderings. $\newcommand{\x}{\mathbf{x}} \newcommand{\y}{\mathbf{y}} \newcommand{\N}{\mathbb{N}} \newcommand{\fl}{\mathrm{fl}} \newcommand{\lfl}{\;\sqsubset^\fl\;}$

For sets $\x, \y \in \binom{\N}{m+1}$, write $\x = \{x_0 < \ldots < x_m\}$, $\y = \{y_0 < \ldots < y_m\}$.

Definition. $\x \lfl \y$ if $\x$ and $\y$ differ first in the $i$th place, and

$i$ is even, and $x_i < y_i$; or
$i$ is odd, and $y_i < x_i$. (This is the flip!)

As for ordinary lex, there’s also a nice inductive characterisation: Write $\x = \{x_0\} \cup \x^{\geq 1}$, and $\y = \{y_0\} \cup \y^{\geq 1}$, similarly to above. Then $\x \lfl \y$ if and only if either $x_0 < y_0$, or $x_0 = y_0$ and $\y^{\geq 1} \lfl \x^{\geq 1}$. (Again, note the flip.)

Does this ring any bells with anybody?

(Of course, $\lfl$ has obvious generalisations beyond $\binom{\N}{m+1}$; I’m sticking to that case here partly for definiteness, mainly since that’s the specific case I’m interested in.)

Background: I’ve been playing around with implementing the algorithms from Ross Street’s “The Algebra of Oriented Simplices” (and related papers) in Haskell/Agda, and this ordering turns out to make a computationally convenient stand-in for his $\lhd$ order, in places.

Answer by Greg Kuperberg for Does this “flipping lexicographic” ordering have a standard name?

2011-02-05T20:48:04Z

I found an example in the mathematical literature where the same ordering on words, and more specifically continued fractions, is called "alternating lexicographic" order. I guess that there are other examples too, and that this is name can be considered standard. The term "boustrophedonic order" also appears in the mathematical literature, but it seems to mean something different. The boustrophedonic order on the English alphabet is AZBYCXDW... . In my opinion, calling your ordering boustrophedonic is clever, but I think that "alternating lexicographic" is more consistent as well as more standard, since it is an alternating combination of the lexicographic and colexicographic (or lex and colex) orderings.

Does this “flipping lexicographic” ordering have a standard name? - MathOverflow

Does this “flipping lexicographic” ordering have a standard name?

Answer by Greg Kuperberg for Does this “flipping lexicographic” ordering have a standard name?