Description
EGERVÁRY SZEMINÁRIUM
Absztrakt:
We consider two types of matroids defined on the edge set of a graph
G: count matroids in which independence is defined by a sparsity count
involving two parameters k and l, and the (three-dimensional generic)
cofactor matroid, in which independence is defined by linear
independence in the cofactor matrix of G.
We give tight lower bounds, for each pair (k,l), that show that if G
is sufficiently highly connected, then G-e has maximum rank for all
edge e of G, and the (k,l)-count matroid is connected. These bounds
unify and extend several previous results, including theorems of
Nash-Williams and Tutte (k=l=1), and Lovász and Yemini (k=2, l=3). We
also prove that if G is highly connected, then the vertical
connectivity of its cofactor matroid is also high.
We use these results to generalize Whitney's celebrated result on the
graphic matroid of G to all count matroids and to the
three-dimensional cofactor matroid: if G is highly connected,
depending on k and $, then its (k,l)-count matroid uniquely determines
G; and similarly, if G is 14-connected, then its cofactor matroid
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.
Joint results with Tibor Jordán and Dániel Garamvölgyi.