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?



Convex hull of total orders
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.


