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 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?

Added: Due to Kevin's concise answer and Thomas' comment, I'd like to add the following question:

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?

share|improve this question
    
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. –  Kevin Buzzard Mar 11 '10 at 15:55
    
Oh...wait...apart from the fact that it clearly can't be done. –  Kevin Buzzard Mar 11 '10 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? –  Hans Stricker Mar 11 '10 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. –  Reid Barton Mar 11 '10 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. –  Hans Stricker Mar 11 '10 at 18:00
add comment

1 Answer

up vote 9 down vote accepted

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.

share|improve this answer
    
This argument can be extended to show the same for any tree (on at least three vertices). Might it still be possible for an interesting subclass of graphs? (e.g. graphs containing cycles, or graphs with complete components.) –  Thomas Bloom Mar 11 '10 at 16:34
    
What do you think: May I change my question to "Which finite graphs may be represented...?" –  Hans Stricker Mar 11 '10 at 16:58
add comment

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.