Describing quasi-graphic matroids

DOI10.1016/J.EJC.2019.103062MaRDI QIDQ2297919zbMATH OpenOpenAlexWikidataFDO

Authors Nathan Bowler, Daryl Funk, Daniel Slilaty

Publication date 20 February 2020

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.00489

zbMATH Keywords

biased graphbiased-graphic matroidlift matroid

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)

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,mathcalB)$ Zaslavsky defined a unique lift matroid $L(G,mathcalB)$ and a unique frame matroid $F(G,mathcalB)$, 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,mathcalB)$ while containing those of $L(G,mathcalB)$, for some biased graph $(G,mathcalB)$. 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.

Recommendations

• Quasi-graphic matroids
• Biased graphs. II: The three matroids
• Almost balanced biased graph representations of frame matroids
• Graphical representations of graphic frame matroids
• Frame matroids and biased graphs

Cites work

• Bias matroids with unique graphical representations
• Biased graphs IV: Geometrical realizations
• Biased graphs. I: Bias, balance, and gains
• Biased graphs. II: The three matroids
• Biased graphs. III: Chromatic and dichromatic invariants
• Frame matroids and biased graphs
• scientific article; zbMATH DE number 3351601 (Why is no real title available?)
• Infinitely many excluded minors for frame matroids and for lifted-graphic matroids
• Lectures on matroids
• Non-Separable and Planar Graphs
• On recognizing frame and lifted-graphic matroids
• Quasi-graphic matroids
• The highly connected matroids in minor-closed classes

Cited in

(8)

• On excluded minors for classes of graphical matroids
• Matrix representations of frame and lifted-graphic matroids correspond to gain functions
• Quasi-graphic matroids
• The 9-connected excluded minors for the class of quasi-graphic matroids
• Obstructions for bounded branch-depth in matroids
• Cobiased graphs: single-element extensions and elementary quotients of graphic matroids
• Corrigendum to: ``Describing quasi-graphic matroids
• Graphical representations of graphic frame matroids

This page was built for publication: Describing quasi-graphic matroids

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