Does this “flipping lexicographic” ordering have a standard name? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T19:07:37Z http://mathoverflow.net/feeds/question/54377 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/54377/does-this-flipping-lexicographic-ordering-have-a-standard-name Does this “flipping lexicographic” ordering have a standard name? Peter LeFanu Lumsdaine 2011-02-05T00:34:14Z 2011-02-05T20:48:04Z <p>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 <em>flipping lexicographic</em> ordering, for evident reasons. I could also imagine it getting called the <em>parity lexicographic</em> 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\;}$</p> <p>For sets $\x, \y \in \binom{\N}{m+1}$, write $\x = \{x_0 &lt; \ldots &lt; x_m\}$, $\y = \{y_0 &lt; \ldots &lt; y_m\}$.</p> <p><strong>Definition.</strong> $\x \lfl \y$ if $\x$ and $\y$ differ first in the $i$th place, and </p> <ul> <li>$i$ is even, and $x_i &lt; y_i$; or</li> <li>$i$ is odd, and $y_i &lt; x_i$. (This is the flip!)</li> </ul> <p>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 &lt; y_0$, or $x_0 = y_0$ and $\y^{\geq 1} \lfl \x^{\geq 1}$. (Again, note the flip.)</p> <p>Does this ring any bells with anybody?</p> <p>(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.)</p> <hr> <p><strong>Background:</strong> 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.</p> http://mathoverflow.net/questions/54377/does-this-flipping-lexicographic-ordering-have-a-standard-name/54464#54464 Answer by Greg Kuperberg for Does this “flipping lexicographic” ordering have a standard name? Greg Kuperberg 2011-02-05T20:48:04Z 2011-02-05T20:48:04Z <p>I <a href="http://books.google.com/books?id=3w9eR3u8GN4C&amp;lpg=PA61&amp;ots=xSJTqwK-Yx&amp;dq=%22alternating%20lexicographic%22&amp;hl=fr&amp;pg=PA58#v=onepage&amp;q=%22alternating%20lexicographic%22&amp;f=false" rel="nofollow">found an example</a> 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.</p>