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, January 28, 2013

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005

Lecture - 14:15

Achill Schürmann - Universität Rostock

Exploiting Polyhedral Symmetries

Many important problems in mathematics and its applications are modeled using linear constraints respectively polyhedra. Standard modeling often yields polyhedra having many symmetries. However, standard algorithms do not take advantage of them, and even worse, they often work particularly poorly on symmetric problems. In this talk we give an overview about ongoing work on new symmetry exploiting techniques for three fundamental task in polyhedral computations: the representation conversion problem, integer linear programming and lattice point counting. Initial proof-of-concept results show that affine symmetries can be exploited quite well in certain situations. In order to apply these new techniques on a broader scale new theoretical grounds have to be broken.

Colloquium - 16:00

Dennis Clemens - FU Berlin

Fast strategies in Maker-Breaker games

A Maker-Breaker game is defined as follows: Given a board X and a subset F of its power set (called the set of winning sets), the two players Maker and Breaker alternately claim elements of X. If Maker occupies an element of F completely during the game, she wins. Otherwise, Breaker is called the winner.

Because of their relation to strong games, fast winning strategies for Maker are of special interest. We will discuss the mentioned relation. Moreover, we will see some recent results concerning fast strategies in Maker-Breaker games played on complete and on sparse random graphs.

Joint work with Asaf Ferber, Roman Glebov, Dan Hefetz, Michael Krivelevich and Anita Liebenau

Letzte Aktualisierung: 14.01.2013