Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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 $\vert E(M)\vert \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 $\vert E(G)\vert$ 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
Email: manoel@dmat.ufpe.br

James Oxley
Affiliation: Department of Mathematics, Louisiana State University, Baton Rouge, Louisiana 70803-4918
Email: oxley@math.lsu.edu

DOI: http://dx.doi.org/10.1090/S0002-9947-01-02767-2
PII: S 0002-9947(01)02767-2
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