2 deleted 4 characters in body

[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. coprimeness1, 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