## 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

- Joseph E. Bonin, Jennifer McNulty, and Talmage James Reid,
*The matroid Ramsey number $n(6,6)$*, Combin. Probab. Comput.**8**(1999), no. 3, 229–235. MR**1702554**, DOI 10.1017/S0963548398003691 - 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. - Erdős, P. and Szekeres, G., A combinatorial problem in geometry,
*Compositio Math.***2**(1935), 463–470. - D. R. Fulkerson,
*Networks, frames, blocking systems*, Mathematics of the Decision Sciences, Part 1 (Seminar, Stanford, Calif., 1967) Amer. Math. Soc., Providence, R.I., 1968, pp. 303–334. MR**0269433** - Fair Barbour Hurst and Talmage James Reid,
*Some small circuit–cocircuit Ramsey numbers for matroids*, Combin. Probab. Comput.**4**(1995), no. 1, 67–80. MR**1336656**, DOI 10.1017/S0963548300001486 - U. Schulte,
*Constructing trees in bipartite graphs*, Discrete Math.**154**(1996), no. 1-3, 317–320. MR**1395474**, DOI 10.1016/0012-365X(94)00335-G - Alfred Lehman,
*On the width-length inequality*, Math. Programming**16**(1979), no. 2, 245–259. MR**527577**, DOI 10.1007/BF01582111 - Manoel Lemos,
*$k$-elimination property for circuits of matroids*, J. Combin. Theory Ser. B**51**(1991), no. 2, 211–226. MR**1099071**, DOI 10.1016/0095-8956(91)90037-K - James G. Oxley,
*Matroid theory*, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1992. MR**1207587** - J. Oxley,
*Unavoidable minors in graphs and matroids*, Graph theory and combinatorial biology (Balatonlelle, 1996) Bolyai Soc. Math. Stud., vol. 7, János Bolyai Math. Soc., Budapest, 1999, pp. 279–305. MR**1673511** - Talmage James Reid,
*Ramsey numbers for matroids*, European J. Combin.**18**(1997), no. 5, 589–595. MR**1455191**, DOI 10.1006/eujc.1995.0112 - P. D. Seymour,
*The matroids with the max-flow min-cut property*, J. Combinatorial Theory Ser. B**23**(1977), no. 2-3, 189–222. MR**462996**, DOI 10.1016/0095-8956(77)90031-4 - P. D. Seymour,
*Decomposition of regular matroids*, J. Combin. Theory Ser. B**28**(1980), no. 3, 305–359. MR**579077**, DOI 10.1016/0095-8956(80)90075-1 - W. T. Tutte,
*Lectures on matroids*, J. Res. Nat. Bur. Standards Sect. B**69B**(1965), 1–47. MR**179781** - Zsolt Tuza,
*On two intersecting set systems and $k$-continuous Boolean functions*, Discrete Appl. Math.**16**(1987), no. 2, 183–185. MR**874916**, DOI 10.1016/0166-218X(87)90074-6 - Pou-Lin Wu,
*An upper bound on the number of edges of a $2$-connected graph*, Combin. Probab. Comput.**6**(1997), no. 1, 107–113. MR**1436723**, DOI 10.1017/S0963548396002787 - Wu, P.-L., Extremal graphs with prescribed circumference and cocircumference, Discrete Math.
**223**(2000), 299–308.

## 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