Funk, Daryl

Report on joint work in progress with Dillon Mayhew, Victoria University of Wellington, New Zealand delivered at the <a href="https://www.canadam.ca/index.html">Canadian Discrete and Algorithmic Mathematics (CANDAM) Conference</a>, Winnipeg, Manitoba (June 5-8, 2023). A matroid is an abstract object that generalises both graphs and vector spaces. Matroids are used to model many types of optimisation problems; often modelling a problem using a matroid can lead to an efficient algorithm for finding optimal solutions. Frame matroids are an important type of matroid, and frame matroids can be represented by biased graphs. Unfortunately, understanding all the biased graph representations of a given frame matroids is difficult, and little is known. We present a theorem which provides a rough biased graphical structure for representations of frame matroids that are sufficiently large, and discuss implications for understanding those substructures that cannot occur in any frame matroid.

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.

We conjecture that the class of frame matroids can be characterized by a sentence in the monadic second-order logic of matroids, and we prove that there is such a characterization for the class of bicircular matroids. The proof does not depend on an excluded-minor characterization.

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.