Convex hull of total orders

Question

Let $n$ be a positive integer and $\prec$ an arbitray total order on $\{1,\dots,n\}$. I associate to this order a vector $v$ with one coordinate for every pair $(i,j)$ s.t. $1\leq i\neq j \leq n$, by this definition: $$v_{ij} = \left\{\begin{array}{cc}1 & i\prec j \\ 0 & i\succ j\end{array}\right. $$

This vector satisfies the following obvious linear inequalities for every distinct triples $1 \leq i,j,k \leq n$:

1)$0\leq v_{ij}$,

2)$v_{ij}+v_{ji}=1$,

3)$v_{ik} \leq v_{ij}+v_{jk} $.

Does these inequalities characterize the convex hull of all vectors associated to total orders?

Answer 1

I claim that this is false for $n=6$. I find it convenient to shift the variables to $w_{ij} = 2 v_{ij} -1$. So the inequalities are $$-1 \leq w_{ij} \leq 1 \quad (1)$$ $$w_{ij} + w_{ji}=0 \quad (2)$$ $$-1 \leq w_{ij} + w_{jk} + w_{k i} \leq 1. \quad (3)$$

Consider the point $x_{12} = x_{34} = x_{56} = 1$, $x_{23} = x_{45} = x_{61} = -1$ and $x_{ij}=0$ in all cases that are not forced from the above by skew symmetry. I claim that $x$ is a vertex.

Inequalities $(1)$ and $(2)$ are clear. For (3), if $(i,j,k)$ are cyclically consecutive modulo $6$, then the sum in the middle is $0$. Otherwise, at most one of the summands is nonzero, so the inequality is clear.

We now must verify that $x_{ij}$ is a vertex. If not, it is in the interior of a line segment, so there is some vector $e_{ij}$ so that $x_{ij} \pm e_{ij}$ is inside the polytope for both choices of sign. Since we must preserve the truth of $(2)$, we have $e_{ij} + e_{ji} = 0$. In order to have $x_{12} \pm e_{12}\leq 1$ for both choices of sign, we must have $e_{12}=0$. Similarly, $e_{i(i+1)}=0$ (with indices cyclic modulo $6$.)

Now, we have $x_{12} + x_{24} + x_{41} = 1$. In order to have $(x_{12} \pm e_{12}) + (x_{24} \pm e_{24}) + (x_{41} \pm e_{41}) \leq 1$ for both choices of sign, we must have $e_{12} + e_{24} + e_{41} =0$. And we already know $e_{12}=0$. So $e_{24} + e_{41}=0$. We can get $12$ linear equations in this manner: $e_{i(i+2)} + e_{(i+2)(i-1)} = 0$ and $e_{i(i+3)} + e_{(i+3) (i+5)}=0$ (indices cyclic modulo $6$). Combined with $e_{ij}=-e_{ji}$, the only solution is that all of the $e$'s are zero.

So $x$ is not at the midpoint of any line segment in the polytope, and is a vertex.

---

Here is a more conceptual explanation. Let $x$ be a point in the polytope. Let $\Gamma$ be the graph with vertex set $[n]$ and an edge $(i,j)$ if $|x_{ij}|=1$. Let $\Delta$ be the $2$-dimensional simplicial complex with a face $(i,j,k)$ if $|x_{ij}+x_{jk} + x_{ki}|=1$. Let $e_{ij}$ be a potential perturbation of $x_{ij}$, as in the solution. If $H^1(\Delta, \mathbb{R})=0$, then inequalities $(3)$ force there to be constants $a_i$ so that $e_{ij} = a_i - a_j$ for every edge $(i,j) \subset \Delta$. If $\Gamma \subset \Delta$, then we must also have $a_i = a_j$ whenever $i$ and $j$ are in the same connected component of $\Gamma$. So, if we can arrange that $\Gamma$ is connected, $H^1(\Delta)=0$ and $\Gamma \subset \Delta$, then we are at a vertex. This was the sort of heuristic I used to find the above example.

Answer 2

Here's a (slightly) different write-up of David's example, combined with Emil's comment: We want to show that the partial order $1<2$, $1<6$, $3<2$, $3<4$, $5<4$, $5<6$ is not a convex combination of total orders. Now the only total orders that can contribute here are the extensions of the given partial order.

We observe that there are only four extensions that make $4<1$, namely $$ 3<5<4<1<2<6 , $$ and here we may switch $3,5$ and/or $2,6$. Since initially $1, 4$ were not comparable (so $x_{14}=0$), these four total orders must get combined weight $1/2$ in the convex combination we are looking for.

We can now similarly consider the (again four) total order extensions that make $6<3$, and again these must get combined weight $1/2$. We have used up all our coefficients, but all orders considered so far have $5<2$, so this will not work (since $x_{25}=0$).