MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider - for the sake of simplicity - only graphs as structures.

For undirected graphs $(V, E\subseteq \binom{V}{2})$ let

  • $E(v)$ be the set of edges $e\in E$ incident with $v$, i.e. $\lbrace e \ |\ v \in e\rbrace$

  • $N(v)$ be the set of vertices $w\in V$ connected with $v$, i.e. $\lbrace w \ |\ v - w\rbrace$

where $v - w$ denotes $\exists\ e = \lbrace v,w\rbrace$.

Let for arbitrary sets $X$, $Y$ denote $X\ \text{o}\mkern-5mu\text{o}\ Y$ the fact that $X \cap Y \neq \emptyset$.

It's a trivial matter of fact that in every undirected graph

$$v - w\quad \text{iff}\quad E(v)\ \text{o}\mkern-5mu\text{o}\ E(w)\quad\quad(\ast) $$

In this respect every undirected graph is supposed to be a self-modelling structure, because it provides a model of itself by a set construction over its vertices.

For directed graphs $(V, E\subseteq V^2)$ things are not so simple. Let

  • $E_{in}(v)$ be the set of in-arrows $e\in E$ of $v$, i.e. $\lbrace e \ |\ \exists w\ e = (w,v)\rbrace$

  • $E_{out}(v)$ be the set of out-arrows of $v$, i.e. $\lbrace e \ |\ \exists w\ e = (v,w)\rbrace$

  • $N_{in}(v)$ be the set $\lbrace w \ |\ w \rightarrow v\rbrace$

  • $N_{out}(v)$ be the set $\lbrace w \ |\ v \rightarrow w\rbrace$

where $v \rightarrow w$ denotes $\exists\ e = (v,w)$.

The first sensible "proposition" half-way similar to $(\ast)$ seems to be

$$v \rightarrow w\quad \text{iff}\quad N_{in}(v)\ \subseteq\ N_{in}(w)\quad\quad(\ast\ast) $$

but this holds only for a resctricted family of digraphs: the transitive digraphs. Interesting enough.

I wonder whether there are other set constructions $F$ over the vertices of a (di)graph and other (un)directed relations $\approx$/$\Rightarrow$ between sets such that

$$v - w\quad \text{iff}\quad F(v)\ \approx \ F(w) $$


$$v \rightarrow w\quad \text{iff}\quad F(v)\ \Rightarrow\ F(w) $$

for other interesting families of (di)graphs.

share|cite|improve this question
For $(\ast)$, you seem to need $v\neq w$. – Joel David Hamkins Jun 20 '13 at 0:18
Wouldn't the directed analogue of $(\ast)$ be the fact that $v\to w$ iff $E_{out}(v)\cap E_{in}(w)\neq\emptyset$ in any directed graph? – Joel David Hamkins Jun 20 '13 at 0:23
Maybe, but two set constructions would be involved: $E_{in}$ and $E_{out}$. On the other side: why not? – Hans Stricker Jun 20 '13 at 0:26
I'm confused: what, exactly, does it mean for a structure to be "self-modelling?" For that matter, what is a "set construction?" – Noah Schweber Jun 20 '13 at 4:59
I think I´m as confused as Noah. Can´t you just glue $E_{out}$ and $E_{in}$ into a single set construction (with some labeling to distinguish which is which)? Then follow Joel´s comment. Maybe you could explain a bit what the point of being "self-modelling" is. – Ramiro de la Vega Jun 20 '13 at 11:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.