Aarhus Universitets segl

Extremal Matroid Theory and The Erdös-Pósa Theorem

by Kasper Kabell Kristensen
PhD Dissertations April 2006

This thesis is associated to the area of mathematics known as matroid theory. It was founded in 1935 by Hassler Whitney, and has since then grown to be one of the major branches of combinatorics.

Matroids abstract combinatorial properties of a number of different types of mathematical objects, such as graphs, matrices, and finite geometries. Many key concepts carry over to matroids, including circuits, rank, and points and lines.

Extremal matroid theory deals with questions of how different parameters of matroids relate to each other. Many such questions are derived from extremal graph theory.

The Growth Rate Conjecture posed by Kung concerns bounds on the number of points as a function of the rank within different classes of matroids. The thesis presents several partial results to this conjecture, as well as some minor related results.

It also contains a matroid generalization of a classical graph-theoretic result known as the Erdös-Pósa Theorem. This result relates the rank of a matroid to the number of disjoint circuits in the dual matroid. In the process, tools are developed for measuring the size of matroids without a given uniform matroid as a minor.

Format available: PDF (707 KB)
Thesis advisor: Jørgen Brandt