Ordering circuits of matroids (Q2112564): Difference between revisions

When a graph theorist first learns about matroids he might hope that matroids possess some property that can be used to make up for their lack of vertices. One such property is the orderability property studied in this paper. A matroid is orderable if its circuits can be given a consistent ordering, that is, the elements of each circuit can be given a reversible cyclic ordering, so that if two elements are adjacent in a circuit, then they are adjacent in every circuit in which they both appear. Clearly graphic matroids are orderable, but it is easy to see that \(U_{2,4}\) is also orderable. The authors' main result characterizes connected, non-binary, orderable matroids as those which may be obtained from \(U_{2,4}\) by a sequence of balanced series extensions (series extensions in which every element is replaced by the same number of series elements) and parallel path additions (essentially the matroid analogue of taking a path \(P\) with each internal vertex having degree two and attaching a new path \(P^\prime\) with the same length as \(P\) to the ends of \(P\)). The situation for binary matroids is less clear. The authors show that for every binary matroid \(M\), if either every series minor of \(M\) is orderable or every parallel minor of \(M\) is orderable, then \(M\) is graphic. Certainly there are non-graphic binary matroids which are not orderable, as the authors describe series extensions of \(F_7^\ast\) and \(M^\ast(K_5)\) which are not orderable. They conjecture that every \(3\)-connected binary orderable matroid is graphic and prove that every \(4\)-connected regular orderable matroid is graphic.