تقرير
Count and cofactor matroids of highly connected graphs
| العنوان: | Count and cofactor matroids of highly connected graphs |
|---|---|
| المؤلفون: | Garamvölgyi, Dániel, Jordán, Tibor, Király, Csaba |
| المصدر: | Journal of Combinatorial Theory, Series B, 2024 |
| سنة النشر: | 2022 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics |
| الوصف: | We consider two types of matroids defined on the edge set of a graph $G$: count matroids ${\cal M}_{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 $\mathcal{C}(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 $e\in E(G)$, and ${\cal M}_{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 $\mathcal{C}(G)$ is also high. We use these results to generalize Whitney's celebrated result on the graphic matroid of $G$ (which corresponds to ${\cal M}_{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 ${\cal M}_{k,\ell}(G)$ uniquely determines $G$; and similarly, if $G$ is $14$-connected, then its cofactor matroid $\mathcal{C}(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. |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.1016/j.jctb.2023.12.004 |
| URL الوصول: | http://arxiv.org/abs/2209.06204 |
| رقم الأكسشن: | edsarx.2209.06204 |
| قاعدة البيانات: | arXiv |
كن أول من يترك تعليقا!