Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
On the Number of Matroids

Speaker  Nikhil Bansal

Affiliation  Eindhoven University of Technology

Host  Konstantin Makarychev

Duration  00:53:42

Date recorded  3 September 2013

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 the known lower bound on the number of matroids.

Joint work with Rudi Pendavingh and Jorn van der Pol.

©2013 Microsoft Corporation. All rights reserved.
> On the Number of Matroids