CS 604 Assignment 1: my solutions

Problem 1

Prove that an element e in a matroid is contained in all bases if and only if it is not contained in any circuit.

Forward Implication. Suppose the element e is contained in all the bases. If it were contained in some circuit, we could remove it from that circuit and get an independent set A. Let $|C|$ denote the cardinality of the bases. If $|A|=|C|$ , A must be a basis which does not contain the element e and hence contradicts the fact that e is contained in all the bases. If $|A|<|C|$ , there must be a basis $B\supset A$ as A is not maximally independent. $e\notin B$ because $A\cup e$ is a circuit. But this contradicts the fact that e is contained in all the bases. Hence the hypothesis that e is contained in some circuit is false. Therefore, if an element is contained in all the bases, then it is not contained in any circuit.

Backward Implication. Suppose the element e is not contained in any circuit. If there were a basis B such that $e\notin B$ , then we could add e to B to get a dependent set. $B\cup e$ would then contain a circuit. The circuit cannot be completely contained in B as B is an independent set, and hence the circuit would contain the element e. But this contradicts the fact that e is not contained in any circuit. Hence our hypothesis that a basis contains e is false. Therefore, if an element is not contained in any circuit, then it is contained in the all the bases.

Problem 2

Let B be a collection of subsets of a finite set E, satisfying the following properties: a) B is not empty. b) For any two sets $B_{1}$ , $B_{2}$ in B, and any element e in $B_{1}$ , there exists an element f in $B_{2}$ such that $(B_{1}-e)\cup f$ is in B. Give an example to show that B need not be the set of bases of a matroid. Suppose, we add another condition: c) No subset in B is a proper subset of another subset in B. Now show that B must be the set of bases of some matroid.

Take $B=\{\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{3,1\},\{1,2,3\}\}$ . The collection B clearly satisfies the first two properties but the sets it contains cannot all be bases as they have different cardinalities.

Take two sets $B_{1}$ and $B_{2}$ in B. $B_{1}$ is not a proper subset of $B_{2}$ by the third property. By second property, for any element $e\in(B_{1}-B_{2})$ , $\exists f\in B_{2}$ such that $(B_{1}-e)\cup f$ is in B. If $f\in(B_{1}\cap B_{2})$ , $((B_{1}-e)\cup f)\subset B_{1}$ , but this is not allowed by third property. Hence $f\in(B_{2}-B_{1})$ . Therefore, the collection B satisfies the two properties:

•

B is not empty.
•

If $B_{1}$ and $B_{2}$ are distinct subsets in B, then for every $x\in(B_{1}-B_{2})$ , $\exists y\in(B_{2}-B_{1})$ such that $(B_{1}-x)\cup y$ is in B.

Hence, B must be the set of bases of some matroid.

Problem 3

Give an example of two matroids $M_{1}$ and $M_{2}$ on the same set E, such that a subset X of E is a circuit of $M_{1}$ iff X is a basis of $M_{2}$ . Characterize all possible such pairs of matroids.

For $m+1\leq n$ , take $M_{1}=U_{n,m}$ and $M_{2}=U_{n,m+1}$ with the same ground set E. The $m+1$ element subsets of E are exactly all the circuits in $M_{1}$ and all the bases in $M_{2}$ .

Problem 4

Let M be a matroid and X and Y be subsets of E(M), each of which contains a basis. Prove that if $|X|>|Y|$ then for some element x in $X-Y$ , $X-x$ also contains a basis.

Take the bases $B_{1}$ and $B_{2}$ such that $B_{1}\subset X$ and $B_{2}\subseteq Y$ . If there is an element $x\in(X-Y)$ such that $x\notin B_{1}$ , then $X-x$ contains the basis $B_{1}$ . Else, $X-Y\subset B_{1}$ and hence $|B_{1}\cap(X-Y)|=|X-Y|$ . $|X|>|Y|\Rightarrow|X-Y|>|Y-X|\Rightarrow|B_{1}\cap(X-Y)|>|B_{2}\cap(Y-X)|% \Rightarrow|B_{2}\cap(X\cap Y)|>|B_{1}\cap(X\cap Y)|$ . Construct basis $B_{3}$ as follows: start with $B_{2}$ and exchange the elements in $B_{2}\cap(Y-X)$ with elements in $B_{1}-B_{2}$ . $|B_{3}\cap(X\cap Y)|\geq|B_{2}\cap(X\cap Y)|>|B_{1}\cap(X\cap Y)|$ . Therefore, $|B_{3}\cap(X-Y)|<|B_{1}\cap(X-Y)|=|X-Y|$ . So, $\exists x\in(X-Y)-B_{3}$ and hence $X-x$ contains the basis $B_{3}$ .

Problem 5

Show that if $B_{1}$ , $B_{2}$ are any two distinct bases of a matroid, then for every element e in $B_{2}-B_{1}$ , there exists an element f in $B_{1}-B_{2}$ , such that $B_{1}+e-f$ is also a basis. Show that any non-empty collection of subsets satisfying the property must be the set of bases of a matroid.

For every e in $B_{2}-B_{1}$ , $(B_{1}\cap B_{2})\cup\{e\}$ is an independent set, since it is a subset of $B_{2}$ . Take $B_{3}=(B_{1}\cap B_{2})\cup\{e\}$ . While $|B_{3}|<|B_{1}|$ , we can add elements from $B_{1}-B_{3}\subseteq B_{1}-B_{2}$ to $B_{3}$ while keeping $B_{3}$ independent. Finally $|B_{3}|=|B_{1}|$ , and so $B_{3}$ is a basis. Also, $|(B_{3}\cap(B_{1}-B_{2}))\cup\{e\}|=|B_{1}-B_{2}|\Rightarrow|B_{3}\cap(B_{1}-B% _{2})|+1=|B_{1}-B_{2}|$ . Therefore there exists an element $f\in B_{1}-B_{2}$ not contained in $B_{3}$ , and $B_{3}=(B_{1}-\{f\})\cup\{e\}$ .

Now suppose B is a non-empty set which satisfies the given property. We wish to prove that if $B_{1}$ and $B_{2}$ are distinct subsets in B, then for every $e\in(B_{1}-B_{2})$ , $\exists f\in(B_{2}-B_{1})$ such that $(B_{1}-e)\cup f$ is in B. Suppose the statement were false, then for some e in $B_{1}-B_{2}$ , $(B_{1}-e)\cup f$ would not be in B for any $f\in B_{2}-B_{1}$ . Construct $B_{3}$ as follows: start with $B_{3}=B_{2}$ . From the set property, for every element $x\in B_{1}-B_{3}$ we can replace an element of $B_{3}-B_{1}$ with x, keeping $B_{3}$ in B. Do the replacements for every element in $B_{1}-B_{3}$ except e. Finally we obtain $B_{3}=(B_{1}-e)\cup f$ for some $f\in B_{2}$ . But this contradicts the presumption that $(B_{1}-e)\cup f$ is not in B. Hence the statement we wished to prove is true, and this implies that B is a basis set for some matroid.