Bonus Problem: my solutions

Consider the circuit space of a rank-r binary matroid having no two disjoint circuits. Since the XOR of two circuits in a binary matroid is a disjoint union of circuits, and the are no two disjoint circuits, the XOR must itself be a circuit. Since the rank of the matroid is r, there exists an r-element subset of the ground set not containing any circuit. Label this subset E, $|E|=r$. Label the elements outside the set as $c_1,c_2,\mathrm{\dots }{c}_{n-r}$, where n is the cardinality of the ground set G. However, every (r+1)-element subset of ground set must contain a circuit. And hence there must be a circuit in $E\cup c_1$. Label this circuit $C_1$. There cannot be any other circuit in $E\cup c_1$ else either that circuit or its XOR with $C_1$ would be in E. Similarly we obtain circuits $C_2,C_3\mathrm{\dots }{C}_{n-r}$ for each of the subsets $E\cup c_2,E\cup c_3,\mathrm{\dots },E\cup c_{n-r}$. Now, if a circuit C has $C\cap E^c={\cup }_{i\in \mathrm{\Lambda }}\{c_i\}$ for some subset $\mathrm{\Lambda }$ of $N=\{1,\mathrm{\dots },n-r\}$, it must be ${⨁}_{i\in \mathrm{\Lambda }}{C}_i$, else its XOR with ${⨁}_{i\in \mathrm{\Lambda }}{C}_i$ will be a subset contained in E, which cannot not be a circuit.

Hence we see that any circuit C can be written as ${⨁}_{i\in \mathrm{\Lambda }}{C}_i$ for some subset $\mathrm{\Lambda }$ of $N=\{1,\mathrm{\dots }n-r\}$. Furthermore, the following properties have to be satisfied

• •

  Now $|\mathrm{\Lambda }|$ is the number of elements in $C\cap E^c$, and hence the maximum number of elements in $C\cap E$ can be $r+1-|\mathrm{\Lambda }|$.

• •

  Also since no circuit can be a proper subset of other, we must have that ${⨁}_{i\in \lambda }{C}_i$ must not be a subset of ${⨁}_{i\in \mathrm{\Lambda }}{C}_i$ for $\lambda \subset \mathrm{\Lambda }$. This is equivalent to condition that $E\cap {⨁}_{i\in \lambda }{C}_i$ not be a subset of $E\cap {⨁}_{i\in \mathrm{\Lambda }}{C}_i$. This is also equivalent to condition that $E\cap {⨁}_{i\in \lambda }{C}_i$ should not be disjoint from $E\cap {⨁}_{i\in {\lambda }^c}{C}_i$

• •

  Every (r+1)-subset must have a circuit contained in it. Hence, for every (r+1) subset S of G, there exists a circuit $C={⨁}_{i\in \lambda }{C}_i$, $\lambda \subseteq \mathrm{\Lambda }$ where ${\cup }_{i\in \mathrm{\Lambda }}\{c_i\}=S\cap E^c$, such that $E\cap {⨁}_{i\in \lambda }{C}_i\subseteq S\cap E^c$.
  

From the condition that number of elements in C has to be less than or equal to $r+1-|\mathrm{\Lambda }|$, we get a naive upper bound, $r+1-(n-r)\ge 0\Rightarrow n\le 2r+1$.

A better bound can be obtained as follows. Take any subset A of $E^c$ such that $|A|=a$ and $A={\cup }_{i\in \lambda }{c}_i$, then for every $r+1-a$ subset in E, its union with A should contain a circuit. From the second property, $C={⨁}_{i\in N-\lambda }{C}_i$ must intersect with every $r+1-a$ subset in E, and hence must have at-least $r-(r-a)=a$ elements from E in addition to $p-a\equiv (n-r)-a=|N-\lambda |$ elements from $E^c$. These combined must be less than or equal to $r+1$.