# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# The Upcoming Monday Lecture and Colloquium

Monday, January 21, 2008

Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Math building - Room MA 041

Lecture - 14:15

### Counting planar graphs and related families of graphs

Abstract:
We survey several results on the enumeration of labelled graphs, in particular planar graphs. The main tools are the theory of map enumeration, the decomposition of graphs into k-connected components, and the analysis of generating functions. Along the way we also discuss graph classes defined in terms of excluded minors, and graphs embeddable on surfaces of higher genus. Properties of random planar graphs and other families of graphs will be presented, in particular some critical phenomena that appear when the edge density crosses a given threshold. The talk is intended to be expository and non-technical.

Colloquium - 16:00

### Perles' Skeleton Theorem and positive spanning sets

Abstract:
I will talk about \emph{minimal positive $k$-spanning vector configurations} in $m$-dimensional vector spaces, and their generalizations in oriented matroids. I will show how to prove a bound on the size of such vector configurations that, for fixed $k$, is polynomial in $m$ by relating it to a problem on skeleta of polytopes. The bound is derived from a theorem by Micha Perles, the Perles Skeleton Theorem. I will discuss this theorem in a generality that makes it applicable to the oriented matroid setting, and thereby prove a bound on the size of minimal positive $k$-spanning sets in totally cyclic oriented matroids. This gives a solution to a problem posed by Bienia and Las Vergnas.
This is joint work with Günter M. Ziegler.