Monday, November 19, 2012
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
I will talk about some recent results on upper bounding the number of
matroids on
a ground set of size n. The talk will consist of two parts. First, I
will describe
a technique for bounding the number of stable sets in a graph, where
one uses the
spectral properties of the graph to represent every stable set using few bits.
Second, we will see how this idea, together with some basic properties
of matroids, can be used to obtain a compressed representation for any matroid.
Our bound substantially improves the previous results and comes quite close
to known lower bound on the number of matroids.
Joint work with Rudi Pendavingh and Jorn van der Pol.
Colloquium - 16:00
Abstract:
At first glance, it might seem that the the "larger" a polytope gets,
the more "flexible" it should be. In other words, if a polytope has
many vertices, then the space of its geometric realizations should be
of a high dimension.
For polytopes of dimension up to 3, this intuition holds true; this
follows from classical works of Legendre and Steinitz. In my talk, I
will demonstrate that for every dimension higher than three, the
intuition fails. I present two results:
(1) I present an infinite family of $4$-polytopes whose realization
spaces have dimension smaller or equal to $96$. This in particular
settles a problem going back to Legendre and Steinitz: To bound the
dimension of the realization space of a polytope in terms of its
$f$-vector.
(2) Moreover, I exhibit an infinite family of combinatorially distinct
$69$-dimensional polytopes whose realization is unique up to
projective transformation. This answers a problem posed by Perles and
Shephard in the sixties.
Based on joint work with G.M. Ziegler.