Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, June 2, 2014

Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041

Lecture - 14:15

Martin Henk - Universität Magdeburg

Polytopes, successive minima, and the Gaussian divergence theorem

We show that polytopes with centroid at the origin satisfy the so-called subspace-concentration-condition (scd). This has several consequences:
a) the "U-conjecture" regarding cone-volume measures of polytopes is correct,
b) the scd is a necessary condition for the (in general still open) logarithmic Minkowski problem. This extends partially recent results obtained in the symmetric setting by Böröczky et al. [1],
c) the sum of the roots of an Ehrhart polynomial of a lattice polytope is bounded from above by the sum of its Minkowskian successive minima.
The main tool for the proof of the scd is a polytopal version of the Gaussian divergence theorem for a special log-concave function.

Most of the presented results are part of a joint work with Eva Linke [2], and Matthias Henze&Maria Hernadez Cifre [3].

[1] Károly J. Böröczky, Erwin Lutwak, Deane Yang, and Gaoyong Zhang, The logarithmic Minkowski problem, JAMS 26(3), 2013.
[2] Martin Henk and Eva Linke, Cone volume measures of polytopes, Adv. Math 253, 50–62, 2014. (arXiv:1305.5335).
[3] Martin Henk, Matthias Henze, and Maria Hernandez Cifre, On extensions of Minkowski's theorem on successive minima, arXiv:1405.4993.

Colloquium - 16:00

Stefan Mengel- Ecole Polytechnique Paris

Tractable Propositional Model Counting by Structural Restrictions

Proposition model counting (#SAT) is the problem of counting satisfying assignments (models) to a CNF-formula. It is the canonical #P-hard counting problem and is important due to its applications in Artificial Intelligence. There is a growing body of work that successfully applies so-called structural restrictions to #SAT, i.e., restrictions to graphs and hypergraphs associated to CNF-Formulas to isolate tractable classes of instances. In this talk I will give an introduction into the area and discuss some very recent results with Johann Brault-Baron, Florent Capelli and Arnaud Durand.

Letzte Aktualisierung: 22.05.2014