اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدObstructions for bounded branch-depth in matroids
58
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
Shrub-depth and rank-depth are dense analogues of the tree-depth of a graph. It is well known that a graph has large tree-depth if and only if it has a long path as a subgraph. We prove an analogous statement for shrub-depth and rank-depth, which was
conjectured by Hlinv{e}ny, Kwon, Obdrv{z}alek, and Ordyniak [Tree-depth and vertex-minors, European J.~Combin. 2016]. Namely, we prove that a graph has large rank-depth if and only if it has a vertex-minor isomorphic to a long path. This implies that for every integer $t$, the class of graphs with no vertex-minor isomorphic to the path on $t$ vertices has bounded shrub-depth.
We characterize classes of graphs closed under taking vertex-minors and having no $P_n$ and no disjoint union of $n$ copies of the $1$-subdivision of $K_{1,n}$ for some $n$. Our characterization is described in terms of a tree of radius $2$ whose lea
ves are labelled by the vertices of a graph $G$, and the width is measured by the maximum possible cut-rank of a partition of $V(G)$ induced by splitting an internal node of the tree to make two components. The minimum width possible is called the depth-$2$ rank-brittleness of $G$. We prove that for all $n$, every graph with sufficiently large depth-$2$ rank-brittleness contains $P_n$ or disjoint union of $n$ copies of the $1$-subdivision of $K_{1,n}$ as a vertex-minor.
We introduce delta-graphic matroids, which are matroids whose bases form graphic delta-matroids. The class of delta-graphic matroids contains graphic matroids as well as cographic matroids and is a proper subclass of the class of regular matroids. We
give a structural characterization of the class of delta-graphic matroids. We also show that every forbidden minor for the class of delta-graphic matroids has at most $48$ elements.
Schlichting conjectured that the negative K-groups of small abelian categories vanish and proved this for noetherian abelian categories and for all abelian categories in degree $-1$. The main results of this paper are that $K_{-1}(E)$ vanishes when $
E$ is a small stable $infty$-category with a bounded t-structure and that $K_{-n}(E)$ vanishes for all $ngeq 1$ when additionally the heart of $E$ is noetherian. It follows that Barwicks theorem of the heart holds for nonconnective K-theory spectra when the heart is noetherian. We give several applications, to non-existence results for bounded t-structures and stability conditions, to possible K-theoretic obstructions to the existence of the motivic t-structure, and to vanishing results for the negative K-groups of a large class of dg algebras and ring spectra.
Let $cX$ be a family of subsets of a finite set $E$. A matroid on $E$ is called an $cX$-matroid if each set in $cX$ is a circuit. We consider the problem of determining when there exists a unique maximal $cX$-matroid in the weak order poset of all $c
X$-matroids on $E$, and characterizing its rank function when it exists.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
