MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 6 down vote accepted

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.

share|cite|improve this answer
Maybe «boustrophedonic» is too clever :) – Mariano Suárez-Alvarez Feb 5 '11 at 20:53
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.