Subgraph complementation and minimum rank (Q2121776)

Summary: Any finite simple graph \(G = (V,E)\) can be represented by a collection \(\mathscr{C}\) of subsets of \(V\) such that \(uv\in E\) if and only if \(u\) and \(v\) appear together in an odd number of sets in \(\mathscr{C}\). Let \(c_2(G)\) denote the minimum cardinality of such a collection. This invariant is equivalent to the minimum dimension of a faithful orthogonal representation of \(G\) over \(\mathbb{F}_2\) and is closely connected to the minimum rank of \(G\). 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)\leqslant c_2 (G)\leqslant \operatorname{mr}(G,\mathbb{F}_2)+1\). Furthermore, we show that the following are equivalent for any graph \(G\) with at least one edge: i) \(c_2(G)=\operatorname{mr}(G,\mathbb{F}_2)+1\); ii) the adjacency matrix of \(G\) is the unique matrix of rank \(\operatorname{mr}(G,\mathbb{F}_2)\) which fits \(G\) over \(\mathbb{F}_2\); iii) there is a minimum collection \(\mathscr{C}\) as described in which every vertex appears an even number of times; and iv) for every component \(G^\prime\) of \(G, c_2(G^\prime) = \operatorname{mr}(G^\prime,\mathbb{F}_2) + 1\). We also show that, for these graphs, \(\operatorname{mr}(G,\mathbb{F}_2)\) is twice the minimum number of tricliques whose symmetric difference of edge sets is \(E\). Additionally, we provide a set of upper bounds on \(c_2(G)\) in terms of the order, size, and vertex cover number of \(G\). Finally, we show that the class of graphs with \(c_2(G)\leqslant k\) is hereditary and finitely defined. For odd \(k\), the sets of minimal forbidden induced subgraphs are the same as those for the property \(\operatorname{mr}(G,\mathbb{F}_2)\leq k\), and we exhibit this set for \(c_2(G) \leqslant 2\).