*(This is a follow-up to my previous question [Can every finite graph be represented by an arithmetic sequence of natural numbers?][1])*

Since it is obviously false that every finite graph can be represented by an *arithmetic* sequence (with an edge between two vertices/numbers $n_i, n_j$ iff GCD$(n_i, n_j)>1$) I'd like to reformulate my question:

Consider a family $F$ of parametrized computable functions $\lbrace f_{\alpha}:\mathbb{N}^k\mapsto\mathbb{N}\rbrace_{\alpha}$ with $\alpha \in \mathbb{N}^{n}$ for some $k,n \in \mathbb{N}$.

A sequence $(n_1,....,n_k,n_{k+1},...,n_{k+l})$ is an $F$-sequence if $n_{i+k} = f_\alpha(n_i,n_{i+1},...,n_{i+k-1})$ for some fixed $f_\alpha \in F$.

An arithmetic sequence is an $F$-sequence for $F = \lbrace f_\alpha(n) = n + \alpha\rbrace_{\alpha \in \mathbb{N}}$.

> **Question:** Is there a family $F$ of functions $f_{\alpha}:\mathbb{N}^k\mapsto\mathbb{N}$ (as above) such that every graph on $n > k$ nodes can be represented by an $F$-sequence
> such that  $n_i$ and $n_j$ are joined by an edge iff $n_i \neq n_j$ and GCD$(n_i, n_j) > 1$

My first question was genuinely "first-order" and admitted a straight-forward "first-order" answer (even though negative). *This* question is genuinely "second-order" and furthermore existential and probably doesn't admit a straight-forward definite answer. Sorry for that (and I tagged it as a "soft question"). But maybe someone can give a hint how to try to attack it?


  [1]: http://mathoverflow.net/questions/17875/can-every-finite-graph-be-represented-by-an-arithmetic-sequence-of-natural-number