8
$\begingroup$

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$: Claw as sum of K_4 and K_3 (mod 2) (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.

$\endgroup$
  • 1
    $\begingroup$ 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/… $\endgroup$ – Christopher Purcell Dec 31 '18 at 17:05
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.