Consider asymmetric unlabelled digraphs $G$ (asymmetric means |Aut($G$)| = 1).

Trivially, (i) each node $v$ can be uniquely labelled (with the pointed graph $G_v$, i.e. $G$ with distinguished node $v$), and (ii) whether there's an edge between $v$ and $w$ can be read off their labels $G_v$ and $G_w$.

Things get interesting when in the case of an (countably) infinite graph $G$ a finite induced subgraph of $G_v$ for all $v$ does suffice for (i) and (ii). Let's call such a graph and its nodes finitely discriminable.

There are two obvious examples of infinite finitely discriminable graphs:

  • the natural number graph with edges from $n$ to $n+1$ in which each node $v$ can be labelled by the induced subgraph consisting of $v$ and its predecessors

  • the graph of hereditarily finite sets with edges from $x$ to $y$ iff $x \in y$ in which each node $v$ can be labelled by its transitive closure graph TC({v})

What these two graphs do share are the Mostowski collapse conditions, i.e. their relation is set-like, well-founded and extensional.


  • Are the Mostowski conditions necessary and/or sufficient for an infinite graph to be finitely discriminable?

  • If they are not necessary: what is an example of an infinite finitely discriminable graph for which one of them does not hold? Is the rest of them necessary, then?

  • Especially: Are there undirected (i.e. not well-founded) finitely discriminable graphs?

  • If the Mostowski conditions are not sufficient: can they be augmented to become sufficient, or is there another completely different set of sufficient conditions?

  • $\begingroup$ I haven't understood the definition of "finitely discriminable" yet, can you help? By "natural number graph" do I assume you mean the graph whose vertices are natural numbers, with edges between $n$ and $n\pm 1$? If so, then, unless I'm very much mistaken, it's finitely discriminable but not for the reasons you state. After all, the label you've associated to 100 (consisting of $1,2,\ldots,100$) could very well be attached to 1 instead (just the wrong way around, with downwards being sent to upwards). Shouldn't you instead associate something like the interval $[1,2n-1]$ to the vertex $n$? $\endgroup$ – James Cranch May 18 '11 at 12:07
  • $\begingroup$ @James: I tried to make things clearer. Especially, I mean the directed natural number graph with edges from n to n+1 only. $\endgroup$ – Hans-Peter Stricker May 18 '11 at 12:31
  • $\begingroup$ It's possible I'm being really stupid. But I'd like a bit more clarification. Firstly, you really ought to say from the beginning that you're interested in directed graphs (to me a graph is undirected). $\endgroup$ – James Cranch May 18 '11 at 12:44
  • $\begingroup$ Secondly, why isn't the graph I described (vertices $\mathbb{N}$, edges from $n$ to $n\pm 1$) a counterexample? $\endgroup$ – James Cranch May 18 '11 at 12:46
  • $\begingroup$ @James: Sorry for that (for me a graph is directed, but I should have been aware that this is not common!) An undirected graph is then just a special kind of (symmetric) digraph. $\endgroup$ – Hans-Peter Stricker May 18 '11 at 13:12

(Please se the edit history for my previous answer.)

I believe the interesting question here is whether we can assign to each node in a countable directed graph $G$ a finite induced pointed subgraph (up to isomorphism), such that we can reconstruct $G$ knowing only those labels. Indeed, a stronger version of this would require that we can reconstruct $G$ in a local, continuous and computable manner, meaning that the question of whether two nodes are connected depends only on the (isomorphism classes of the) labels on those nodes, and not on any other information, including $G$, and that this is computable from those labels. (In particular, for this strong version of the question, it doesn't make sense to consider a separate algorithm for each $G$, since the reconstruction procedure should be the same for every $G$.) The idea is that we build a copy of the original graph from these pieces by fitting them together like a puzzle.

Theorem. Every countable graph is finitely discriminable, in the sense that it has such a labeling with finite induced subgraphs, for which there is a uniform computable procedure to reconstruct an isomorphic copy of the graph in a local, continuous computable manner.

Proof. Suppose $G$ is any countably infinite directed graph. Let $\Gamma$ be a fixed computable directed graph that is universal for all countable directed graphs. (Thus, $\Gamma$ is something like a directed version of the random graph.) Thus, there is an embedding $\pi:G\to\Gamma$ to an induced subgraph of the countable random graph $\Gamma$. Fix a computable copy of $\Gamma$, using positive elements of $\mathbb{N}$ as vertices, and fix $\pi$. Thus, each vertex $v$ in $G$ is mapped to a natural number $\pi(v)$, such that $\pi[G]$ is an isomorphic copy of $G$ inside $\Gamma$.

Let me now describe my finite neighborhood labels. Assign to each vertex $v$ in $G$ any finite induced subgraph of $G$ having size $\pi(v)$. (Note, $\pi(v)$ is a positive natural number, so this is possible.)

The point now is that if I know the labels assigned to two nodes, then in particular, I know the sizes of those labels, and so I know which nodes inside $\Gamma$ they are meant to correspond to, and so I know whether or not my nodes should have an edge or not. Thus, from the labels I can reconstruct the copy of $G$ inside $\Gamma$. QED

I anticipate that perhaps you will not like this proof, because the reconstruction procedure I have given does not using any of the edge information from the finite induced subgraphs, but only the size of that subgraph, and perhaps this seems like cheating. In this case, I think the question would need to become more precise about what exactly it is that is desired.

  • $\begingroup$ In answer to your second paragraph, this is the way I understand it: we label each vertex $v$ with a graph with a distinguished vertex. This must arise as an induced subgraph of a set of vertices which contains $v$, and the distinguished vertex is $v$. But the labelling doesn't include the name of the vertex you started with. In slogan form, "when can you reconstruct a graph given neighbourhoods of every point?" $\endgroup$ – James Cranch May 18 '11 at 13:33
  • $\begingroup$ Yes, I agree that that is the interesting question here (and it seems to have little to do with the Mostowski conditions). $\endgroup$ – Joel David Hamkins May 18 '11 at 13:39
  • $\begingroup$ Actually, I think it's not easy to think of asymmetric digraphs which aren't finitely discriminable... $\endgroup$ – James Cranch May 18 '11 at 14:15
  • $\begingroup$ I asked this question some year ago: mathoverflow.net/questions/25215/… $\endgroup$ – Hans-Peter Stricker May 18 '11 at 14:15
  • $\begingroup$ @James: interesting enough! $\endgroup$ – Hans-Peter Stricker May 18 '11 at 14:16

To clarify some questions (as I understand them) by an extended example: Let $G_{a,b}$ be the directed graph with $a+b+1$ vertices $-a,-a+1,-a+2,\cdots,-1,0,1,\cdots,b-1,b$ and edges directed away from $0$ (the root) and let $g_{a,b}$ be the corresponding unlabeled directed graph. Imagine that all the vertices are black. Then I can specify the root by showing you $g_{a,b}$ with the root colored red. If $a \ne b$ then I can specify any vertex of $G_{a,b}$ in this manner, otherwise not. If the values of $a$ and $b$ are known to us then I can specify the root by showing you $g_{1,1}$ with a red root. If $a \lt b$ then I can specify vertex $-j$ by merely showing you $g_{j,a+1}$ with a red point in the right place and vertex $j$ by something similar with $g_{a,c}$ where $c=\min(j,a+1)$. All this is true for $G_{a,\infty}$ with $a$ finite.

For the undirected graph with paths of lengths $a+1,b+1,c+1$ sharing a common endpoint similar things are true when $a \ne b \ne c \ne a$. Would that be an undirected example of the desired type if $c=\infty?$


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.