Describing quasi-graphic matroids. (March 2020)

• Record Type: Journal Article
• Authors: Bowler, Nathan; Funk, Daryl; Slilaty, Daniel
• Is Part Of: European journal of combinatorics. Volume 85(2020)
• Publication Date: 2020-03
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2019.103062
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: The class of quasi-graphic matroids recently introduced by Geelen, Gerards, and Whittle generalises each of the classes of frame matroids and lifted-graphic matroids introduced earlier by Zaslavsky. For each biased graph ( G, B ) Zaslavsky defined a unique lift matroid L ( G, B ) and a unique frame matroid F ( G, B ), each on ground set E ( G ) . We show that in general there may be many quasi-graphic matroids on E ( G ) and describe them all: for each graph G and partition ( B, L, F ) of its cycles such that B satisfies the theta property and each cycle in L meets each cycle in F, there is a quasi-graphic matroid M ( G, B, L, F ) on E ( G ) . Moreover, every quasi-graphic matroid arises in this way. We provide cryptomorphic descriptions in terms of subgraphs corresponding to circuits, cocircuits, independent sets, and bases. Equipped with these descriptions, we prove some results about quasi-graphic matroids. In particular, we provide alternate proofs that do not require 3-connectivity of two results of Geelen, Gerards, and Whittle for 3-connected matroids from their introductory paper: namely, that every quasi-graphic matroid linearly representable over a field is either lifted-graphic or frame, and that if a matroid M has a framework with a loop that is not a loop of M then M is either lifted-graphic or frame. We also provide sufficient conditions for a quasi-graphic matroid to have a unique framework. Zaslavsky has asked for those matroids whose independent sets are contained in the collection of independent sets of F ( G, B ) while containing those of L ( G, B ), for some biased graph ( G, B ) . Adding a natural (and necessary) non-degeneracy condition defines a class of matroids, which we call biased-graphic . We show that the class of biased-graphic matroids almost coincides with the class of quasi-graphic matroids: every quasi-graphic matroid is biased-graphic, and if M is a biased-graphic matroid that is not quasi-graphic then M is a 2-sum of a frame matroid with one or more lifted-graphic matroids.