Uniformly computable classes of graphs

[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

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:

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?

-

This question sounds more like a research project than a definite problem. Part of the reason for me to say this is because this question is only interesting if you impose some (ill-defined) qualifications on what an interesting answer can be; and even then, it is not clear how one can answer the question without having the insights into the structure of the integers which you are hoping to find. Having said that, I'll hazard some elementary observations.

Throughout the following, I will refer to the integer which corresponds to a vertex in a graph as its index.

The problem of Gödel numbering

Your question is still about computable predicates. As long as you do so, without imposing further restrictions, there will still be too much room open for Gödel numbering to give solutions to sub-problems.

The predicate V0 that I described before, while 'elaborate' (in that it would not be so simple in closed form), relied quite heavily on using prime factorization as a means of describing compound data structures --- specifically, in order to construct the indices of vertices to represent a sort of label for the vertex, its adjacency relations to other vertices, and even complete information about the entire graph.

In order to obtain "interesting" representations of graphs just by families of indices and relations on them, we obviously want to reduce reliance on Gödel numbering. We can do this by disallowing Gödel numbering in the indices,* i.e. in the first argument n to the predicate V and the first two arguments to the predicate E. But even if we do this, a very modest amount of Gödel numbering in the third argument μ to E gives away the whole game, as I show below.

* Of course, this pre-supposes that determining what constitutes Gödel numbering is a computable problem; I would argue that it isn't even well-defined. We can concievably describe a restriction to how much one can exploit the prime factorization of indices, but this would not address information being carried by the integer in e.g. representation of the index in base 1000, or any arbitrarily esoteric-but-computable representation of the index. Furthermore, even while prohibiting Gödel numbering, we still presumably want/need the index to bear some information; just not potentially arbitrarily complex information. But let's ignore that technical problem and suppose it can be done for the sake of argument.

A "significantly less complex" universal set of predicates

It suffices to do the following:

• Set $\nu$ to be a multiple of the first n primes, for a graph on n vertices.
• Set $V(n,\nu) \equiv \big( \nu \in n \mathbb N \;\;\&\;\; n ~\text{prime}\big)$.
• Set $\mu = 2^{e_1} 3^{e_2} \cdots p_m^{e_m}$, for a graph on m edges, where each integer ej is a product of two primes which are the indices of adjacent vertices.
• Set $E(n,m,\mu) \equiv (\exists p~\text{prime}):\big(\mu \in p^{nm}\mathbb N \;\;\&\;\; \mu \notin p^{nm + 1} \mathbb N\big)$.

The sole explicit instance of "Gödel numbering" in this scheme is in the construction of μ. However, it suffices to admit very simple choices of V and E to represent an arbitrary graph. The number μ isn't even terribly esoteric: the only retriction on μ is that the exponents of its prime factorization are always square-free, and have exactly two prime factors when they are non-zero. This construction generalizes to hypergraphs and graphs with loops trivially.

The key to this construction, of course, is that the prime numbers serve as "easily distinguishable" indices for the vertices, to the extent that any number which is a multiple of two or more primes may be easily interpreted as a set; and then we store multiple sets by storing them in the exponents of a prime factorization of some integer.

I may have fallen afoul of some restriction you have in mind; for instance, it is likely that the set of μ of the form above (either in the explicit construction or the generalization for prime power indices) have small "measure", for many reasonable definitions of measures. From you examples e.g. of cycle graphs, however, I assume the fact that not all μ fall under this construction is not a problem.

Approaches to trees which avoid Gödel numbering

'Universal' predicates which rely on Gödel numbering are obviously boring, in that they indicate only what is possible. After one understands Gödel numbering as a means of representing data structures, they are not in themselves interesting. The challenge is then to see what one can do without using Gödel numbering (which I take in a practical sense to refer to using integers only to denote sequences or collections of other integers).

This is tricky for a graph class such as "arbitrary trees" (or even "arbitrary binary trees"), because there is little structure to deal with; it seems to me that natural representations of them will amount to something like lattices of subsets with added restrictions.

The trick is that for each index, you would like to identify a unique vertex (depending possibly on μ) which can be its "parent" (in the picture of rooted trees); or more generally, however one defines the set of allowed indices, at most one element of the set can be its parent, with exactly one vertex failing to have a parent.

This is where your question becomes ill-defined. Your motivation seems to be to somehow plumb the structure of the integers using graphs; but to do this, we must somehow already have a structure to hand to represent trees. This is not a research problem, so much as it is a very open-ended research programme.

Two potential approaches --- simple ones, and so likely not to be realizable --- occur to me.

1. Once more, we can consider prime factorizations. To avoid the temptation of Gödel numbering, we should not be too picky with the indices; the index-set should admit integers with non-trivial common divisors. A natural choice of edge-predicate is then $$E(n,m,\mu) \equiv \big(\exists A,B\big):\Big(\{A,B\} = \{n,m\} \;\;\&\;\; A/B ~\text{is the largest prime factor of A}\Big) ,$$ that is, where transition from each vertex v to its parent corresponds to division by the largest prime factor of the index of v. A natural choice of predicate V is then to choose indices which are factors of some particular integer.

It is not clear to me how general a class of trees we can get from this; we can easily obtain paths and stars, and some variety of other trees. It is also not clear to me how to get a reasonably varied class of binary trees.

2. We can consider ways of partitioning integers into a sum of smaller integers. Because addition in itself has so "little" structure, any structure would have to come from the allowed set of summands, which has to be given by the integer μ; this comes dangerously close to Gödel numbering. A simple solution is to use this integer to parameterize a family of summands, e.g. powers of μ. This too can lead to Gödel numbering of a different sort; a possible approach is to use ternary expansions of integers to represent the location of a node in a tree by left-right branching from the root, with log3(n) representing the distance from the root, and the jth digit representing whether one takes the left or right branch at the jth level to reach the vertex in question. So there is a real question of what there is that one can do, under the constraint of doing something interesting.

A compromise is to succumb to prime factorization, but to more or less ignore the exponents to avoid the temptation to do Gödel numbering. So, the possible transitions may be taken to be the (maximal) prime-power factors of μ. This still uses μ to denote a set of integers, but not a set with arbitrary elements. To identify a parent of an index, one may take the number which may be reached by subtracting the largest allowable transition. One may easily obtain paths (e.g. restrict to odd indices and take μ = 2) and arbitrary star graphs (e.g. restrict indices to 1 and p+1 for p prime, and take μ to be a suitable square-free integer). It's not obvious how to get arbitrary trees.

One can think of generalizing this to allow transitions which are e.g. arbitrary prime-power factors, not just maximal prime-power factors. This can be used to get a wide variety of trees. For instance, we may consider restricting the indices to integers n which are a sum of at most k powers of two, and let the parent of each index be the one which is obtained by subtracting the largest power 2r < n. This is pretty simple; but also dangerously close to the ternary scheme described above. It is not clear exactly how to delineate the boundary between 'interesting' and 'using Gödel numbering'. (Then again, perhaps this last decomposition isn't interesting anyway --- or perhaps it is merely the concept of 'the structure of an arbitrary tree' which is not especially interesting.)

In closing

Unless your objective is actually to embark on an open-ended research project, you might want to restrict your question a bit more. In particular, you should give some thought to imposing conditions which would prevent "trivial" solutions, especially using numerical tricks to embed the structures you are interested in into the indices and/or parameters.

Unless you somehow refine your question, it is just extremely open-ended. Not to say that it isn't a nice sort of project.

-
Wow! Have to go through this with a little more of time. Will comment on this later. –  Hans Stricker Mar 24 '10 at 14:39
In the meanwhile you might want to have a look at this question (and its great answer): mathoverflow.net/questions/19076/… –  Hans Stricker Mar 24 '10 at 14:42
Interesting to see that the approach using demi-primes in a diverging interval of integers reduces the problem to a popular number-theoretical conjecture. I am not a number theorist, per se, but it seems an unobvious reduction. I will have to give that answer (and why you might have chosen that formulation --- is there any particular reason?) some more thought later. –  Niel de Beaudrap Mar 24 '10 at 15:39
Which formulation do you mean? And what do you mean by "diverging interval"? –  Hans Stricker Mar 24 '10 at 15:59
"Diverging interval" was my attempt to succinctly convey what you wrote, i.e. a sequence of intervals which goes off to infinity, in the same way one may speak of "an integer quantity" (really, a sequence of integers) diverging. –  Niel de Beaudrap Mar 24 '10 at 17:19