Monday, January 21, 2008
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Math building - Room MA 041
Lecture - 14:15
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
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.