Assignment 2: my solutions

Take two circuits in a binary matroid with columns $a_1,\mathrm{\dots },a_k,b_1,\mathrm{\dots },b_l$ in the first circuit and $b_1,\mathrm{\dots },b_l,c_1,\mathrm{\dots },c_m$ in the second circuit. Therefore we have the following two relations:

Adding the two equations, and remembering that the field is ${\mathbb{Z}}_2$, we get

which is a relation for the XOR elements of the two circuits. Hence the elements in the XOR subset are dependent. If all the elements form a circuit, the property is proved. Else, the XOR subset must have a circuit properly contained in it. We prove the statement by induction on size $n$ of XOR subset. The statement clearly holds for $n=1$. Assume the statement holds for all sizes less than $n$. Relabel the XOR elements as $x_1,\mathrm{\dots },x_n$ where $x_1,\mathrm{\dots },x_p$ with form a circuit. We then have

By induction hypothesis, $x_{p+1},\mathrm{\dots },x_n$ form a disjoint union of circuits, which are disjoint from the circuit $x_1,\mathrm{\dots },x_p$. Hence the property is proved.

Claim: If two circuits $C_1$ and $C_2$ have one element in common, then size of $C_1$ and $C_2$ is 2.
Proof: Let $C_1$ and $C_2$ have one element in common, say $e$, then by property of circuits, there must be a circuit in $C_3$ in $C_1\cup C_2-e$. But $C_3$ can intersect with $C_1$ and $C_2$ in only one element. Therefore $C_3=x\cup y$ where $x\in C_1-e$ and $y\in C_2-e$. But $C_3\cup C_2-x$ must have a circuit which intersects with $C_2$ in atmost one element. If size of $C_1$ is greater than 2, this circuit cannot be $y\cup e$ else it will be properly contained in $C_1$. Let this circuit be $C_4=y\cup z$ where $z\in C_2$. Then there must be a circuit in $C_4\cup C_3-y=x\cup z$ which is contained entirely in $C_2$. But since this can not be true, size of $C_1$ must be true. Same argument holds for $C_2$.

Also, from the argument, it is evident that if $x\cup y$ forms a circuit and $y\cup z$ form a circuit, then $x\cup z$ form a circuit. Therefore, these edges may be represented as a set of parallel edges in a graph. A circuit which does not intersect with any other circuit may be represented by a simple cycle in the graph. All the remaining elements of the ground set can be put as a disjoint forest in the graph. The cycle matroid obtained from the graph is then isomorphic to the original matroid.

Consider the collection $C$ of the subsets. We show that the collection satisfies the three circuit properties and choose to temporarily call the subsets as ’circuits’. Name the circuits that satisfy (i) as ’Type 1’ circuits and those that satisfy (ii) as ’Type 2’ circuits.
(i)$\varphi \notin C$.
(ii) Since no proper subset of a simple cycle is a simple cycle, no subset of Type 1 circuit is a circuit. Since the only proper subsets of Type 2 circuits that are union of edge disjoint simple cycles are simple cycles with odd weight, they do not form a circuit. Hence no circuit is a proper subset of another circuit.
(iii) Take two circuits $C_1$ and $C_2$.
Case a: $C_1$ and $C_2$ are type 1 circuits, then their XOR is a disjoint union of simple cycles and the weight of all cycles add up to an even number. Then there must be atleast one cycle of even weight or two cycles of odd weights. Thus, we have a circuit in every $C_1\cup C_2-e$ where $e\in C_1\cap C_2$.
Case b: $C_1$ and $C_2$ are type 1 and type 2 circuits respectively. Then the XOR of $C_1$ with one cycle of $C2$ is a disjoint union of simple cycles, and the XOR of $C_1$ with the other cycle of $C2$ is a also a disjoint union of simple cycles. The XOR of the unions is also a disjoint union of simple cycles with total weight even and hence by similar argument as in case a, will have a circuit.
Case c: Arguments similar to previous cases show that the XOR must have a circuit.
Therefore, the collection indeed is a collection of circuits for the matroid.

Claim: Size of C is b which is the size of the bases in the matroid.
Proof: Size of C cannot be greater than b as removal of a single element from the circuit C gives an independent set which is not a basis. Size of C cannot be less than b as addition of a single element gives a dependent set which contains a basis. Hence, size of C must be b.

We show that adding C to the collection of independent sets gives a matroid. All properties of independent sets were satisfied in the original matroid, i.e. for all sets except C in the new collection. As C was a circuit in the original matroid, all it’s subsets were independent and are present in the collection. Cardinality of C is the highest among the independent set (as shown in the claim above), so now we only need to prove that for any set $X$ in C with there exists a $c\in C$ such that $X\cup c$ is independent. If then the there exists such a c as C originally contained an independent set of b-1. If $|X|=b-1$, we have two cases:
(i) All elements of $X$ are present in $C$ in which case we can just add $C-X$ to X and get the set C which is in the collection.
(ii) There exists an element $y\in X$ such that $y\notin C$. Adding y to C in the original matroid gives a basis B contained in $C\cup \{e\}$. Therefore there must be an element in $B-X$ which when added to $X$ gives an independent set in the original matroid and hence a set in the collection. And since $B-X\subseteq C$, proof is complete.