|
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
Retrieve article in:
PDF DVI PostScript
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
This paper proves that a connected matroid in which a largest circuit and a largest cocircuit have and elements, respectively, has at most elements. It is also shown that if is an element of and and are the sizes of a largest circuit containing and a largest cocircuit containing , then . 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 and are replaced by the sizes of a smallest circuit containing and a smallest cocircuit containing . Moreover, it follows from the second inequality that if and are distinct vertices in a -connected loopless graph , then cannot exceed the product of the length of a longest -path and the size of a largest minimal edge-cut separating from .
References:
-
- 1.
- Bonin, J., McNulty, J., and Reid, T.J., The matroid Ramsey number
, 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.,
-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
-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
-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
|