Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

A sharp bound on the size of a connected matroid
HTML articles powered by AMS MathViewer

by Manoel Lemos and James Oxley PDF
Trans. Amer. Math. Soc. 353 (2001), 4039-4056 Request permission

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
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
  • Received by editor(s): April 12, 1999
  • Received by editor(s) in revised form: January 18, 2000
  • Published electronically: June 1, 2001
  • © Copyright 2001 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 353 (2001), 4039-4056
  • MSC (2000): Primary 05B35; Secondary 05C35
  • DOI: https://doi.org/10.1090/S0002-9947-01-02767-2
  • MathSciNet review: 1837219