CS 604 Assignment 6: my solutions

Connectivity

Problem 1

Let M be a matroid and X a subset of E(M) such that $M|X$ is connected. Find necessary and sufficient conditions for $M|cl(X)$ to be connected.

X is contained in a connected component of M. $M|cl(X)$ will not be connected if there exists an element $r(X\cup y)=r(X)$ , which lies in a different component. Let A be the largest independent subset in X. Since $y\cup A$ is independent if y is independent and in another connected component, y can belong to the closure if and only if it is a loop. Therefore, necessary and sufficient condition for $M|cl(X)$ to be connected is that there shouldn’t be any loops in the matroid.

Problem 2

Let M be a connected matroid such that $M\backslash e$ is disconnected for all elements e in E(M). Prove that M has a cocircuit of size 2. Also show that every circuit in M is a flat, that $cl(C)=C$ for any circuit C. Suppose M is an n-connected matroid such that $M\backslash e$ is not n-connected for all elements e. Does M necessarily contain a cocircuit of size n?

Since M is connected there must be at-least one circuit C in the matroid. We then use the theorem that if $M\backslash e_{i}$ is disconnected for all $e_{i}\in C$ , then there exists a co-circuit of size 2 in the circuit.

Let $x$ be an element outside C. We show that $x\cup C$ does not contain a circuit, else $x$ would be in the closure of C. Suppose it did contain a circuit $C_{1}$ . Then any 2 elements $e, f$ which were connected through a circuit $C_{2}$ containing $x$ would still be connected. To check this, observe that there exists a circuit $C_{3}$ in $C_{1}\cup C_{2}-x$ containing e. Similarly, there exists a circuit $C_{4}$ in $C_{1}\cup C_{2}-x$ containing $f$ . Now $e$ is connected to some $c_{1}\in C$ through $C_{3}$ , $c_{1}$ through C is connected to $c_{2}$ , which is connected to $f$ through $C_{4}$ . Hence $e$ is connected to $f$ through circuits not involving $x$ . Since this holds for all $e, f$ , deleting $x$ leaves the graph connected, which contradicts the property that deletion of any element disconnects the matroid.

Problem 3

Let M be a connected matroid with at least two elements and let e be an arbitrary element. Suppose the largest circuit containing e has $l$ elements. Prove that there exist $l-1$ cocircuits, each containing e, whose union is E(M).

Problem 4

Suppose that x and y are distinct elements of an n-connected matroid M, where $n\geq 2$ and $|E(M)|\geq 2(n-1)$ . Suppose that $M\backslash x/y$ is n-connected but $M\backslash x$ is not. Prove that M has a cocircuit of size n containing x and y.

Problem 5

Let M be the 2-sum of two connected matroids $M_{1}$ and $M_{2}$ . Prove that there exists a minor of M isomorphic to $M_{1}$ and a minor of M isomorphic to $M_{2}$ . Let N be a 3-connected minor of M. Prove that N is a minor of either $M_{1}$ or $M_{2}$ .

Let $E_{1}$ be the edge set in M derived from $M_{1}$ , similarly $E_{2}$ from $M_{2}$ . There exists a circuit C with elements in both $E_{1}$ and $E_{2}$ . Delete $E_{2}-C$ from $M$ and contract all but one elements of $C-E_{1}$ . Circuits are preserved under contraction and it is easy to check from the 2-sum construction (via circuits) that the circuits in the obtained matroid are same as circuits of $M_{1}$ . The matroid obtained is isomorphic to $M_{1}$ .

M is the 2-sum of $M_{1}$ and $M_{2}$ . There is a 2-separation between $M_{1}$ and $M_{2}$

\lambda_{M}(X)=r_{M}(E_{1})+r_{M}(E_{2})-r(M)+1

If $r(M)$ decreases then either $r_{M}(E_{1})$ or $r_{M}(E_{2})$ would also decrease as independent sets in M are unions of independent sets from $M_{1}$ and $M_{2}$ (subtracting p). Therefore, connectivity between $E_{1}$ and $E_{2}$ would not increase upon contraction or deletion. Therefore, if N has to be 3-connected, it must be restricted to either $M_{1}$ or $M_{2}$ in which case it will be a minor of the either of the two.