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

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

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

(If there were none, this would imply that $S_< = R_<$, which I would find a surprising result at first sight – or is it by any means obvious?)

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

[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 that the vertices of each directed cycle must form a complete subgraph, which is something like well-foundedness.)

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

(If there were none, this would imply that $S_< = R_<$, which I would find a surprising result at first sight – or is it by any means obvious?)

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

(If there were none, this would imply that $S_< = R_<$, which I would find a surprising result at first sight – or is it by any means obvious?)