7
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Commented Mar 11, 2010 at 15:55
  • $\begingroup$ Oh...wait...apart from the fact that it clearly can't be done. $\endgroup$ Commented Mar 11, 2010 at 15:57
  • $\begingroup$ 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? $\endgroup$ Commented Mar 11, 2010 at 16:04
  • $\begingroup$ 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. $\endgroup$ Commented Mar 11, 2010 at 17:30
  • $\begingroup$ I will try. And I'll try this: to find other progressions (than arithmetic ones) for which the statement holds for all graphs. $\endgroup$ Commented Mar 11, 2010 at 18:00

1 Answer 1

12
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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.) $\endgroup$ Commented Mar 11, 2010 at 16:34
  • $\begingroup$ What do you think: May I change my question to "Which finite graphs may be represented...?" $\endgroup$ Commented Mar 11, 2010 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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