Count and cofactor matroids of highly connected graphs (Q6196151): Difference between revisions

In this paper, the authors consider two types of matroids defined on the edge set of a graph \(G\): count matroids \(\mathcal{M}_{k,\ell}(G)\), in which independence is defined by a sparsity count involving the parameters \(k\) and \(\ell\), and the \(C_{2}^{1}\)-cofactor matroid \(\mathcal{C}(G)\), in which independence is defined by linear independence in the cofactor matrix of \(G\). It is shown, for each pair \((k, \ell)\), that if \(G\) is sufficiently highly connected, then \(G -e\) has maximum rank for all \(e \in E(G)\), and the matroid \(\mathcal{M}_{k,\ell}(G)\) is connected. These results unify and extend several previous results, including theorems of \textit{C. St. J. A. Nash-Williams} [J. Lond. Math. Soc. 36, 445--450 (1961; Zbl 0102.38805)] and \textit{W. T. Tutte} [J. Lond. Math. Soc. 36, 221--230 (1961; Zbl 0096.38001)] \((k = \ell = 1)\), and \textit{L. Lovász} and \textit{Y. Yemini} (\(k = 2\), \(\ell = 3\)) [SIAM J. Algebraic Discrete Methods 3, 91--98 (1982; Zbl 0497.05025)]. They also prove that if \(G\) is highly connected, then the vertical connectivity of \(\mathcal{C}(G)\) is also high. These results are used to generalize \textit{H. Whitney}'s celebrated result [Am. J. Math. 55, 245--254 (1933; Zbl 0006.37005)] on the graphic matroid of \(G\) (which corresponds to \(\mathcal{M}_{1,1}(G)\)) to all count matroids and to the \(C_{2}^{1}\)-cofactor matroid: if \(G\) is highly connected, depending on \(k\) and \(\ell\), then the count matroid \(\mathcal{M}_{k,\ell}(G)\) uniquely determines \(G\); and similarly, if \(G\) is 14-connected, then its \(C_{2}^{1}\)-cofactor matroid \(\mathcal{C}(G)\) uniquely determines \(G\). Similar results are shown for the \(t\)-fold union of the \(C_{2}^{1}\)-cofactor matroid, and the authors 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 [\textit{B. Mohar} et al., Discrete Math. 307, No. 3--5, 650--658 (2007; Zbl 1109.05102)]. A new conjecture concludes the paper.