Lecture by Antoine Deza (Université Paris Sud) On lattice polytopes, convex matroid optimization, and degree sequences of hypergraphs

Jun 25, 2018 | 02:15 PM

We introduce a family of polytopes, called primitive zonotopes, which can be seen as a generalization of the permutahedron of type $B_d$. We discuss connections to the largest diameter of lattice polytopes and to the computational complexity of multicriteria matroid optimization. Complexity results and open questions are also presented. In particular, we answer a question raised in 1986 by Colbourn, Kocay, and Stinson by showing that deciding whether a given sequence is the degree sequence of a 3-hypergraph is computationally prohibitive. Based on joint works with Asaf Levin (Technion), George Manoussakis (Ben Gurion), Syed Meesum (IMSc Chennai), Shmuel Onn (Technion), and Lionel Pounin (Paris XIII).

Time & Location

Jun 25, 2018 | 02:15 PM

Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin room MA 041 (ground floor)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)