An infinite family of excluded minors for strong base-orderability

DOI10.1016/J.LAA.2015.09.055zbMATH Open1326.05025arXiv1507.05521OpenAlexW2206068481MaRDI QIDQ896863FDOQ896863

Authors: Joseph E. Bonin, Thomas J. Savitsky 

Publication date: 14 December 2015

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: We discuss a conjecture of Ingleton on excluded minors for base-orderability, and, extending a result he stated, we prove that infinitely many of the matroids that he identified are excluded minors for base-orderability, as well as for the class of gammoids. We prove that a paving matroid is base-orderable if and only if it has no minor that is isomorphic to the cycle matroid of the complete graph on four vertices. For each k that is at least 2, we define the property of k-base-orderability, which lies strictly between base-orderability and strong base-orderability, and we show that k-base-orderable matroids form what Ingleton called a complete class. By generalizing an example of Ingleton, we construct a set of matroids, each of which is an excluded minor for k-base-orderability, but is (k-1)-base-orderable; the union of these sets, over all k, is an infinite set of base-orderable excluded minors for strong base-orderability.

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

Recommendations

• Matroids over \(F_ p\) which are rational excluded minors
• Adjacency, inseparability, and base orderability in matroids
• On the relative importance of excluded minors
• When excluding one matroid prevents infinite antichains
• On finding some new excluded minors for gammoids

zbMATH Keywords

excluded minorsbase-orderable matroidsstrongly base-orderable matroids

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Combinatorial aspects of matroids and geometric lattices (05B35) Graph minors (05C83)

Cites Work

• Title not available (Why is that?)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the Vector Representation of Matroids
• A characterisation of binary transversal structures
• Gammoids and transversal matroids
• Exchange systems, matchings, and transversals
• Counting matroids in minor-closed classes
• The lattice of cyclic flats of a matroid
• Some properties of basic families of subsets
• A Multiple Exchange Property for Bases
• An exchange theorem for bases of matroids
• Characterizations of transversal and fundamental transversal matroids
• Induced Matroids
• Title not available (Why is that?)
• Comments on bases in dependence structures
• Title not available (Why is that?)
• Title not available (Why is that?)
• Semidirect sums of matroids
• A COMPLETE CLASS OF MATROIDS
• Title not available (Why is that?)

Cited In (2)

• Partitioning into common independent sets via relaxing strongly base orderability
• The Excluded Minors for Three Classes of 2-Polymatroids Having Special Types of Natural Matroids

Uses Software

• nauty
• Matroid

This page was built for publication: An infinite family of excluded minors for strong base-orderability

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