*[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**:

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

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

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

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$)**

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

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

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

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

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

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

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

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

**???**$ \Leftrightarrow n < \nu$ is odd # CoP**???**$ \Leftrightarrow n < \nu$ # CoP**???**$ \Leftrightarrow \nu_0 \leq n < \nu_1$ # CoP**???**$ \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^{1}, 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.

^{1} 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)\rbrace$ have a high level in the arithmetical hierarchy.

Questions:

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?

Does anyone have an idea how the graphs in the

???examples might be characterized in the language of graph theory?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)

allgraphs?