Infinite graphs with finitely discriminable vertices

Question

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.

Questions:

• 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?

Answer 1

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

Answer 2

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?$