Obstructions for bounded branch-depth in matroids

DOI10.19086/AIC.24227zbMATH Open1477.05018arXiv2003.13975OpenAlexW3165795633MaRDI QIDQ5162868FDOQ5162868

Authors: J. Pascal Gollin, Kevin Hendrey, Dillon Mayhew, Sang-Il Oum 

Publication date: 5 November 2021

Published in: Advances in Combinatorics (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/2003.13975

Recommendations

• Branch-depth: generalizing tree-depth of graphs
• Obstructions to branch-decomposition of matroids
• Branch-width and well-quasi-ordering in matroids and graphs.
• Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids
• The branchwidth of graphs and their cycle matroids

zbMATH Keywords

branch-widthrepresentable matroidsquasi-graphic matroidsbranch-depthtwisted matroids

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Graph minors. X: Obstructions to tree-decomposition
• Title not available (Why is that?)
• Approximating clique-width and branch-width
• Graph minors. V. Excluding a planar graph
• Sparsity. Graphs, structures, and algorithms
• The excluded minors for GF(4)-representable matroids
• The dependence graph for bases in matroids
• First order convergence of matroids
• The branchwidth of graphs and their cycle matroids
• Branchwidth of graphic matroids
• The structure of the 3-separations of 3-connected matroids
• Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids
• Title not available (Why is that?)
• Comments on bases in dependence structures
• Some open problems on excluding a uniform matroid
• Obstructions to branch-decomposition of matroids
• Quasi-graphic matroids
• Obstructions for bounded shrub-depth and rank-depth
• Branch-depth: generalizing tree-depth of graphs
• Describing quasi-graphic matroids

Cited In (4)

• The branchwidth of graphs and their cycle matroids
• The extremal functions of classes of matroids of bounded branch-width
• The \(r\)-depth of a matroid
• Obstructions to branch-decomposition of matroids

This page was built for publication: Obstructions for bounded branch-depth in matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5162868)