论文标题
高度连接图的计数和辅因子矩阵
Count and cofactor matroids of highly connected graphs
论文作者
论文摘要
我们考虑在图$ g $的边缘定义的两种类型的曲霉：count Matroids $ {\ cal m} _ {k，\ ell}（g）$，其中独立性由涉及参数$ k $ and $ \ ell $的稀疏计数定义独立性是由$ g $的辅因子矩阵中的线性独立性定义的。对于每对$（k，\ ell）$，我们给出了紧密的下限，这表明如果$ g $足够高度连接，则$ g-e $在e（g）$中的所有$ e \ and $ e（g）$中的排名最高，并且连接了$ {\ cal m} _ {k，\ ell}（g）$。这些边界统一并扩展了几个先前的结果，包括Nash-Williams和Tutte的定理（$ K = \ ell $），以及Lovász和Yemini（$ K = 2，\ ell = 3 $）。我们还证明，如果$ g $高度连接，则$ \ Mathcal {C}（g）$的垂直连接也很高。 我们使用这些结果将惠特尼的庆祝结果概括为$ g $的图形矩阵（对应于$ {\ cal m} _ {1,1}}（g）$）对所有计数Matroid count count count count count count and Cofactor Matroid：to三维辅助手Matroid：如果$ g $高度连接，则根据$ k $和$ k $ $ \ el $ $ \ el $， m} _ {k，\ ell}（g）$唯一确定$ g $;同样，如果$ g $是$ 14 $连接的，则其cofactor Matroid $ \ mathcal {c}（g）$唯一确定$ g $。我们还获得了三维辅因子Matroid的$ t $ fold联合的类似结果，并使用它们证明，每$ 24 $连接的图都有一个跨越的树$ t $，$ g-e（t）$是$ 3 $ connected的$ 3 $ connected，这证实了一种推测Kriesell的案例。
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ász 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.
