Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



A sharp bound on the size of a connected matroid

Authors: Manoel Lemos and James Oxley
Journal: Trans. Amer. Math. Soc. 353 (2001), 4039-4056
MSC (2000): Primary 05B35; Secondary 05C35
Published electronically: June 1, 2001
MathSciNet review: 1837219
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 05B35, 05C35

Retrieve articles in all journals with MSC (2000): 05B35, 05C35

Additional Information

Manoel Lemos
Affiliation: Departamento de Matemática, Universidade Federal de Pernambuco, Recife, Pernambuco 50740-540, Brazil

James Oxley
Affiliation: Department of Mathematics, Louisiana State University, Baton Rouge, Louisiana 70803-4918

Received by editor(s): April 12, 1999
Received by editor(s) in revised form: January 18, 2000
Published electronically: June 1, 2001
Article copyright: © Copyright 2001 American Mathematical Society