Skip to main content
Notice removed Draw attention by Per Alexandersson
Bounty Ended with David E Speyer's answer chosen by Per Alexandersson
Notice added Draw attention by Per Alexandersson
Bounty Started worth 50 reputation by Per Alexandersson
deleted 6 characters in body
Source Link

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}\leq 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?

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}\leq 1$,

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?

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?

Source Link

Convex hull of total orders

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}\leq 1$,

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?