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 3, 2007

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

Lecture - 14:15

Tibor Szabó - ETH Zürich

Random graph intuition and pseudorandomness in positional games

Positional games are played ever since humans exist. We all play(ed)
some variants of it, befitting our age, like Tic-tac-toe,
5-in-a-row, or Hex. In this talk we concentrate on "weak" positional
games, a close relative of the "strong" games we do actually play.
A major difference between the two is that while mathematical study
of strong games often leads to an uphill battle of case-analysis,
weak games accomodate a beautiful theory filled with half-understood
connections to important concepts of combinatorics and computer
We will mostly discuss games played on the edges of the complete
graph. We plan to explain the mysterious connection to the theory of
random graphs (pointed out by Erd\H os in the seventies) and
describe our attempts to enhance the understanding of this phenomena
via pseudorandom thinking. In particular, we present recent advances
in several classic graph games, for example connectivity and Hamiltonicity.
We do not assume any previous knowledge of positional games or
random graph theory.

Colloquium - 16:00

Andreas Paffenholz - FU Berlin

Permutation Polytopes

A permutation polytope is defined as the convex hull of a subgroup of the group of permutation matrices. Hence, these polytopes form a special class of 0/1-polytopes. A well-known example of such a polytope is the Birkhoff or assignment polytope, which is the polytope corresponding to the full permutation group. It appears in many different areas of mathematics and has been extensively studied, while the area of general permutation polytopes is quite new. A first general treatment was given by Guralnick and Perkinson in 2006.
In this talk I will report on joint work with Barbara Baumeister, Christian Haase, and Benjamin Nill (FU Berlin). I give an overview on combinatorial properties of permutation polytopes, their connections to the the subgroup that defines them, and discuss several notions of equivalence.

Letzte Aktualisierung: 23.11.2007