Count and cofactor matroids of highly connected graphs

DOI10.1016/J.JCTB.2023.12.004MaRDI QIDQ6196151zbMATH OpenFDO

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

Publication date 14 March 2024

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

cofactor matroidconnected matroidcount matroidrigid graphvertical connectivity

Mathematics Subject Classification ID

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

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.

Review text

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.

Recommendations

• Highly connected rigidity matroids have unique underlying graphs
• About count matroids
• On minimally \(k\)-connected matroids
• The connectivity and minimum degree of circuit graphs of matroids
• The highly connected matroids in minor-closed classes

Cites work

• Abstract 3-Rigidity and Bivariate C₂¹-Splines II: Combinatorial Characterization
• BICIRCULAR MATROIDS
• Connected rigidity matroids and unique realizations of graphs
• Connections in combinatorial optimization
• Connectivity in bicircular matroids
• Edge-Disjoint Spanning Trees of Finite Graphs
• Globally rigid augmentation of rigid graphs
• Highly connected rigidity matroids have unique underlying graphs
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 952952 (Why is no real title available?)
• scientific article; zbMATH DE number 3301261 (Why is no real title available?)
• scientific article; zbMATH DE number 3313442 (Why is no real title available?)
• On Generic Rigidity in the Plane
• On matroidal families
• On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs
• On the Problem of Decomposing a Graph into n Connected Factors
• Packing of rigid spanning subgraphs and spanning trees
• Research problems from the 5th Slovenian Conference (Bled, 2003)
• The d-dimensional rigidity matroid of sparse graphs

Cited in

(2)

• Rigidity and reconstruction in matroids of highly connected graphs
• Highly connected orientations from edge-disjoint rigid subgraphs

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)