Count and cofactor matroids of highly connected graphs

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

Dániel Garamvölgyi, Csaba Király, Tibor Jordán

Publication date: 14 March 2024

Published in: Journal of Combinatorial Theory. Series B (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

count matroidrigid graphconnected matroidvertical connectivitycofactor matroid

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Connectivity (05C40) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Cites Work

• Title not available (Why is that?)
• Connected rigidity matroids and unique realizations of graphs
• Title not available (Why is that?)
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Generic Rigidity in the Plane
• Connectivity in bicircular matroids
• BICIRCULAR MATROIDS
• Title not available (Why is that?)
• The \(d\)-dimensional rigidity matroid of sparse graphs
• On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs
• Packing of rigid spanning subgraphs and spanning trees
• On matroidal families
• Highly connected rigidity matroids have unique underlying graphs
• Research problems from the 5th Slovenian Conference (Bled, 2003)
• Globally Rigid Augmentation of Rigid Graphs
• Abstract 3-Rigidity and Bivariate $C_2^1$-Splines II: Combinatorial Characterization

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)