Count and cofactor matroids of highly connected graphs

Garamvölgyi, Dániel and Jordán, Tibor and Király, Csaba (2024) Count and cofactor matroids of highly connected graphs. JOURNAL OF COMBINATORIAL THEORY SERIES B, 166. pp. 1-29. ISSN 0095-8956

Preview

Text 2209.06204v2.pdf Available under License Creative Commons Attribution. Download (422kB) | Preview

Abstract

We consider two types of matroids defined on the edge set of a graph G: count matroids Mk,ℓ(G), in which independence is defined by a sparsity count involving the parameters k and ℓ, and the C1 2 -cofactor matroid C(G), in which independence is defined by linear independence in the cofactor matrix of G. We show, for each pair (k, ℓ), that if G is sufficiently highly connected, then G − e has maximum rank for all e ∈ E(G), and the matroid Mk,ℓ(G) is connected. These results unify and extend several previous results, including theorems of Nash-Williams and Tutte (k = ℓ = 1), and Lov´asz and Yemini (k = 2, ℓ = 3). We also prove that if G is highly connected, then the vertical connectivity of C(G) is also high. We use these results to generalize Whitney’s celebrated result on the graphic matroid of G (which corresponds to M1,1(G)) to all count matroids and to the C1 2 - cofactor matroid: if G is highly connected, depending on k and ℓ, then the count matroid Mk,ℓ(G) uniquely determines G; and similarly, if G is 14-connected, then its C1 2 -cofactor matroid C(G) uniquely determines G. We also derive similar results for the t-fold union of the C1 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.

Actions (login required)

Edit Item