11
$\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
  • 2
    $\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$ Dec 31, 2018 at 17:05

2 Answers 2

4
$\begingroup$

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

$\endgroup$
5
$\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$
0

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.