A sharp bound on the size of a connected matroid |
| |
Authors: | Manoel Lemos James Oxley |
| |
Affiliation: | Departamento de Matemática, Universidade Federal de Pernambuco, Recife, Pernambuco 50740-540, Brazil ; Department of Mathematics, Louisiana State University, Baton Rouge, Louisiana 70803-4918 |
| |
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 . |
| |
Keywords: | |
|
| 点击此处可从《Transactions of the American Mathematical Society》浏览原始摘要信息 |
|
点击此处可从《Transactions of the American Mathematical Society》下载全文 |
|