# Self-containing graphs

[Second try, after this question failed.]

Let me sketch a notion of self-containing structures by a simple example. Consider the class $\Gamma$ of finite or countable digraphs ("graphs" for short) with the relation $<$ on it, $G< H$ meaning that $G$ is isomorphic to an induced proper subgraph of $H$.

Consider the class of graphs $G$ that may arise (up to isomorphism) as $<$-graphs of a subset $V$ of $\Gamma$, i.e. for which there is a set of graphs $V \subset \Gamma$ such that $\langle V,< \rangle \cong G$. Call such a graph $<$-representable:

$$R_< := \lbrace G \in \Gamma\ |\ (\exists V \subset \Gamma)\ \langle V,< \rangle \cong G \rbrace$$

Question 1: How can $R_<$ be characterized? (One necessary condition is of course, that the graph is transitive.)

Call a set of graphs $V \subset \Gamma$ self-containing (with respect to $<$), when there is a graph $G \in V$ (sic!) that is isomorphic to $\langle V,< \rangle$ (which implies that $V$ is finite or countable and $<$-representable). Consider the class of all sets of self-containing graphs

$$S^*_< := \lbrace V \subset \Gamma |\ (\exists G \in V)\ \langle V,< \rangle \cong G \rbrace$$

(Note the formal "duality" of the definitions of $R_<$ and $S^*_<$, but also the "little" asymmetry between $G\in V$ and $G \in \Gamma$.)

Call a graph $G \in \Gamma$ self-containingly $<$-representable, when there is a self-containing set of graphs $V$ such that $\langle V,< \rangle \cong G$:

$$S_< := \lbrace G \in \Gamma\ |\ (\exists V \in S^*_<)\ \langle V,< \rangle \cong G \rbrace$$

(Note this time the "little" asymmetry in the definitions of $R_<$ and $S_<$ between $V \subset \Gamma$ and $V \in S^*_<$.)

Question 2: How can $S_<$ be characterized? (At least some necessary or sufficient conditions are welcome.)

Question 3: Are there $<$-representable graphs that are not self-containingly $<$-representable? (Examples are welcome.)

-
For question 3, take a graph consisting of a unique vertex with a loop. This is representable by an infinite graph, but not by a finite one, in particular it is not self-containingly representable. –  Pierre Simon Sep 12 '13 at 18:41

Let's rephrase the problem: $(Γ,≤)$ (with $G ≤ H$ iff $G=H$ or $G < H$) is a preordered set (transitive and reflexive). $<$ is not necessarily symmetric, $≤$ is not necesserily an equivalence relation. Then $R_<$ is the set of suborders that are Elements of $Γ$. For order relations the set of the principal ideals or the set principal filters form such constructions. If I'm not mistaken in a preorder the set the principal ideals ordered by set inclusion is isomorphic to the order relation that arises if you factor out the equivalence classes.

An important fact is that the induced subgraph of a preorder relation is still a preorder relation. So if $G$ is an ordered set then it is $<$ representable in the ordered set of its primary ideals. For preorders we can represent an element $x$ by a set $I(x,G)$ that contains $x∈G$ and all elements $y∈G$ that are strictly below $x$ (those $y$ such that $x≥y$ and $x\not≤y$ hold). So

• Question 1 $(R_≤,≤)$ is the class of finite or countable preordered sets.
• Question 2 $(S^*_≤,≤)$ contains all systems that are generated by a preordered Set $G$ and the system $I(x)$ ordered by set inclusion, as set inclusion induces an order embedding of the induced order of < in $I(x)$. Furthermore it contains all such structures that can be generated out of them.
• Question 3 $(R_≤,≤) = S_≤,≤)$

This is still not the system you are talking about, as you forbid non-proper subsets and loops must be considered separately. But this may be a starting point.

If you are interested in more insights you could investigate the problem with tools similar to formal concept analysis. You can consider $(2^Γ,Γ,J)$ where $⟨V,≤⟩\mathrel J G :⇔ G\cong ⟨V,≤⟩$ as some kind of formal context. As far as I know Sebastian Kerkhoff recently developed a categorical generalisation of that framework.

BTW.: You are talking about a category. Thus, maybe category theory has additional results.

Edit:

And that it doesn't get lost: The problem of loops is not touched by the question whether it is a strict or reflexive preorder. As the category of graphs with a loop on each node is equivalent to the category of graphs with no loop on any node (removing all nodes is a functor and adding a loop to each node is its inverse, their combination is the identity functor). Using a reflexive order considered as small catgeory each loop can be represented as non-identity loop, which turns the induced subcategory of this node into a non-trivial semigroup. So we can see: Two equivalent Graphs are either isomorphic or have injective endomporphsms. The latter means the corresponding nodes have a loop.

-
Thanks! Why is $\leq$ not an equivalence relation? –  Hans Stricker Sep 13 '13 at 7:11
If $H$ is a proper subgraph of some finite graph $G$ then $G$ there is no injective mapping from the set of nodes of $G$ into the set of nodes of $H$. –  Tobias Schlemmer Sep 13 '13 at 7:37
I was stupid: of course it is not. (I was misled because you wrote "is not necessarily an equivalence relation" - of course not.) –  Hans Stricker Sep 13 '13 at 9:49