论文标题
构成分支的障碍
Obstructions for bounded branch-depth in matroids
论文作者
论文摘要
Devos，Kwon和Oum介绍了矩形分支深度的概念，作为图形深度的天然类似物。他们猜想一个足够大的分支深度的矩形包含均匀的矩阵$ u_ {n，2n} $或大型风扇图的循环曲线。我们证明，具有足够大的分支深度的矩形要么包含大型风扇图的循环曲线，要么是较小的分支宽度。作为推论，我们证明了它们对在固定有限的磁场和准绘制的矩阵上代表的矩阵的猜想，其中均匀的矩阵不是一个选择。
DeVos, Kwon, and Oum introduced the concept of branch-depth of matroids as a natural analogue of tree-depth of graphs. They conjectured that a matroid of sufficiently large branch-depth contains the uniform matroid $U_{n,2n}$ or the cycle matroid of a large fan graph as a minor. We prove that matroids with sufficiently large branch-depth either contain the cycle matroid of a large fan graph as a minor or have large branch-width. As a corollary, we prove their conjecture for matroids representable over a fixed finite field and quasi-graphic matroids, where the uniform matroid is not an option.
