Fork-decompositions of matroids
type: Item
instance of: scholarly article
title: Fork-decompositions of matroids
zbMATH Open document ID: 1053.05024
DOI: 10.1016/S0196-8858(03)00058-7
author: Rhiannon Hall
author: Charles Semple
author: James Oxley
author: Geoff Whittle
published in: Advances in Applied Mathematics
publication date: 2004-10-12T00:00:00Z
review text: In an effort to strengthen the notion of 3-connectivity, the authors study weakened versions of 4-connectivity for matroids. In particular, the authors introduce fork-connectivity, a new type of 4-connectivity for matroids, to allow further progress in matroid representation theory. Conjecture 1.1 (The analogue of Kahn's conjecture). For every finite field \(\text{GF}(q)\), there is an integer \(\nu_q\) such that every vertically 4-connected \(\text{GF}(q)\)-representable matroid has at most \(\nu_q\) inequivalent representations over \(\text{GF}(q)\). The authors believe Conjecture 1.1 to hold for vertically 4-connected matroids and prove that Conjecture 1.1 holds for fork-connected matroids if and only if it holds for vertically 4-connected matroids. The authors prove that every fork-connected matroid can be reduced to a vertically 4-connected matroid by a sequence of segment-cosegment or cosegment-segment exchanges. Since no analogue of Seymour's splitter theorem holds for vertically 4-connected matroids, the authors consider sequentially 4-connected matroids which are closed under duality, contain vertically 4-connected matroids, and for which an analogue of the wheels and whirls theorem has been proven. Fork-connectivity is weaker than sequential 4-connectivity yet maintains many benefits of stronger 4-connectivity notions (e.g. Conjecture 1.1). The authors conjecture that an analogue of Seymour's splitter theorem holds for the class of fork-connected matroids. By taking direct sums and 2-sums of 3-connected forked matroids, the class of forked matroids is formed, which is closed under duality and minors. The authors show this class has finitely many excluded minors.
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 2107251
zbMATH Keywords: fork-connectivity
zbMATH Keywords: 4-connected matroids
zbMATH Keywords: fork-connected matroids
zbMATH Keywords: forked matroids
zbMATH Keywords: minors
reviewed by: Kelly J. Pearson
MaRDI profile type: Publication
cites work: A simple theorem on 3-connectivity
cites work: Modular Constructions for Combinatorial Geometries
cites work: On matroid connectivity
cites work: Q4717852
cites work: Matroid 4-connectivity: A deletion-contraction theorem
cites work: Branch-width and Rota's conjecture
cites work: The excluded minors for GF(4)-representable matroids
cites work: Branch-width and well-quasi-ordering in matroids and graphs.
cites work: Inequivalent representations of matroids having no \(U_{3,6}\)-minor
cites work: On matroids of branch-width three.
cites work: Whitney Connectivity of Matroids
cites work: On the Uniqueness of Matroid Representations Over GF(4)
cites work: On a matroid generalization of graph connectivity
cites work: Q3135082
cites work: The structure of a 3-connected matroid with a 3-separating set of essential elements
cites work: On the structure of 3-connected matroids and graphs
cites work: Generalized \(\Delta\text{--}Y\) exchange and \(k\)-regular matroids
cites work: On inequivalent representations of matroids over finite fields
cites work: Q4352948
cites work: Q4135576
cites work: Graph minors. X: Obstructions to tree-decomposition
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: On the delta-wye reduction for planar graphs
cites work: Connectivity in Matroids
full work available at URL: s0196-8858(03)00058-7
OpenAlex ID: W2071164314
description: scientific article; zbMATH DE number 2107251