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

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.

• I'm not sure if this is worthy of a full answer, but there is a similar question about expressing a graph in terms of the symmetric difference of complete bipartite graphs here: mathoverflow.net/questions/76043/… Dec 31, 2018 at 17:05

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).

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.