Aarhus Universitets segl

The Erdös-Pósa property for matroid circuits

by Jim Geelen and Kasper Kabell
Preprints Number 1 (January 2006)
The number of disjoint co-circuits in a matroid is bounded by its rank. There are, however, matroids with arbitrarily large rank that do not contain two disjoint co-circuits; consider, for example, $M(K_n)$ and $U_{n,2n}$. Also the bicircular matroids $B(K_n)$ have arbitrarily large rank and have no $3$ disjoint co-circuits. We prove that for each $k$ and $n$ there exists a constant $c$ such that, if $M$ is a matroid with no $U_{n,2n}$-, $M(K_n)$-, or $B(K_n)$-minor, then either $M$ has $k$ disjoint co-circuits or $r(M)\le c$.
Format available: PDF (326 KB)