# Define a homomorphism of a set of graphs to its power set

Let $$G$$ be a simple graph and $$S$$ be the set of all sub graphs of $$G$$. Define two operations on $$S$$ as: $$union$$ of two graphs $$G_1$$ and $$G_2$$ is, $$G_1\cup G_2$$

$$=\langle V(G_1)\cup V(G_2), (E(G_1)\cup E(G_2)\rangle$$

and the graphs $$intersection$$ is, $$G_1\cap G_2$$

$$=\langle V(G_1)\cap V(G_2), (E(G_1)\cap E(G_2)\rangle$$.

Let $$P(S)$$ be the power set of $$S$$ and for any two subsets of $$S$$ namely, $$A, B\in P(S)$$, define:

$$A\sqcup B=\lbrace G_i\cup G_j:~G_i\in A, G_j\in B\rbrace$$ and

$$A\sqcap B=\lbrace G_i\cap G_j:~G_i\in A, G_j\in B\rbrace$$. Also, consider a mapping

$$f: S\rightarrow P(S)$$ such that $$f(empty~ graph)= emptyset$$ and $$f( G)=S$$.

So, how should $$f$$ be defined so that it is a homomorphism keeping in mind that every element of $$S$$ is a graph while every element of $$P(S)$$ is a subset containing graphs?

• I hope it is not a stupid question. What do you consider a homomorphism in this case? Sep 19 '19 at 21:44
• @user2679290 Even breakthrough results were borned out of stupid questions only. So, please bear.
– gete
Sep 20 '19 at 1:27

A possible answer is the following, if you are willing to relax the definitions (in a very minor way) of union and intersection of two graphs.

For clarity, let me introduce an additional notation. For any subgraph $$H$$ of $$G$$, considered as a graph with vertex set $$V(G)$$ (this is trivially possible by adding those vertices of $$G$$ into $$H$$, which do not participate in the edge set of $$H$$), let $$Q_G(H)$$ be the set of all subgraphs of $$H$$, where again the vertex set of each graph in $$Q_G(H)$$ is $$V(G)$$ (hence the subscript $$G$$ in $$Q_G$$).

Define the union and intersection of two graphs in $$Q_G(G)$$ as you have defined for the edge set, but now over vertex set $$V(G)$$. Now the map $$f:Q_G(G)\to P(Q_G(G))$$ defined by $$f(H)=Q_G(H)$$ should give you the desired homomorphism.

• In that case $Q_G(G)\subseteq S$. Right?
– gete
Sep 20 '19 at 13:29
• They'll be essentially equal. Every graph H in S will be in Q_G(G), however,the vertex set of H will not be V(H) but instead V(G). Sep 20 '19 at 13:54
• Noted. Thanks...
– gete
Sep 20 '19 at 15:02