|
|
Connectivity |
|
|
|
||
|
This is an important topic in matroid theory as well as in graph theory, but again I'll only give a light, short treatment of it here. First I should mention connectivity in graphs: A graph is said to be connected if you can travel from any one vertex to any other by moving along paths of edges. The graph is 2-connected if you can delete any vertex and still remain connected; it's 3-connected if you can remove any two vertices and still remain connected, and so on. We require that a k-connected graph have at least k + 1 vertices. A vertex cutset of a connected is a subset of the vertices of a graph, whose removal (simultaneously removing all edges adjacent to those vertices) makes the graph no longer connected. If X and Y are two subgraphs of a given graph (which do not share edges), and Z is some subgraph of the same graph for which any path connecting X to Y must contain a vertex of Z, then we say that Z is a barrier between X and Y. Note that a cutset is a barrier between at least two portions of the graph in question, and note also that for a given barrier Z, there may be many possible X's and Y's. The maximal possible X's and Y's we call the bridges of Z; Z is a barrier between any two of its bridges. A nontrivial bridge of Z contains at least one vertex not in Z. (We note that one can say a graph is k-connected if no subset of its vertex set of size k or greater has two or more nontrivial bridges.) A great deal is known about connectivity in graphs, and since there's a lot of other concepts that extend from graphs to matroids, it would be very nice to have connectivity fully extend to matroids too. Unfortunately, this concept of connectivity, if taken directly to matroids, doesn't "work" when we start taking duals of matroids (which is a standard tool). So we use a slightly different definition for matroid connectivity: A matroid is said to have a k-separation if you can find a partition (X, Y) of the ground set E such that A couple things to note: because of a property of the rank function r, r(X) + r(Y) - r(E) is always at least 0, and so we'll never have a 0-separation or less. It's common to say just connected instead of 2-connected, as if we have a 1-separation we want to say we're disconnected (remember, if we have no 1-separation then we're at least 2-connected, but having no 1-separation means that we're not disconnected). Finally, it's interesting to note the following characterization of disconnected matroids: Theorem. A matroid M is disconnected (i.e. it has a 1-separation) iff there exists a partition (X, Y) of the ground set E such that every circuit C of M is either a subset of X or a subset of Y. Matroid and graph connectivity are both very important to my research. Whittle in his papers outlines a great many important results known about 3-connected matroids which he uses heavily in his proofs, and I myself had to rely very heavily on graph connectivity to obtain my own results. |
||
|
|
||