We consider two types of matroids defined on the edge set of a graph G: (k,l)-count matroids, in which independence is defined by a sparsity count involving the parameters k and l, and the (generic C^1_2-)cofactor matroid, in which independence is defined by linear independence in the C^1_2-cofactor matrix of G. We give tight lower bounds, for each pair (k,l), that show that if G is sufficiently highly connected, then G-e has maximum rank for all edge e of G, and the (k,l)-count matroid of G is connected. These bounds unify and extend several previous results, including theorems of Nash-Williams and Tutte (k=l=1), and Lovász and Yemini (k=2, l=3). We also prove that if G is highly connected, then the vertical connectivity of the co-factor matroid of G is also high.

We use these results to generalize Whitney's celebrated result on the graphic matroid of G (which corresponds to the case where k=l=1) to all count matroids and to the C^1_2-cofactor matroid: if G is highly connected, depending on k and l, then its (k,l)-count matroid uniquely determines G; and similarly, if G is 14-connected, then its cofactor matroid uniquely determines G. We also derive similar results for the t-fold union of the C^1_2-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.

Joint work with Tibor Jordán and Dániel Garamvölgyi.