A problem of P. Seymour on nonbinary matroids
type: Item
instance of: scholarly article
title: A problem of P. Seymour on nonbinary matroids
zbMATH Open document ID: 0593.05016
DOI: 10.1007/BF02579246
published in: Combinatorica
publication date: 1985-01-01T00:00:00Z
review text: It is well-known that a matroid is non-binary if and only if it has a \(U_{2,4}\)-minor. This paper looks at the problem of relating sets of elements in a non-binary matroid M to \(U_{2,4}\)-minors of M. \textit{R. E. Bixby} [Discrete Math. 8, 139-145 (1974; Zbl 0279.05027)] proved that, when \(k=2\), if M is k-connected and X is a (k-1)-element subset of M, then M has a \(U_{2,4}\)-minor whose ground set contains X. The same result was proved for \(k=3\) by \textit{P. D. Seymour} [Combinatorica 1, 387- 394 (1981; Zbl 0489.05020)] who also asked whether it remains true for \(k=4\). This paper answers this question negatively. The author's example is a 15-element rank-7 matroid \(M_ 1\) that is obtained from a binary matroid \(M_ 2\) with the same rank and ground set by relaxing a circuit- hyperplane of the latter. This means that the independent sets of \(M_ 1\) are all the independent sets of \(M_ 2\) together with a single circuit-hyperplane of \(M_ 2\). Another counterexample to the case \(k=4\) of this result, a 12-element rank-6 matroid, has been independently found by \textit{C. Coullard} [Counterexamples to conjectures on 4-connected matroids, Combinatorica (to appear)]. After establishing that his example has the properties claimed, the author concludes with two conjectures, the first of which has been proved by the reviewer [Combinatorica 5, 343- 345 (1985)].
reviewed by: James Oxley
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 3952784
zbMATH Keywords: k-connectivity
zbMATH Keywords: non-binary matroid
author: J. Kahn
MaRDI profile type: Publication
cites work: \(l\)-matrices and a characterization of binary matroids
cites work: Matroid representation over GF(3)
cites work: On minors of non-binary matroids
cites work: Q3249424
cites work: Connectivity in Matroids
Recommended article: Counterexamples to conjectures on 4-connected matroids
Recommended article: Minors of 3-connected matroids
Recommended article: On Nonbinary 3-Connected Matroids
Recommended article: A class of non-binary matroids with many binary minors
Recommended article: The smallest rounded sets of binary matroids
Recommended article: Proof of a conjecture of Kahn for non-binary matroids
Recommended article: A minor-based characterization of matroid 3-connectivity
Recommended article: A note on roundedness in 4-connected matroids
Recommended article: A characterization of a class of non-binary matroids
Recommended article: On two classes of nearly binary matroids
description: scientific article; zbMATH DE number 3952784