Terminology for expressing a graph as a sum of cliques (mod 2)

Question

I am interested in the problem of expressing the edges of a given (undirected, simple) graph as the sum of edge sets of cliques modulo $2$.

To be more concrete, given a graph $G=(V,E)$, I am seeking to find cliques $C_1=(V_1,E_1)$, $\dots$, $C_k=(V_1,E_k)$ so that $V_i\subseteq V$ for all $i$, each edge set $E_i$ consists of all edges between pairs of vertices of $V_i$, and (most importantly), every edge $e\in E$ lies in an odd number of $E_i$ and every non-edge $e\notin E$ lies in an even number of $E_i$.

For example, in this sense we can express the claw as the sum (modulo $2$) of $K_4$ and $K_3$: (And of course any graph $G=(V,E)$ is the sum of $|E|$ copies of $K_2$, but many graphs have less trivial expressions as sums.)

Have you seen this sort of question asked in the literature? I have not been able to find any terminology for this question, or any literature on it, so I would appreciate almost anything MathOverflow users could share with me about it.

Answer 1

The closest notion to this that I have found in the literature is that of subgraph complementation, introduced by Kamiński, Lozin, and Milanič, in which the edges of a given induced subgraph of a graph $G$ are complemented. Then we may phrase your problem as building $G$ by taking successive subgraph complements, starting with the empty graph on $V(G)$.

In fact, your question inspired a research project amongst myself and the two others who responded to this post, the product of which is available here: arXiv:2101.06180.

We provide upper bounds on the minimum number of cliques in an expression of $G$ as you describe in terms of the number of vertices, the number of edges, and the size of a minimum vertex cover. We relate this problem to the minimum rank problem over the field of order $2$, enabling us in some cases to find the minimum size of such an expression. We also show that, similar to the minimum rank problem over $\mathbb{F}_2$, the class of graphs which may be expressed as a sum of $k$ cliques is hereditary and finitely defined for any positive integer $k$.

By considering an incidence matrix corresponding to a collection of cliques in an expression, we see that your problem is equivalent to that of finding a faithful orthogonal representation of a graph over $\mathbb{F}_2$; that is, an assignment of vectors over $\mathbb{F}_2$ to the vertices of $G$ so that two vectors are orthogonal if and only if they represent non-adjacent vertices. In the study of minimizing the dimension of such a representation, Lozin and Alekseev use an early variant of the subgraph complement (see the proof of Theorem 3).

Answer 2

I have never come across anything like this in the literature, but it is a fun question. It is reminiscent of the Lights-Out puzzle on general graphs.

Here is a greedy approach that gives $\leq |V(G)|-1$ cliques. Suppose we have some graph $G$ that we want to express as a sum of cliques.

Start with an empty graph $H$ with $V(H)=V(G)$. While $H$ is not isomorphic to $G$, choose a vertex $v$ that has the highest number of "incorrect" (non-)edges, i.e. the highest number of other vertices $w$ such that $vw \in E(H)\triangle E(G)$ (symmetric difference). Add a clique on the set of vertices $\{v\} \cup \{ w |vw \in E(H)\triangle E(G)\}$. Now all of $v$'s edges are "correct", and $v$ will never be chosen again to appear in a clique.

Note that this is not always optimal if the goal is to express as a sum of as few cliques as possible. Take, for example, the bowtie graph (two triangles that share a vertex). The above greedy algorithm uses 3 cliques, when it is easy to see that this graph is expressible as a sum of 2 cliques.