Exchange Distance of Basis Pairs in Split Matroids
From MaRDI portal
Abstract: The basis exchange axiom has been a driving force in the development of matroid theory. However, the axiom gives only a local characterization of the relation of bases, which is a major stumbling block to further progress, and providing a global understanding of the structure of matroid bases is a fundamental goal in matroid optimization. While studying the structure of symmetric exchanges, Gabow proposed the problem that any pair of bases admits a sequence of symmetric exchanges. A different extension of the exchange axiom was proposed by White, who investigated the equivalence of compatible basis sequences. These conjectures suggest that the family of bases of a matroid possesses much stronger structural properties than we are aware of. In the present paper, we study the distance of basis pairs of a matroid in terms of symmetric exchanges. In particular, we give a polynomial-time algorithm that determines a shortest possible exchange sequence that transforms a basis pair into another for split matroids, a class that was motivated by the study of matroid polytopes from a tropical geometry point of view. As a corollary, we verify the above mentioned long-standing conjectures for this large class. Being a subclass of split matroids, our result settles the conjectures for paving matroids as well.
Recommendations
Cites work
- A unique exchange property for bases
- Bases-cobases graphs and polytopes of matroids
- Basis pair graphs of transversal matroids are connected
- Basis-exchange properties of sparse paving matroids
- Cyclic orderings and cyclic arboricity of matroids
- Decomposing symmetric exchanges in matroid bases
- Edge‐disjoint spanning trees: A connectedness theorem
- Equitable partitions to spanning trees in a graph
- Excluded minors for the class of split matroids
- Fair representation in the intersection of two matroids
- Frame matroids, toric ideals, and a conjecture of White
- scientific article; zbMATH DE number 3534506 (Why is no real title available?)
- scientific article; zbMATH DE number 7351371 (Why is no real title available?)
- scientific article; zbMATH DE number 5873618 (Why is no real title available?)
- scientific article; zbMATH DE number 3342868 (Why is no real title available?)
- Hypergraph characterization of split matroids
- Lattice Theory of Generalized Partitions
- Matroids from hypersimplex splits
- On circuits and serial symmetric basis-exchange in matroids
- On sequential basis exchange in matroids
- On serial symmetric exchanges of matroid bases
- On the asymptotic proportion of connected matroids
- On the toric ideal of a matroid
- On the toric ideals of matroids of a fixed rank
- Ordering of the elements of a matroid such that its consecutive w elements are independent
- Some Abstract Pivot Algorithms
- The toric ideal of a graphic matroid is generated by quadrics
- The toric ideal of a matroid of rank 3 is generated by quadrics
- Toric ideals of lattice path matroids and polymatroids
Cited in
(8)- Weighted exchange distance of basis pairs
- Cyclic orderings of paving matroids
- Serial exchanges in random bases
- Cyclic ordering of split matroids
- Reconfiguration of basis pairs in regular matroids
- Face enumeration for split matroid polytopes
- Hamiltonian connectivity of some base-cobase graphs
- Enumerating the faces of split matroid polytopes
This page was built for publication: Exchange Distance of Basis Pairs in Split Matroids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6187077)
