25
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Is it obvious that $i<i$ and $j<k$ implies $i<k$, under these conditions? Is this what 3) is supposed to say? I dont think the current version works. $\endgroup$ – Per Alexandersson Jun 13 '14 at 16:59
  • 2
    $\begingroup$ @PerAlexandersson If $i\prec j$ and $j\prec k$ then $v_{ji}=v_{kj}=0$ so by 3) $v_{ki}=0$ then $i\prec k$. In fact 3) is equivalent to transitivity of order. $\endgroup$ – Mostafa Jun 13 '14 at 19:10
  • 3
    $\begingroup$ Ok, so, it is clear that all total orders are in this polytope, and also that every lattice point in this polytope defines a total order. Thus, you need to show that this polytope has only integer vertices, right? Can it be perhaps that this polytope is totally unimodular? That would be a nice property. $\endgroup$ – Per Alexandersson Jun 13 '14 at 20:49
  • 2
    $\begingroup$ Given a total order $t$ we can associate a permutation $P_t$ matrix in an obvious way. There is a theorem by Birkhoff and von Neumann which says that the convex hull of permutation matrices is the set of doubly stochastic matrices. My first idea would be to relate your question with this theorem. However, it's not clear how to do that. Question: Is there a linear map $L$ such that if a vector $(v_{ij})$ comes (by the rule above) from a total order $t$ then its image $L((v_{ij}))$ is the permutation matrix $P_t$? I don't know. $\endgroup$ – Jairo Bochi Jun 17 '14 at 23:35
  • 2
    $\begingroup$ @JairoBochi There can't be such a map. The convex hull of the $v_{ij}$ only has dimension $\binom{n}{2}$; the Birkhoff-von Neumann polytope has dimension $(n-1)^2$. $\endgroup$ – DES-SupportsMonicaAndTransfolk Aug 11 '14 at 16:19
16
+50
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ Nice! The inequalities are valid for any partial order if we put $w_{ij}=0$ when $i,j$ are incomparable, and your example shows that some partial orders are not in the convex hull of total orders. A natural follow-up question is then whether the inequalities describe the convex hull of partial orders. $\endgroup$ – Emil Jeřábek supports Monica Aug 11 '14 at 18:36
  • $\begingroup$ @EmilJeřábek: Good question! I feel this is related to the Birkhoff polytope, and also the convex hull of all Alternating Sign matrices of a fixed size. There is an article by J. Striker, giving the inequalities/equalities for the latter case, it is not a trivial task. So it might be that the inequalities for partial orders can be tricky to find. Perhaps some actual experimentation in Sage is in order... $\endgroup$ – Per Alexandersson Aug 11 '14 at 18:41
  • $\begingroup$ I have a feeling that the number of facets of the total order polytope grows faster than a polynomial in $n$. As a result, the polytope can not be described by relations with a bounded set of indices. $\endgroup$ – Lev Borisov Aug 12 '14 at 2:50
8
$\begingroup$

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$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.