AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

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

Zoom

527 278 8807

passcode not visible

logged in users only

If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.