Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMatrix representations of frame and lifted-graphic matroids correspond to gain functions
131
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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)$.
rate research
Read More
Given a 3-connected biased graph $Omega$ with a balancing vertex, and with frame matroid $F(Omega)$ nongraphic and 3-connected, we determine all biased graphs $Omega$ with $F(Omega) = F(Omega)$. As a consequence, we show that if $M$ is a 4-connected nongraphic frame matroid represented by a biased graph $Omega$ having a balancing vertex, then $Omega$ essentially uniquely represents $M$. More precisely, all biased graphs representing $M$ are obtained from $Omega$ by replacing a subset of the edges incident to its unique balancing vertex with unbalanced loops.
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 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.
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.
A {em connectivity function} on a set $E$ is a function $lambda:2^Erightarrow mathbb R$ such that $lambda(emptyset)=0$, that $lambda(X)=lambda(E-X)$ for all $Xsubseteq E$, and that $lambda(Xcap Y)+lambda(Xcup Y)leq lambda(X)+lambda(Y)$ for all $X,Y subseteq E$. Graphs, matroids and, more generally, polymatroids have associated connectivity functions. In this paper we give a method for identifying when a connectivity function comes from a graph. This method uses no more than a polynomial number of evaluations of the connectivity function. In contrast, we show that the problem of identifying when a connectivity function comes from a matroid cannot be solved in polynomial time. We also show that the problem of identifying when a connectivity function is not that of a matroid cannot be solved in polynomial time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
