A051252 - Prime Circles - Summary and Update

[John Conway]

   I wrote that I found it very hard to believe that this had been
proved.  I'm sorry - It was indeed obvious.  John Conway


> As Mike Hennebry pointed out, if 2m+1 and 2m+3 are both prime, then we
> can definitely find a hamilton cycle in G(2m). For example, this is the
> case with G(10) where 11 and 13 are both prime. We find the Hamilton 
> cycle as follows:
> 
> 	- write down the odd numbers from 1 to 2m-1 in a column
> 	- write down the even numbers backwards from 2m to 2 adjacent to them
> 
> 	1  10
> 	3  8
> 	5  6
> 	7  4
> 	9  2
> 
> Then because 2m+1 is prime, every vertex is adjacent to its horizontal
> neighbour
>  	
> 	1 - 10
> 	3 - 8
> 	5 - 6
> 	7 - 4
> 	9 - 2
> 
> Because 2m+3 is prime, each even number is adjacent to the odd number
> to its left and one-step-down.
>                                                  
> 	1 - 10
>           /
> 	3 - 8
>           /
> 	5 - 6
>           /
> 	7 - 4
>           /
> 	9 - 2
> 				
> Because 3 is prime, 1 is adjacent to 2 and so we complete the Hamilton
> cycle
> 
> 	1 - 10 - 3 - 8 - 5 - 6 - 7 - 4 - 9 - 2
> 
> 
> So at least we have a large supply of G(2m)s that we *can* prove are
> Hamiltonian.... however it is NOT known whether there are an infinite
> number of "twin primes" or not, and so we have not even yet found an
> infinite family of hamiltonian G(2m)s.
> 
> So, in decreasing order of difficulty, the open problems are:
> 
> 	1. Find an expression for the number of Hamilton cycles in G(2m)
> 
> 		- this is unlikely to be possible
> 
> 	2. Show that every G(2m) has at least ONE Hamilton cycle
> 
> 		- this is almost certainly true, but needs some sort
> 		of proof, maybe inductive or maybe a "strategy" for
> 		creating a Hamilton cycle, or maybe even numerical
> 		by showing the graph is sufficiently dense to force
> 		a Hamilton cycle (though I think the graph is not
> 		dense enough for this).
> 
> 	3. Find an infinite family of G(2m)s that DO have Hamilton cycles
> 
> 		- an ad hoc proof would suffice here; find some condition
> 		on 2m that yields a Hamilton cycle
> 
> 	4. Find more families of G(2m) that do have Hamilton cycles
> 
> 		- ditto
> 
> 
> The number of edges in G(n) is given by sequence A071917 (notice that here
> n can be even or odd, the number of edges makes sense but G(odd) can 
> never be hamiltonian because the graph is bipartite).
> 
> RELATED PROBLEMS
> 
> 
> There are some related problems which may or may not prove useful....
> 
> 	Any 1-factor (collection of m disjoint edges) in G(2m) gives
> 	a partition of {1,2,..2m} into m pairs, each pair summing to a prime. 
> 	A Hamilton cycle gives you two 1-factors (each 1-factor consists of
> 	alternating edges of the cycle), and hence yields two disjoint
> 	partitions. But the reverse implication is not true - you can't
> 	necessarily put together two disjoint partitions to get a 
> 	Hamilton cycle. So proving things about disjoint partitions, while
> 	it may be interesting in itself, does not prove anything about
> 	Hamilton cycles in G(2m).
> 	
> 	There is a page run by Carlos Rivera (www.primepuzzles.net) which
> 	mentions a problem (Number 176) that is *harder* than Santi's problem. 
> 	He wants to arrange the numbers from 1...2m in a circle (again, 
> 	a combinatorial circle not a geometric circle) such that in 
> 	addition to adjacent entries summing to a prime, we also have *opposite* 
> 	numbers summing to a prime. Any solution to "Problem 176" is automatically
> 	a Hamilton cycle in G(2m), however a Hamilton cycle in G(2m) may not
> 	have the additional property required by "Problem 176".  
> 	In general therefore, the number of solutions to "Problem 176" will be 
> 	smaller than the number of Hamilton cycles in G(2m).  Because G(2m) is 
> 	bipartite (even numbers and odd numbers), "Problem 176" cannot 
> 	have a solution if m is even (because then the opposite numbers
> 	are both odd or both even and so clearly cannot sum to a prime).
> 
> 	The smallest solution is for 2m = 10 when we have
> 
> 	1 - 2 - 3 - 4 - 7 - 6 - 5 - 8 - 9 - 10
> 
> 	as a solution (the additional conditions are satisfied by the
> 	opposite pairs (1,6) (2,5) (3,8) (4,9) (7,10)) and in fact the
> 	above example of the "2m+1,2m+3" construction is also a solution
> 	to "Problem 176".
> 
> 	For small 2m, the numbers of solutions to "Problem 176" are
> 
> 		2m=6	0	
> 		8	0
> 		10	4
> 		12	0
> 		14	8
> 		16 	0
> 		18	556 
> 
> 	so it would appear that even this harder problem has lots of 
> 	solutions. 
> 
> 
> EXTENSIONS
> 
> 
> 	Santi and others have extended the problem to consider things
> 	like "prime latin squares". I won't comment on these now as this
> 	message is already too long.
> 
> 
> 
> 
> 	Cheers
> 
> 	Gordon
> 
>