Question

[Follow-up to Can every finite graph be represented by one prescribed sequence of natural numbers?, reformulated thanks to a hint from Jacques Carette]

Let $V(n,\nu)$ and $E(n,m,\mu)$ be computable predicates with parameters $\nu, \mu$.

Consider the class $\Gamma(V,E)$ of finite graphs $G$ for which there are parameters $\nu, \mu$ such that

• the vertex set of $G$ is in bijection with $\lbrace n \ |\ V(n,\nu)\rbrace$ and

• $x_i$ and $x_j$ are adjacent iff $E(n_i,n_j,\mu)$.

Motivation

The existence or non-existence of computable predicates $V, E$ such that $\Gamma(V,E)$ coincides with a class $\Gamma$ of graphs characterized in the language of graph theory might reveal a "hidden" structure of the natural numbers, but to be honest, balanced strictly $k$-ary trees and hypercubes are the most interesting structures I did "discover" so far.

Problems:

1. Given a pair of predicates $V,E$ as above $\Rightarrow$ characterize $\Gamma(V,E)$ in the language of graph theory.

2. Given a class $\Gamma$ of graphs characterized in the language of graph theory $\Rightarrow$ find $V,E$ with $\Gamma = \Gamma(V,E)$.

3. Given $\Gamma$ as above $\Rightarrow$ find $V,E$ with $\Gamma = \Gamma(V,E)$ and minimal complexity.

4. Given $\Gamma$ as above $\Rightarrow$ find $V,E$ such that $\Gamma(V,E)$ contains almost all graphs in $\Gamma$ and no or almost no others. ("Almost" in the sense of Erdos–Rényi.)

Examples ($\Gamma \Leftrightarrow V$ # $\ E$)

1. complete graphs $ \Leftrightarrow n < \nu$ # $0 = 0$

2. empty graphs $ \Leftrightarrow n < \nu$ # $0 = 1$

3. path graphs $ \Leftrightarrow n < \nu$ # $ n = m + 1$

4. cycle graphs $ \Leftrightarrow n < \nu$ # $ n = m + 1$ mod $\mu $

5. balanced strictly $\mu$-ary trees $ \Leftrightarrow 0 < n < \nu$ # $ 0 \leq n - \mu\cdot m \leq \mu-1 $

6. hypercube graphs $ \Leftrightarrow n < 2^\nu$ # $ (\exists k < \nu) | n-m | = 2^k $

7. empty graphs $ \Leftrightarrow n < \nu$ is even # $n$ and $m$ are coprime (CoP for short)

8. complete graphs $ \Leftrightarrow n < \nu$ is prime # CoP

9. ??? $ \Leftrightarrow n < \nu$ is odd # CoP

10. ??? $ \Leftrightarrow n < \nu$ # CoP

11. ??? $ \Leftrightarrow \nu_0 \leq n < \nu_1$ # CoP

12. ??? $ \Leftrightarrow (\exists k < \nu_2)\ n = \nu_0 + k\cdot \nu_1$ # CoP (see another question of mine)

Observation

The graphs in $\Gamma(V,E)$ are necessarily the more symmetric the more $V$ and $E$ are regular (in an admittedly vague sense). To get classes of more irregular graphs one needs at least one irregular predicate, e.g. coprimeness¹, even though this is not sufficient, see examples 7 and 8. In general, $\Gamma(V,$CoP$)$ seems hard to be characterized in graph theoretic terms, if at all.

¹ Note that every finite graph is isomorphic to an induced subgraph of the coprimeness graph.

One for all

Niel's elaborate construction yields a predicate $V_0(n,\nu)$ – with the parameter $\nu$ being interpreted as the Gödel number of a graph – such that $\Gamma(V_0,$CoP$)$ is the class of all finite graphs. This fact doesn't really reveal a "hidden" structure of the natural numbers. It just uses the fact that graphs are gödelizable and shows – as Niel points out – how we can do "packing and unpacking of data structures in the integers". This comes along with the fact, that the sets $\lbrace n \ |\ V_0(n,\nu) = 1\rbrace$ V_0(n,\nu)\rbrace$ have a high level in the arithmetical hierarchy.

Questions:

1. Can anyone imagine (or even give) really astonishing, non-trivial predicates $V,E$, yielding for example the class of all (unbalanced and/or not strictly $k$-ary) trees?

2. Does anyone have an idea how the graphs in the ??? examples might be characterized in the language of graph theory?

3. Can anyone imagine predicates $V$ significantly less complex than $V_0$ and predicates $E$ not significantly more complex than coprimeness such that $\Gamma(V,E)$ is the class of (almost) all graphs?