Bases-cobases graphs and polytopes of matroids

DOI10.1007/BF01303201MaRDI QIDQ684402zbMATH OpenOpenAlexFDO

Authors Raul Cordovil, Maria Leonor Moreira

Publication date 15 September 1993

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01303201

zbMATH Keywords

bases-cobases graph block matroid polytope

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Paths and cycles (05C38)

Review text

Paraphrasing the authors' summary, let \(M\) be a block matroid, i.e., a matroid whose ground set \(E\) is a disjoint union of two bases. Then the graph \(G= G(M,M^*)\) having as vertices the bases \(B\) of \(M\) for which the complement \(E\backslash B\) is also a base, and edges the unordered pairs \((B,B')\) of such bases differing exactly by two elements is said to be the bases-cobases graph associated with \(M\). And moreover, the polytope \(K=K(M,M^*)\) whose extreme points are the incidence vectors of the bases of \(M\) whose complement is also a base is said to be the polytope of the bases-cobases. The following two main results are proved: (1) If \(M\) is a graphic block matroid, then any pair of vertices of \(G(M,M^*)\) corresponding to complementary bases is joined by a path of length \(\text{rank}(M)\). (2) If \(M\) is a block matroid, then \(K(M,M^*)\) is a hypercube if and only if \(\dim(K)=\text{rank}(M)\). The first of these results generalizes a result previously proved by \textit{Y. Kajitani}, \textit{S. Ueno} and \textit{H. Miyano} [Discrete Math. 72, No. 1-3, 187-194 (1988; Zbl 0657.05018)].

Recommendations

Cites work

Cited in

(24)

This page was built for publication: Bases-cobases graphs and polytopes of matroids

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