My Math Forum (http://mymathforum.com/math-forums.php)
-   Number Theory (http://mymathforum.com/number-theory/)
-   -   Graph theory and number theory (http://mymathforum.com/number-theory/22114-graph-theory-number-theory.html)

 proglote October 29th, 2011 07:01 PM

Graph theory and number theory

(Self-proposed) Given a graph with n vertices, assign a positive integer greater than one to each vertex, such that the integers are consecutive. Draw an edge connecting two vertices iff the numbers assigned to them and relatively prime. Is it possible for such a graph be planar for all $n \in \mathbb{N}$ ?

For n = 6 just choose the numbers 11, 12, 13, 14, 15, 16. I couldn't find a possibility for n = 7 (haven't tried much though).

Any ideas?

 Peter October 30th, 2011 02:09 AM

Re: Graph theory and number theory

It is certainly not possible for any n. A very bad bound would be:

It is not possible, if n is bigger than $37=2\cdot 3\cdot 5 + 7$.

If n is that big, one can easily find a complete graph with 5 vertices, which is contained (and known to be not planar).

Here is how it works: Take k to be the smallest number in your numbering of the vertices, that is divisible by 2,3, and 5. Then the numbers k+1, k+2, k+3, k+5 and k+7 occure as numbers of vertices. However, the difference of two of them is at most 6, so only the primes 2,3, and 5 could divide two of them, but that is absurd, as 2 divids only k+2, 3 divides only k+3 and 5 divides only k+5. It follows, that these numbers are pairwise coprime, showing the assertion.

I'm sure one can improve this bound easily, and exspect the bound to be in the area of 10. May be the 3-3 graph is even easier to find.

rgds
Peter

 proglote October 30th, 2011 09:49 AM

Re: Graph theory and number theory

Thanks for the bound, Peter. I see by Turán we can have at most $\frac{3}{8} n^2$ edges. Is there a similar theorem for complete bipartite subgraphs such as $K_{3,3}$? Because for n = 8 we need less than 24 edges, and if we choose (48 -> 55) we have 19 edges but I still think it's not planar!

 proglote October 30th, 2011 05:20 PM

Re: Graph theory and number theory

I will show that $n \ < \ 13.$

Let $S$ be the set of n consecutive numbers. If $n \ge 13$, then there is a number $k \in S$ such that $k \equiv \{2,8,11} \ mod \ 15$ and $k + 6 \in S$, which follows because given seven consecutive numbers, one of them, k, must be congruent to 2, 8 or 11 mod 15, thus given 13 consecutive numbers $k+6 \in S.$

Consider the vertices to which k, k+1, k+2, k+3, k+5 and k+6 are assigned. Separate them in two groups : k, k+2, k+6 and k+1, k+3, k+5. There is an edge connecting (k, k+1), (k+1,k+2), (k+2,k+3) and (k+5,k+6) because they are consecutive. If k is not divisible by 3, there is an edge (k, k+3) and (k+3,k+6). If k is not divisible by 5, there is an edge (k,k+5). If k is not congruent to 1 modulo 3, there is an edge (k+2, k+5). If k is not congruent to 4 modulo 5, there is an edge connecting (k+1,k+6). Then these two groups form a complete bipartite graph, hence the graph is not planar.

Putting the restrictions above together, we need k to be congruent to 2 modulo 3 and k to be congruent to 1, 2 or 3 modulo 5, thus if there is a k congruent to 2, 8 or 11 mod 15, then the graph is not planar, which is the case for $n \ge 13$ as proven above.

I am still not sure about n = 8, 9, 10, 11, 12 though.

 All times are GMT -8. The time now is 06:19 PM.