Source author record

J. G. van der Pol

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Information Theory math.IT

Catalog footprint

Research overview

3works

3topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2013arXiv

Counting matroids in minor-closed classes

A flat cover is a collection of flats identifying the non-bases of a matroid. We introduce the notion of cover complexity, the minimal size of such a flat cover, as a measure for the complexity of a matroid, and present bounds on the number of matroids on $n$ elements whose cover complexity is bounded. We apply cover complexity to show that the class of matroids without an $N$ -minor is asymptotically small in case $N$ is one of the sparse paving matroids $U_{2,k}$ , $U_{3,6}$ , $P_6$ , $Q_6$ , or $R_6$ , thus confirming a few special cases of a conjecture due to Mayhew, Newman, Welsh, and Whittle. On the other hand, we show a lower bound on the number of matroids without $M(K_4)$ -minor which asymptoticaly matches the best known lower bound on the number of all matroids, due to Knuth.

preprint2013arXiv

On the number of matroids

We consider the problem of determining $m_n$ , the number of matroids on $n$ elements. The best known lower bound on $m_n$ is due to Knuth (1974) who showed that $\log \log m_n$ is at least $n-3/2\log n-1$ . On the other hand, Piff (1973) showed that $\log\log m_n\leq n-\log n+\log\log n +O(1)$ , and it has been conjectured since that the right answer is perhaps closer to Knuth's bound. We show that this is indeed the case, and prove an upper bound on $\log\log m_n$ that is within an additive $1+o(1)$ term of Knuth's lower bound. Our proof is based on using some structural properties of non-bases in a matroid together with some properties of independent sets in the Johnson graph to give a compressed representation of matroids.

preprint2012arXiv

An entropy argument for counting matroids

We show how a direct application of Shearers' Lemma gives an almost optimum bound on the number of matroids on $n$ elements.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.