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, December 7, 2009

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

Lecture - 14:15

Frank Vallentin - Delft

Semidefinite programs with rank constraints

Finding a sparse/low rank solution in linear/semidefinite programming has many important applications, e.g. combinatorial optimization, compressed sensing, geometric embedding, sensor network localization. In this talk we will consider one of the most basic problems involving semidefinite programs with rank constraints: the positive semidefinite Grothendieck problem with rank-n-constraint. It contains the MAX CUT problem as a special case when n = 1. We will perform a complete complexity analysis of the problem by designing an approximation algorithm and by proving that the algorithm is optimal if one assumes the unique games conjecture. joint work with Jop BriŽt and Fernando de Oliveira Filho (

Colloquium - 16:00

Rade Zivaljevic - Mathematical Institute SANU, Belgrade

Chessboard complexes indomitable

A recent wonderful breakthrough in the ``Colored Tverberg problem'' (Pavle V. M. Blagojevic, GŁnter M. Ziegler, Optimal bounds for the colored Tverberg problem, arXiv:0910.4987v1 [math.CO]) placed chessboard complexes $\Delta_{m,n}$ in the focus again. Closely related ``cycle-free chessboard complexes'' $\Omega_{m,n}$ have recently emerged in completely different problem on the borderline of combinatorics and topology (Shaun Ault, Zbigniew Fiedorowicz, arXiv:0708.1575v4 [math.AT]). We review properties of these complexes focusing on their homology, connectivity, and (still open) problems about their shellability (vertex decomposability). The lecture is based on the joint paper with Sini\v sa Vrecica (European J.~Math.\ 2009, arXiv:0710.5252v3 [math.AT]).

Letzte Aktualisierung: 16.11.2009