The motivation for the following question comes from finite model theory, but it is not a technical question about this field, and it is particularly directed at people working in other fields.

It happens in mathematics that you can state some property of finite structures (graphs, finite groups etc.) "more easily" using the assumption that the structure comes with a linear order. Often this assumption comes in disguise, e.g. when one considers only permutations of initial segments of the natural numbers instead of arbitrary finite sets. Let me give an example to explain what I mean:

## Example: Parity of permutations

The parity of a permutation $\pi$ of a finite set $X$ is usually defined as the unique number modulo 2 of transpositions into which $\pi$ can be decomposed. A basic and very well known theorem states that this number is even
iff for each linear order on $X$ the number of inversions of $\pi$, i.e. pairs $x,y \in X$ such that $x < y$ but $\pi(x) > \pi(y)$, is even.
The number of inversions is *independent* of the choice of linear order on $X$, i.e. if the number of inversions is even for one linear order on $X$
then this is also the case for each other linear order.
This is the crucial property in which I am interested.

Using the linear order, the original formulation which is pretty complicated from a logical view point (you have to be able to speak about all decompositions of $\pi$ into transpositions) is turned into a statement which is first-order if you admit the use of an arbitrary linear order on $X$ (and, in this particular example, a "modulo 2 counting quantifier" stating that the number of elements satisfying a formula $\phi(x)$ is even). In fact, one can show that the property "having even parity" of permutations cannot be defined by first-order logic without an order, even with the modulo 2 counting quantifier.

## Question

*Do you know of any other non-trivial properties of finite structures
that arise naturally in some field of mathematics, which can be stated
"more easily" as in the example above using a linear order in such a way that,
whether or not a structure satisfies this property is independent of the choice of linear order on this structure?*

allmathematics, there tends to be pleasant formulations of theory whenever you have some kind of monoidal or group-like structure around. $\endgroup$ – Ryan Budney May 28 '13 at 9:52