Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn excluded minors of connectivity 2 for the class of frame matroids
154
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We investigate the set of excluded minors of connectivity 2 for the class of frame matroids. We exhibit a list $mathcal{E}$ of 18 such matroids, and show that if $N$ is such an excluded minor, then either $N in mathcal{E}$ or $N$ is a 2-sum of $U_{2,4}$ and a 3-connected non-binary frame matroid.
rate research
Read More
Frame matroids and lifted-graphic matroids are two distinct minor-closed classes of matroids, each of which generalises the class of graphic matroids. The class of quasi-graphic matroids, recently introduced by Geelen, Gerards, and Whittle, simultaneously generalises both the classes of frame and lifted-graphic matroids. Let $mathcal{M}$ be one of these three classes, and let $r$ be a positive integer. We show that $mathcal{M}$ has only a finite number of excluded minors of rank $r$.
We show that the class of bicircular matroids has only a finite number of excluded minors. Key tools used in our proof include representations of matroids by biased graphs and the recently introduced class of quasi-graphic matroids. We show that if $N$ is an excluded minor of rank at least eight, then $N$ is quasi-graphic. Several small excluded minors are quasi-graphic. Using biased-graphic representations, we find that $N$ already contains one of these. We also provide an upper bound, in terms of rank, on the number of elements in an excluded minor, so the result follows.
The cut-rank of a set $X$ in a graph $G$ is the rank of the $Xtimes (V(G)-X)$ submatrix of the adjacency matrix over the binary field. A split is a partition of the vertex set into two sets $(X,Y)$ such that the cut-rank of $X$ is less than $2$ and both $X$ and $Y$ have at least two vertices. A graph is prime (with respect to the split decomposition) if it is connected and has no splits. A graph $G$ is $k^{+ell}$-rank-connected if for every set $X$ of vertices with the cut-rank less than $k$, $lvert Xrvert$ or $lvert V(G)-Xrvert $ is less than $k+ell$. We prove that every prime $3^{+2}$-rank-connected graph $G$ with at least $10$ vertices has a prime $3^{+3}$-rank-connected pivot-minor $H$ such that $lvert V(H)rvert =lvert V(G)rvert -1$. As a corollary, we show that every excluded pivot-minor for the class of graphs of rank-width at most $k$ has at most $(3.5 cdot 6^{k}-1)/5$ vertices for $kge 2$. We also show that the excluded pivot-minors for the class of graphs of rank-width at most $2$ have at most $16$ vertices.
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.
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)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
