Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Available in electronic format
Available in print format
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(e) ISSN 0002-9947(p)

     

A sharp bound on the size of a connected matroid

Author(s): Manoel Lemos; James Oxley
Journal: Trans. Amer. Math. Soc. 353 (2001), 4039-4056.
MSC (2000): Primary 05B35; Secondary 05C35
Posted: June 1, 2001
MathSciNet review: 1837219
Retrieve article in: PDF
This article is available free of charge

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:

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
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: 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
Posted: June 1, 2001
Copyright of article: Copyright 2001, American Mathematical Society




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia