Let $W_0$ be some fixed, finite set of "atomic vertices". Noting $2^X$ the power set of some set $X$, we consider $\bigl\{ (V, E) \bigm| V \in 2^{W_0}, E \in 2^{\{ (s, t) | s, t \in V \}} \bigr\}$, the set of all graphs whose vertices come from $W_0$. We are interested in the case where such graphs could appear as vertices in a graph (together with "atomic vertices" from $W_0$), and recursively consider such graphs-of-graphs as vertices in "higher-order" graphs

$$\forall n \in \mathbb{N}, \quad W_{n+1} = W_n \cup \bigl\{ (V, E) \bigm| V \in 2^{W_n}, E \in 2^{\{ (s, t) | s, t ∈ V \}} \bigr\}\quad .$$

I'm considering a Computer Science and/or Knowledge Graph and/or Philosophy application involving such "graphs-of-graphs". Before reinventing the wheel, I would like to know what the literature has to say about this, but I don't know where to start looking.

Are you aware of any terminology/conventions/notations for such "graphs"? Are there issues/paradoxes that I should be aware of in the limit $n \to \infty$? Are there works, especially accessible ones, that you would recommend on the topic? Thanks!

Following Mike's Comment/Answer, I decided to add a few explicit examples.

First suppose that $W_0 = \emptyset$, in which case $W_1 = \bigl\{\bigr (\emptyset, \emptyset) \}$ because the only graph you can build with no vertices is the empty graph (with no vertices nor edges). But for $W_2$, we may treat the graph $(\emptyset, \emptyset)$ as a vertex, giving

\begin{align} W_2 = \Bigl\{ & (\emptyset, \emptyset),\\ & \bigl(\{(\emptyset, \emptyset)\}, \emptyset\bigr),\\ & \bigl(\{(\emptyset, \emptyset)\}, ((\emptyset, \emptyset), (\emptyset, \emptyset))\bigr) \Bigr\} \quad , \end{align}

i.e., the set comprised of 1. the empty graph, 2. a graph with no edge and the empty graph as a vertex, and 3. a graph with a single edge joining the empty graph to itself (self-loop). We could then continue with $W_3$, this time with 3 vertices available as building blocks.

In the limit $n \to \infty$, I believe that recursive definitions like the following would be valid

$$g = \Bigl( \bigl\{(\emptyset, \emptyset), g\bigr\}, \bigl\{ \bigl((\emptyset, \emptyset), g\bigr) \bigr\} \Bigr) \quad ,$$

i.e., the graph $g$ has the empty graph and itself as vertices, with a single edge oriented from the empty graph to the graph $g$. But this is the kind of "hand waving" that could eventually lead to issues/paradoxes...

Up to this point, I considered $W_0 = \emptyset$, but what if we allow for some "atomic vertices"? My understanding is that if $W_0$ only contains graphs that would have been valid in the above (e.g., $W_0 = \{(\emptyset, \emptyset)\}$), this will affect "shallow" layers but leave the limit $n \to \infty$ unaltered. However, if we instead add something new (and perhaps not even a graph, say $W_0 = \{42\}$), then this would increase the expressiveness of limit $n \to \infty$.

Please note that I have a very "applied" perspective here: I'm thinking of such graphs as a candidate tool to represent concepts. As an example of where I'm coming from, please consider Figure 19(c) from https://arxiv.org/abs/2003.02320 . Ignoring the edge labels "flight" and "valid from", this knowledge graph could be represented as

\begin{align} \Bigl(\Bigl\{ & \bigl( \bigl(\{\text{Santiago}, \text{Arica}\},\{\bigl(\text{Santiago}, \text{Arica}\bigr)\}\bigr), 1956 \Bigr\},\\ \Bigl\{& \bigl( \bigl(\{\text{Santiago}, \text{Arica}\},\{\bigl(\text{Santiago}, \text{Arica}\bigr)\}\bigr) , 1956\bigr)\Bigr\}\Bigr) \quad . \end{align}

This kind of representation is already quite powerful, and I'm wondering how far we can push it.


1 Answer 1


For whatever reason, my internet browser won't let me get into writing a comment, which is what this is.

As far as this specific example, I am not sure. But, for comprehension, better to both write in in concise formal mathematical language, and then explain a bit less formally with words. Meanwhile, is the graph you wrote out even well-defined? So $S,T \in \cal{P}(S_{n-1})$ are adjacent in $G_n$ iff $|S|=|T|$ and $s_it_i \in E(G_{n-1})$ for each $i=1,2,\ldots, |S|$ and some ordering of $S$ and $T$?

IN GENERAL:Your best bet is to just say explicitly what you mean. Say "Let $G$ be a graph. And then in turn, we replace each vertex $v \in V(G)$ with a graph $H_v$ of the following structure, and then we put an edge between a vertex $u_v \in H_v$ and $u_w \in H_w$ iff $vw$ is an edge in $G$, and ...."

The term commonly used for what you are describing is "graph product", but there are many flavors of such graph products i.e., do you replace each edge $vw$ in $G$ with a complete bipartite graph between $V(H_v)$ and $V(H_w)$ or just a matching between $V(H_v)$ and $V(H_w)$, or even just one edge; are the $H_v$s; $v \in V(G)$ all the same graph, and even, are the $H_v$s vertex-disjoint.

  • $\begingroup$ I'm not sure I understand what you mean, but what is clear is that my question sorely lacked explicit examples: I added some. Concerning "graph product": unless I'm missing some very deep insight/correspondences, then I don't think this is relevant. $\endgroup$ Feb 12, 2021 at 12:50

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.