Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
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


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

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

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

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia