Self-containing graphs

Question

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

Answer 1

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.