Return to Question

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

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

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

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