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

Joint work with Rudi Pendavingh and Jorn van der Pol.

Speaker Details

Nikhil Bansal is an Associate Professor in the Department of Mathematics and Computer Science at Eindhoven University of Technology. He obtained his PhD from Carnegie Mellon University in 2003, and worked at the IBM T.J. Watson Research Center until 2011, where he also managed the Algorithms group. He is broadly interested in theoretical computer science with focus on the design and analysis of approximation and online algorithms for combinatorial optimization problems. For his work, he has received best paper awards at FOCS 2011, ESA 2011 and ESA 2010, and IBM Research best paper awards for 2007 and 2010.

Series:
Microsoft Research Talks
Date:
Speakers:
Nikhil Bansal
Affiliation:
Eindhoven University of Technology

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks