My Math Forum Graph theory and number theory

 Number Theory Number Theory Math Forum

 October 29th, 2011, 06:01 PM #1 Senior Member   Joined: Apr 2011 From: Recife, BR Posts: 352 Thanks: 0 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?
 October 30th, 2011, 01:09 AM #2 Senior Member   Joined: Sep 2008 Posts: 150 Thanks: 5 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
 October 30th, 2011, 08:49 AM #3 Senior Member   Joined: Apr 2011 From: Recife, BR Posts: 352 Thanks: 0 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!
 October 30th, 2011, 04:20 PM #4 Senior Member   Joined: Apr 2011 From: Recife, BR Posts: 352 Thanks: 0 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.

 Tags graph, number, theory

,

,

### graph theory forum

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Ecllipsers Applied Math 0 February 9th, 2014 03:46 PM avnerg Applied Math 0 September 18th, 2013 06:03 AM sulonski Applied Math 1 August 2nd, 2012 10:03 AM johnyjj2 Applied Math 0 December 28th, 2010 02:49 PM davy89 Applied Math 1 November 30th, 2008 01:05 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top