# Can every finite graph be represented by an arithmetic sequence of natural numbers?

(This is a follow-up to my previous questions Natural models of graphs?.)

Erdös in The Representation of a Graph by Set Intersections (1966) states:

Theorem. Let $$G$$ be an arbitrary graph. Then there is a set $$S$$ and a family of subsets $$S_1, S_2, ...$$ of $$S$$ which can be put into one-to-one correspondence with the vertices of $$G$$ in such a way that $$x_i$$ and $$x_j$$ are joined by an edge of $$G$$ iff $$i \neq j$$ and $$S_i \cap S_j \neq \emptyset$$.

If we identify $$S$$ with a set of prime numbers and each $$S_i$$ with the product of its members we get the following:

Corollary. Let $$G$$ be an arbitrary finite graph. Then there is a sequence of natural numbers $$(n_1, n_2, ..., n_k)$$ which can be put into one-to-one correspondence with the vertices of $$G$$ in such a way that $$x_i$$ and $$x_j$$ are joined by an edge iff $$i \neq j$$ and GCD$$(n_i, n_j) > 1$$.

We can choose the prime numbers (the elements of $$S$$, from which the $$n_i$$ are built) arbitrarily, and so the question arises, whether they can always be choosen in such a way, that the set $$(n_1, n_2, ..., n_k)$$ is an arithmetic sequence.

Of course every complete graph on $$k$$ nodes can be represented by an arithmetic sequence: just take some consecutive sequence of even numbers. Green-Tao's Theorem guarantees that also every empty graph on $$k$$ nodes can be represented by an arithmetic sequence $$(p_1, p_2, ..., p_k)$$ of primes.

Question: Can every graph on $$k$$ nodes be represented by an arithmetic sequence of natural numbers 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$$

This would be one kind of natural model of a graph, that I was looking for, originally.

Maybe some references?

Question: If not every graph on $$k$$ nodes can be represented by an arithmetic sequence of natural numbers 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$$: Are there interesting classes of graphs with this property?

• Umm...I think the Green-Tao theorem is overkill. To get n+1 coprime integers in an arithmetic progression just consider 1,1+d,1+2d,...,1+nd with d=n!. Nice question though. Commented Mar 11, 2010 at 15:55
• Oh...wait...apart from the fact that it clearly can't be done. Commented Mar 11, 2010 at 15:57
• I did feel that Green-Tao theorem is overkill, thanks for showing me why. I guess there will be an answer to your second comment? Commented Mar 11, 2010 at 16:04
• The new question is not a real question, I feel. Pick a class of graphs you think is interesting and try enough examples that you can make a reasonable guess that it works. Commented Mar 11, 2010 at 17:30
• I will try. And I'll try this: to find other progressions (than arithmetic ones) for which the statement holds for all graphs. Commented Mar 11, 2010 at 18:00

OK so take the unique tree on 3 vertices. Claim: you can't encode this with an arithmetic progression (AP). For if the AP is $a,a+d,a+2d$ then (because we have two edges) either vertices 1 and 2 are joined, or vertices 2 and 3 are joined (or both). Hence there is some $p>1$ such that either $p$ divides both $a$ and $a+d$, or $p$ divides both $a+d$ and $a+2d$. In either case, $p$ then divides $d$, so it divides $a$, so it divides everything, so the graph is complete.