|
We consider two types of matroids defined on the edge set of a graph $G$:
count matroids ${\cal M}_{k,\ell}(G)$, in which independence is defined by a sparsity count
involving the parameters $k$ and $\ell$, and the (three-dimensional generic) cofactor matroid $\mathcal{C}(G)$, in which independence is defined by
linear independence in the cofactor matrix of $G$.
We give tight lower bounds, for each pair $(k,\ell)$, that show that if $G$ is sufficiently highly connected, then
$G-e$ has maximum rank for all $e\in E(G)$, and
${\cal M}_{k,\ell}(G)$ is connected. These bounds unify and extend several previous results, including theorems
of Nash-Williams and Tutte ($k=\ell=1$), and Lov\'asz and Yemini ($k=2, \ell=3$).
We also prove that if $G$ is highly connected, then the vertical connectivity of $\mathcal{C}(G)$ is also high.
We use these results
to generalize
Whitney's celebrated result on the graphic matroid of $G$ (which corresponds to ${\cal M}_{1,1}(G)$)
to all count matroids and to the
three-dimensional cofactor matroid: if $G$ is highly connected, depending on $k$ and $\ell$, then the count matroid
${\cal M}_{k,\ell}(G)$ uniquely determines $G$; and similarly, if $G$ is $14$-connected, then its cofactor matroid $\mathcal{C}(G)$ uniquely determines $G$.
%A version of the latter result was conjectured by B. Servatius and H. Servatius.
We also derive similar results for the $t$-fold union of the three-dimensional cofactor matroid, and use them to prove that every $24$-connected graph has a spanning tree $T$ for which $G-E(T)$ is
$3$-connected, which verifies a case of a conjecture of Kriesell.
Bibtex entry:
| AUTHOR | = | {Garamvölgyi, D{\'a}niel and Jord{\'a}n, Tibor and Kir{\'a}ly, Csaba}, |
| TITLE | = | {Count and cofactor matroids of highly connected graphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2022}, |
| NUMBER | = | {TR-2022-12} |