Count and cofactor matroids of highly connected graphs

DOI10.1016/J.JCTB.2023.12.004arXiv2209.06204MaRDI QIDQ6196151

Author name not available (Why is that?)

Publication date: 14 March 2024

Published in: (Search for Journal in Brave)

Abstract: We consider two types of matroids defined on the edge set of a graph $G$: count matroids ${calM}_{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 $mathcalC(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 $einE(G)$, and ${calM}_{k,ell}(G)$ is connected. These bounds unify and extend several previous results, including theorems of Nash-Williams and Tutte ($k=ell$), and Lov'asz and Yemini ($k=2,ell=3$). We also prove that if $G$ is highly connected, then the vertical connectivity of $mathcalC(G)$ is also high. We use these results to generalize Whitney's celebrated result on the graphic matroid of $G$ (which corresponds to ${calM}_{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 ${calM}_{k,ell}(G)$ uniquely determines $G$; and similarly, if $G$ is $14$-connected, then its cofactor matroid $mathcalC(G)$ uniquely determines $G$. 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.

Full work available at URL: https://arxiv.org/abs/2209.06204

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Count and cofactor matroids of highly connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6196151)