Subgraph complementation and minimum rank

Given any finite simple graph $G = (V,E)$, there exists a collection $\mathscr{C}$ of subsets of $V$ in which two vertices appear together in an odd number of subsets if and only if they are adjacent in $G$. Equivalently, it is always possible to obtain $G$ from the empty graph on $V$ by a sequence of {\em subgraph complementations}, the operation of complementing an induced subgraph of $G$. It is natural to ask for the minimum cardinality of such a collection $\mathscr{C}$, or for the minimum number of subgraph complementations needed, which we denote by $c_2(G)$. This problem is closely related to the minimum rank problem; we show that $c_2 (G) = \operatorname{mr}(G,\mathbb{F}_2)$ when $\operatorname{mr}(G,\mathbb{F}_2)$ is odd or when $G$ is a forest. Otherwise, $\operatorname{mr}(G,\mathbb{F}_2)\leq c_2 (G)\leq \operatorname{mr}(G,\mathbb{F}_2)+1$. We then examine a few conditions equivalent to $c_2(G) = \operatorname{mr}(G,\mathbb{F}_2) + 1$. Finally, the class of graphs with $c_2(G) \leq k$ is hereditary and finitely defined for any natural number $k$, and we exhibit the sets of minimal forbidden induced subgraphs for small values of $k$.
Joint work with Christopher Purcell and Puck Rombach.