Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

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?

share|improve this question
    
I dont understand your parameter $\alpha$. Do you mean that $\alpha \in \mathbb N$, giving an integer-parameterized family, ensuring that you have a family of functions $F$ which may increase in 'complexity'? –  Niel de Beaudrap Mar 13 '10 at 18:47
    
I mean a function $F: \mathbb{N}^{n+k} \rightarrow \mathbb{N}$ with $(\alpha_1,...,\alpha_n,n_1,...,n_k) \mapsto F(\alpha_1,...,\alpha_n,n_1,...,n_k)$. Keeping $\alpha = (\alpha_1,...,\alpha_n)$ fixed yields $f_\alpha: \mathbb{N}^{k} \rightarrow \mathbb{N}$. –  Hans Stricker Mar 13 '10 at 21:32
    
You may without loss of generality let n = 1: simply encode $\alpha = 2^{a_1} 3^{a_2} \cdots p_n^{a_n}$, where $p_n$ denotes the $n$th prime; then as overhead, your function F can compute the tuple $(a_1, \ldots , a_n)$ from $\alpha$. For a fixed choice of $n$, this procedure is even efficient. --- Of course, it may be more conceptually fruitful to consider tuples $\alpha \in \mathbb N^n$ rather than just $\alpha \in \mathbb N$; but in any case, this indicates that the choice of n will not affect the answer –  Niel de Beaudrap Mar 14 '10 at 13:06
    
Another question (prompted because you use the letter n in multiple places). Do you mean for every graph on more than k vertices to be expressible by this parameterized function F in the manner described above? Or do you instead mean that your parameter n describing the size of the tuples must be greater than k, and the parameterized family of functions F represents all graphs (in the manner described above) provided they are on n vertices? –  Niel de Beaudrap Mar 14 '10 at 13:13
    
I mean "for every graph on more than k vertices". –  Hans Stricker Mar 14 '10 at 15:04

1 Answer 1

up vote 2 down vote accepted

The answer is "yes": there is such a family of $F$ functions. In fact, a single computable function, acting on a single integer argument, suffices. We may do this by storing essentially complete information about the graph, and about the process of "constructing" the graph $G$ (that is, the process of computing suitable integers $n_j$ representing vertices $v_j \in V(G)$), in the integers $n_j$ themselves.

Edit: My original answer contained an error in which the correct adjacency relations were not properly produced. I correct this below, and have taken the opportunity to make other minor revisions.

We may specify a graph on $n$ vertices using a single integer by a number of different methods, such as using binary representation to use an $n^2$ bit integer to give the adjacency matrix of the graph. (The leading 1 represents an entry in the diagonal, which may serve to define the size of the graph without denoting any edges if we consider only simple graphs.) Denote this binary representation of the graph $G$ by $g \in \mathbb N$. We compute the integers $n_j$ by carrying $g$ as the exponents of different primes, and using other prime factors to "induce" adjacency between the integers representing different integers.

Let $p_j$ denote the $j^{\textrm{th}}$ prime, with $p_1 = 2$, $p_2 = 3$, etc. We define $$ N_j = p_j^g $$ which will act as a "label" of sorts for our vertices; each vertex $v_j \in V(G)$ (for an arbitrary ordering of the vertices) will be represented by an integer which is divisible by the prime $p_j$, but not by any other prime $p_k$ for $1 \le k \le n$. At the same time, this labelling carries with it an entire description of the graph, as well as the vertex ordering (in this case, given by the ordering of the rows/columns of the adjacency matrix of $G$). The smallest prime factor of the integer $n_j$ corresponding to the vertex $v_j$ will indicate which vertex it is in the order, and carry a complete description of the graph $G$.

We may induce adjacency among the vertices by giving them appropriate common prime factors. A simple way to do this is to associate a prime to each edge, and give any two vertices belonging to a common edge the corresponding prime factor. (Vertices which do not share an edge in common will have no common prime factors, and thus be coprime.) We order the possible edges by considering the lexicographic ordering on all ordered pairs $(v_j, v_k)$ such that $v_j < v_k$: thus the possible edge $v_j v_k$ (for $j < k$) will be edge number $\varepsilon(j,k) = \binom{k-1}{2} + j$ in the enumeration. More generally, we may define $$ \varepsilon(j,k) = \binom{\max \{j,k\} - 1}{2} + \min \{j,k\} .$$ We may represent the adjacency of two vertices $v_j, v_k$ by giving their corresponding integers $n_j, n_k$ a common prime factor, namely the prime $p_{n+\varepsilon(j,k)}$. The exponents of the primes $p_{n+1}$ through $p_{n+\binom{n}{2}}$ in the integers $n_j$ then form the incidence matrix of edges to vertices in $G$.

Thus, we may let $F(x)$ be the function which computes the following:

  1. Determine the smallest prime $p_{j-1} \mid x$, and the corresponding index $j$.
  2. Determine the exponent, $g$, of the largest power of $p_{j-1}$ which divides $x$.
  3. Extract from $g$ complete information about the graph $G$, including its size $n$.
  4. Determine the next largest prime $p_j > p_{j-1}$.
  5. Compute $N_j = p_j^g$.
  6. Compute $M_j = p_{n+j}$.
  7. For each $1 \le k \le n$, $k \ne j$:
    • Compute $\varepsilon(j,k)$.
    • If $v_j$ is adjacent to $v_k$ in $G$, set $M_j \leftarrow M_j p_{n+\varepsilon(j,k)}$.
  8. Return $y = N_j M_j$.

To produce an appropriate $F$-sequence which represents $G$, it then suffices to compute $n_1$, which is $$ n_1 = p_1^g \prod_{k \ne j} {p_{n+\varepsilon(j,k)}}^{A_{j,k}} , $$ where $A$ is the adjacency matrix of $G$; this suffices to iteratively produce the other integers $n_k$ using $F$.

The above can be readily extended to accommodate hypergraphs (allow more than two vertices per 'edge') and other generalizations; one only needs to choose a suitable representation, and store it in an integer in some way which can be extracted. These are standard tricks in computability theory; we are just adapting Godel numbering for a special purpose in this case.

If you want an "interesting" way of representing graphs by models in integer sequences, which does not just amount to packing and unpacking of data structures in the integers, you're going to have to impose some non-trivial bounds --- on the integer sizes, on the computational efficiency of the procedure, etc. --- and then, you will almost certainly have to be satisfied with obtaining only some special class of graphs. But that special class may still be an interesting one, if your computational constraints are well-chosen.

share|improve this answer
    
@Neil, thanks for this great answer and for the encouragement! –  Hans Stricker Mar 15 '10 at 14:38
    
You're welcome. Can I take it that you accept this answer, then? –  Niel de Beaudrap Mar 15 '10 at 18:20
    
I have to admit, I'm not through all the details, but as soon that I am, I am going to accept it. –  Hans Stricker Mar 15 '10 at 21:55
    
@Niel: Please let me point you to my follow-up question at mathoverflow.net/questions/18535/… where I mention your answer prominently. –  Hans Stricker Mar 18 '10 at 0:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.