1
$\begingroup$

I recently became interested in the geometric structure of the Birkhoff polytope since it's connected to a problem that I'm working on. The Wikipedia article states that the Birkhoff polytope has $n^2$ facets, but doesn't explain the partitioning actually works. So I'm wondering how I can determine which vertices (which are permutation matrices) belong to the same facet.

The only clue that I've found comes from the paper "Faces of the Birkhoff Polytope", which says

The facets of the Birkhoff polytope are precisely defined by the inequalities $x_{ij} \geq 0$ for $1 \leq i, j \leq n$.

While this makes sense for continuous points, I'm not sure how to relate the inequality to find the vertices of the facets.

$\endgroup$
2
$\begingroup$

Since the facets lie in the hyperplanes $x_{ij}=0$, the facet corresponding to $x_{ij}$ contains all vertices that have $x_{ij}=0$, i.e. the permutation matrices that correspond to permutations that don't map $j$ to $i$. There are $(n-1)(n-1)!$ of these. (Pick one of the other $n-1$ elements to map $j$ to and then count the possible images of the remaining elements as usual.)

By the way, the Wikipedia article also states that the facets are defined by the non-negativity constraints.

$\endgroup$
  • $\begingroup$ Thanks for the help! Do you happen to know if there is a way to determine the facets of the facets as well? I'm interested in a recursive relationship specifically for the Birkhoff polytope. $\endgroup$ – blink Jun 1 '18 at 23:24
  • $\begingroup$ There was a comment posted here earlier saying that a facet of a facet occurs where two facets intersect. I'm not sure why it was removed, since it seemed correct. $\endgroup$ – blink Jun 2 '18 at 3:21
  • $\begingroup$ I got stuck at the claim quoted in the question. How do the inequalities $x_{ij} \geq 0$ determine the facets of the Birkhoff polytopes? $\endgroup$ – ensbana Mar 9 at 10:44

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.