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

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?)

  • 1. Bonin, J., McNulty, J., and Reid, T.J., The matroid Ramsey number $n(6,6)$, Combin. Probab. Comput. 8(1999), 229-235. MR 2000i:05040
  • 2. Denley, T. and Reid, T.J., On the number of elements in matroids with small circuits and small cocircuits, Combin. Probab. Comput. 8 (1999), 529-537. CMP 2000:09
  • 3. Erdos, P. and Szekeres, G., A combinatorial problem in geometry, Compositio Math. 2 (1935), 463-470.
  • 4. Fulkerson, D.R., Networks, frames, blocking sysyems, in Mathematics of the Decision Sciences, Part 1, Lectures in Applied Math. Vol. 11, Amer. Math. Soc., Providence, R.I., 1968, pp. 303-334. MR 42:4329
  • 5. Hurst, F. and Reid, T.J., Some small circuit-cocircuit Ramsey numbers for matroids, Combin. Probab. Comput. 4 (1995), 67-80. MR 96d:05033
  • 6. Hurst, F. and Reid, T.J., Ramsey numbers for cocircuits in matroids, Ars Combin. 45 (1997), 181-192. MR 97a:05067
  • 7. Lehman, A., On the width-length inequality, Math. Programming 17 (1979), 403-417. MR 83a:94034a
  • 8. Lemos, M., $k$-elimination property for circuits of matroids, J. Combin. Theory Ser. B 51 (1991), 211-226. MR 92e:05027
  • 9. Oxley, J.G., Matroid Theory, Oxford University Press, New York, 1992. MR 94d:05033
  • 10. Oxley, J.G., Unavoidable minors in graphs and matroids, in Graph theory and combinatorial biology (Balatonlelle, 1996), Bolyai Soc. Math. Stud. 7, János Bolyai Math. Soc., Budapest, 1999, pp. 279-305. MR 2000c:05038
  • 11. Reid, T.J., Ramsey numbers for matroids, Europ. J. Combin 18 (1997), 589-595. MR 98h:05139
  • 12. Seymour, P.D., The matroids with the max-flow min-cut property, J. Combin. Theory Ser. B 23 (1977), 189-222. MR 57:2960
  • 13. Seymour, P.D., Decomposition of regular matroids, J. Combin. Theory Ser. B 28 (1980), 305-354. MR 82j:05046
  • 14. Tutte, W.T., Lectures on matroids, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 1-47. MR 31:4023
  • 15. Tuza, Z., On two intersecting set systems and $k$-continuous Boolean functions, Discrete Appl. Math 16 (1987), 183-185. MR 88a:05007
  • 16. Wu, P.-L., An upper bound on the number of edges of a $2$-connected graph, Combin. Probab. Comput. 6 (1997), 107-113. MR 97m:05146
  • 17. Wu, P.-L., Extremal graphs with prescribed circumference and cocircumference, Discrete Math. 223 (2000), 299-308. CMP 2001:01

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

American Mathematical Society