A sharp bound on the size of a connected matroid

Abstract:

This paper proves that a connected matroid $M$ in which a largest circuit and a largest cocircuit have $c$ and $c^*$ elements, respectively, has at most $\frac {1}{2}cc^*$ elements. It is also shown that if $e$ is an element of $M$ and $c_e$ and $c^*_e$ are the sizes of a largest circuit containing $e$ and a largest cocircuit containing $e$, then $|E(M)| \le (c_e -1)(c^*_e - 1) + 1$. Both these bounds are sharp and the first is proved using the second. The second inequality is an interesting companion to Lehman’s width-length inequality which asserts that the former inequality can be reversed for regular matroids when $c_e$ and $c^*_e$ are replaced by the sizes of a smallest circuit containing $e$ and a smallest cocircuit containing $e$. Moreover, it follows from the second inequality that if $u$ and $v$ are distinct vertices in a $2$-connected loopless graph $G$, then $|E(G)|$ cannot exceed the product of the length of a longest $(u,v)$-path and the size of a largest minimal edge-cut separating $u$ from $v$.