Campus Event Calendar

Event Entry

What and Who

The Birkhoff-Polytope and the hardness of removing vertices

Simon Döring
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Thursday, 30 March 2023
30 Minutes
E1 4


The Birkhoff-Polytope is the convex hull of all permutation matrices embedded in R^{n²}. The polytope is well-studied and has n² many facets. However, many real-world applications require us to look at the convex hull of a certain subset of permutations. We will see that the Birkhoff-Polytope becomes much more complicated whenever we remove a single vertex from its convex hull, and we will prove that such a polytope has at least n² + (n-1)! many facets. Furthermore, we will state a conjecture that connects the Birkhoff-Polytope with a removed vertex to the NP-hard "MaxDAG" problem of finding the maximum DAG in a weighted graph.

Lastly, we will see that the closely related permutahedron has a much simpler structure when removing a single vertex from its convex hull. Here, we can use Yannakakis theorem to construct a compact extension.


Roohani Sharma
+49 681 9325 1116
--email hidden

Virtual Meeting Details

527 278 8807
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at

Roohani Sharma, 03/27/2023 09:14
Roohani Sharma, 03/20/2023 13:18 -- Created document.