Editing Weak ordering (section)

===Adjacency structure===

[[File:Permutohedron.svg|thumb|300px|The permutohedron on four elements, a three-dimensional [[convex polyhedron]]. It has 24 vertices, 36 edges, and 14 two-dimensional faces, which all together with the whole three-dimensional polyhedron correspond to the 75 weak orderings on four elements.]]
Unlike for partial orders, the family of weak orderings on a given finite set is not in general connected by moves that add or remove a single order relation to or from a given ordering. For instance, for three elements, the ordering in which all three elements are tied differs by at least two pairs from any other weak ordering on the same set, in either the strict weak ordering or total preorder axiomatizations. However, a different kind of move is possible, in which the weak orderings on a set are more highly connected. Define a {{em|dichotomy}} to be a weak ordering with two equivalence classes, and define a dichotomy to be {{em|compatible}} with a given weak ordering if every two elements that are related in the ordering are either related in the same way or tied in the dichotomy. Alternatively, a dichotomy may be defined as a [[Dedekind cut]] for a weak ordering. Then a weak ordering may be characterized by its set of compatible dichotomies. For a finite set of labeled items, every pair of weak orderings may be connected to each other by a sequence of moves that add or remove one dichotomy at a time to or from this set of dichotomies. Moreover, the [[undirected graph]] that has the weak orderings as its vertices, and these moves as its edges, forms a [[partial cube]].<ref>{{citation|title=Media Theory: Interdisciplinary Applied Mathematics|first1=David|last1=Eppstein|author1-link=David Eppstein|first2=Jean-Claude|last2=Falmagne|author2-link=Jean-Claude Falmagne|first3=Sergei|last3=Ovchinnikov|publisher=Springer|year=2008|at=Section 9.4, Weak Orders and Cubical Complexes, pp. 188–196}}.</ref>

Geometrically, the total orderings of a given finite set may be represented as the vertices of a [[permutohedron]], and the dichotomies on this same set as the facets of the permutohedron. In this geometric representation, the weak orderings on the set correspond to the faces of all different dimensions of the permutohedron (including the permutohedron itself, but not the empty set, as a face). The [[codimension]] of a face gives the number of equivalence classes in the corresponding weak ordering.<ref>{{citation|first=Günter M.|last=Ziegler|authorlink=Günter M. Ziegler|title=Lectures on Polytopes|publisher=Springer|series=Graduate Texts in Mathematics|volume=152|year=1995|page=18}}.</ref> In this geometric representation the partial cube of moves on weak orderings is the graph describing the [[covering relation]] of the [[face lattice]] of the permutohedron.

For instance, for <math>n = 3,</math> the permutohedron on three elements is just a regular hexagon. The face lattice of the hexagon (again, including the hexagon itself as a face, but not including the empty set) has thirteen elements: one hexagon, six edges, and six vertices, corresponding to the one completely tied weak ordering, six weak orderings with one tie, and six total orderings. The graph of moves on these 13 weak orderings is shown in the figure.