#
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

*Abstract:*

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

science.

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

*Abstract:*

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