On the Number of Matroids

Опубликовано 27 июля 2016, 2:04

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.