1
$\begingroup$

I asked this question one week ago on MSE and has received no answer.

Infinite directed graphs (graphs with countably many nodes and edges) have a number of different applications. They can be identified with binary relations, in other words as elements of the power set of $\mathbb{N} \times \mathbb{N}$, although the correspondence is not one-to-one because each infinite graphs correspond to infinite many binary relations, one for each labeling of nodes with natural numbers.

A recursive infinite directed graphs is a graph that can be built by some algorithm. I see three possible ways to recursively build this kind of graphs:

  1. algorithms that build the graphs node by node, edge by edge with a list of instructions. This list of instructions is finite, but it contains a loop that runs for ever. For instance an infinite tree where every node has n-children can be built starting with a root, adding n nodes to the root, and then again adding n children to each of leafs, and so on. An infinite star is built by keeping adding edges between the root and all the other nodes. Those two examples are very simple. What would be an effective set of instructions (a programming language) to build any possible recursive infinite directed graph?

  2. starting with some basic infinite graphs and defining a finite set of transformations that combined can produce any recursive infinite graph. This sounds similar to the definition of recursive function (where the basic functions are successor function, constant function, identity function and the transformations are composition, primitive recursion and $\mu$-recursion). If you restrict this very same definition to functions with one variable $f: \mathbb{N} \longrightarrow \mathbb{N} $ you have a the subset of these graphs corresponding to functions, so graphs with at most one outer edge for each node. Is there a way to expand this definition to encompass all recursive relations?

  3. another way is with the characteristic function of a relation, in this case for a binary relations it would be $f: \mathbb{N} \times \mathbb{N} \longrightarrow \{0,1\}$. How can we define the recursive functions of this type in terms of basic functions and operators similarly to the general definition of recursive functions?

Are there other possible approaches (for instance what about working with the infinite adjacency matrices of the graphs)? Finally what are the connections between the different approaches?

I assume there must be a way to assign numbers to nodes of a recursive graph which make the corresponding binary relation non recursive, but then I guess that this labeling function is not recursive as well. If an algorithm that build a graph assigns a natural number to a node incrementally when it adds this node to the graph then the the corresponding binary relation should be recursive as well, is this correct or am I missing something? Is there something more that should be said about assigning numbers to nodes?

I could not a find any text book on infinite graphs and for some reasons recursion/computability theory focuses on functions and relations are considered just a byproduct.

Improve this question
$\endgroup$
3
  • $\begingroup$ One ordinary thing to say is that a recursive function on $\mathbb{N}\times\mathbb{N}$ defines a recursive graph presentation, and that some of these presentations have recursive (or non-recursive) isomorphisms between them. For what applications would you need or want a more elaborate definition? $\endgroup$
    – user44143
    Commented Oct 10, 2020 at 20:29
  • $\begingroup$ @MattF. are you talking about functions $f: \mathbb{N} \times \mathbb{N} \longrightarrow \{0,1\}$ or more generally functions $f: \mathbb{N} \times \mathbb{N} \longrightarrow \mathbb{N} $? $\endgroup$
    – user115415
    Commented Oct 11, 2020 at 12:24
  • $\begingroup$ Functions to {0,1} $\endgroup$
    – user44143
    Commented Oct 11, 2020 at 13:39

0

Reset to default

You must log in to answer this question.