Skip to main content
2 of 5
added 775 characters in body
David E Speyer
  • 156.3k
  • 14
  • 422
  • 763

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.

David E Speyer
  • 156.3k
  • 14
  • 422
  • 763