Describing quasi-graphic matroids
Digital Document
Collection(s) |
Collection(s)
|
---|---|
Content type |
Content type
|
Resource Type |
Resource Type
|
Genre |
Genre
|
Language |
Language
|
Peer Review Status |
Peer Review Status
Peer Reviewed
|
Persons |
---|
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, \mathcal B)$ Zaslavsky defined a unique lift matroid $L(G, \mathcal B)$ and a unique frame matroid $F(G, \mathcal 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. 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, \mathcal B)$ while containing those of $L(G, \mathcal B)$, for some biased graph $(G, \mathcal 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. |
---|
Publication Title |
Publication Title
|
---|---|
Publication Number |
Publication Number
Volume 85
|
DOI |
DOI
10.1016/j.ejc.2019.103062
|
---|---|
ISSN |
ISSN
0195-6698
|
URL | |
---|---|
Identifier URI | |
Use and Reproduction |
Use and Reproduction
©2020. European Journal of Combinatorics. Elsevier.
|
Rights Statement |
Rights Statement
|
Subject Topic |
Subject Topic
|
---|