首页 | 本学科首页   官方微博 | 高级检索  
     检索      


A sharp bound on the size of a connected matroid
Authors:Manoel Lemos  James Oxley
Institution: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 $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$.

Keywords:
点击此处可从《Transactions of the American Mathematical Society》浏览原始摘要信息
点击此处可从《Transactions of the American Mathematical Society》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号