Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

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

Nikhil Bansal - Eindhoven University of Technology

Counting the number of matroids

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

Karim Adiprasito - Freie Universität Berlin

Many high-dimensional polytopes with small realization spaces

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.

Letzte Aktualisierung: 07.11.2012