[home] - [up]


Lectures and Colloquia during the semester



January 16, 2006

Freie Universität Berlin - Institut für Informatik
Takustraße 9
14195 Berlin
Room 005           - map -
Lecture - 14:15

Igor Pak -Massachusetts Institute of Technology

Combinatorics and geometry of convex polyhedra

Abstract: I will survey various combinatorial, geometric and computational problems on surfaces of convex polyhedra related to the study of closed geodesics, to computing the geodesic distance, non-overlapping unfolding, isometric embedding of surfaces, etc. I will try put these results into historical perspective, by showing connections to the smooth case as a motivation. In the last part of the talk I will mention my joint work with Ezra Miller on non-overlapping unfoldings of convex polyhedra in higher dimension, and how these can be obtained algorithmically. The talk is aimed at a general audience, so no background will be assumed.


Colloquium - 16:00

Jürgen Schütz - Freie Universität Berlin

Counting spanning arborescences in directed graphs

Abstract: An arborescence is a directed, rooted tree, where the edges are directed towards the root. In the first part of the talk we consider a theorem of W. Tutte concerning the number t(G,v) of spanning arborescences in a directed graph G rooted at a vertex v. We will show, how this result follows from the Lemma of Gessel and Viennot. With Tutte's theorem it is easy to show, that for Eulerian graphs the number t(G,v) is independent from v. From this, two questions arise: 1. Are there other graphs with this property? 2. Given a graph G with n vertices and maximum net degree k>0, how large can |t(G,v)-t(G,w)| be for vertices v and w? These two questions are studied in the second part of the talk.


[home] - [up] - [top]