Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCharacterizing matroids whose bases form graphic delta-matroids
135
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We introduce delta-graphic matroids, which are matroids whose bases form graphic delta-matroids. The class of delta-graphic matroids contains graphic matroids as well as cographic matroids and is a proper subclass of the class of regular matroids. We give a structural characterization of the class of delta-graphic matroids. We also show that every forbidden minor for the class of delta-graphic matroids has at most $48$ elements.
rate research
Read More
For an abelian group $Gamma$, a $Gamma$-labelled graph is a graph whose vertices are labelled by elements of $Gamma$. We prove that a certain collection of edge sets of a $Gamma$-labelled graph forms a delta-matroid, which we call a $Gamma$-graphic delta-matroid, and provide a polynomial-time algorithm to solve the separation problem, which allows us to apply the symmetric greedy algorithm of Bouchet to find a maximum weight feasible set in such a delta-matroid. We present two algorithmic applications on graphs; Maximum Weight Packing of Trees of Order Not Divisible by $k$ and Maximum Weight $S$-Tree Packing. We also discuss various properties of $Gamma$-graphic delta-matroids.
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.
We give upper and lower bounds on the number of delta-matroids, and on the number of even delta-matroids.
Let $M$ be a 3-connected matroid and let $mathbb F$ be a field. Let $A$ be a matrix over $mathbb F$ representing $M$ and let $(G,mathcal B)$ be a biased graph representing $M$. We characterize the relationship between $A$ and $(G,mathcal B)$, settling four conjectures of Zaslavsky. We show that for each matrix representation $A$ and each biased graph representation $(G,mathcal B)$ of $M$, $A$ is projectively equivalent to a canonical matrix representation arising from $G$ as a gain graph over $mathbb F^+$ or $mathbb F^times$. Further, we show that the projective equivalence classes of matrix representations of $M$ are in one-to-one correspondence with the switching equivalence classes of gain graphs arising from $(G,mathcal B)$.
We investigate valuated matroids with an additional algebraic structure on their residue matroids. We encode the structure in terms of representability over stringent hyperfields. A hyperfield $H$ is {em stringent} if $aboxplus b$ is a singleton unless $a=-b$, for all $a,bin H$. By a construction of Marc Krasner, each valued field gives rise to a stringent hyperfield. We show that if $H$ is a stringent skew hyperfield, then the vectors of any weak matroid over $H$ are orthogonal to its covectors, and we deduce that weak matroids over $H$ are strong matroids over $H$. Also, we present vector axioms for matroids over stringent skew hyperfields which generalize the vector axioms for oriented matroids and valuated matroids.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
