Monday, December 3, 2007
Freie Universität Berlin
Institut für Informatik
Takustr. 9, 14195 Berlin
room 005
Lecture - 14:15
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
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.