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


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.

-
Reminds me of boustrophedon. –  Stephen S Feb 5 '11 at 9:16
+1 for 'boustrophedon order' –  ndkrempel Feb 5 '11 at 13:03
The first 4-letter word in the boustrophedonic dictionary is "waxy", since the only things that would beat it are $\{a < x < y < z\}$ and $\{a < w < x < z\}$, neither of which has any anagrams. –  Tracy Hall Feb 5 '11 at 21:04

Ah, thankyou very much — indeed, googling "alternating lexicographic" turns up quite a number of results, which (from a small sample) seem to describe the right ordering. This looks like the answer I was after. Although it now seems so pedestrian compared to ‘flipping’ and ‘boustrophedonic’… –  Peter LeFanu Lumsdaine Feb 5 '11 at 22:39