A051252 - Prime Circles - Summary and Update

[Gordon Royle]

Dear Sequence Fans and Combinatorialists

There has been considerable correspondence, started by a question
from Santi Spadaro, about a "curious graph", which seems to have generated
both some interest and some confusion, with several threads heading off
tangentially. It has also been occurring in (at least) two forums - comb-l
and the mailing list for sequence fans.

I thought I would try to summarize the situation for everyone concerned:

Consider the graph G(2m) which has vertex set {1,2,...,2m} and
where (i,j) is an edge if and only if i+j is prime. For example, the 
graph G(8) has

  vertices: 1, 2, 3, 4, 5, 6, 7, 8
  edges: (1,2) (1,4) (1,6) (2,3) (2,5) (3,4) (3,8) (4,7) (5,6) (5,8) (6,7) 


The question raised by Santi is 

	"Is G(2m) hamiltonian for all values of m?"

Recall that a graph is hamiltonian if there is a cycle passing through
all the vertices of the graph; such a cycle is called a Hamilton cycle.

It is clear that G(8) is hamiltonian, because we can identify two 
different Hamilton cycles:

	1 - 2 - 3 - 8 - 5 - 6 - 7 - 4 
and
	1 - 2 - 5 - 8 - 3 - 4 - 7 - 6


If we fire up the computer, we discover that 

	G(8)  has 2 different Hamilton cycles
	G(10) has 48 different Hamilton cycles
	G(12) has 512 different Hamilton cycles
	G(14) has 1440 different Hamilton cycles
	G(16) has 40512 different Hamilton cycles
	...
	G(22) has 106906168 different Hamilton cycles

These numbers were computed by brute force search conducted by Jud McCranie.


This strongly suggests that Santi's question should be answered in the
affirmative - he is only asking for ONE Hamilton cycle, while this 
computational evidence suggests that there are VAST numbers of Hamilton cycles
However computational evidence is no proof, and so the question is

	"Can we PROVE the existence of even ONE Hamilton cycle in G(2m)?"

Now, the sequence of numbers 2, 48, 512, 1440 etc is listed in Neil
Sloane's Encylopaedia of Integer Sequences as sequence A051252 and it
turns out that these Hamilton cycles in G(2m) are also called "prime
circles". Notice that the phrase "prime circle" has nothing to do with
GEOMETRIC circles; they are defined purely combinatorially and are
*precisely* equivalent to Hamilton cycles in G(2m). 


	Ham cycle in G(2m)			Prime circle

1 - 2 - 3 - 8 - 5 - 6 - 7 - 4			   4 - 1
					         /      \
						7        2
                                                |        |
						6        3
 						 \      /
						  5 - 8


So do we even know that the sequence has infinitely many non-zero entries?

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

-- 
Dr. Gordon F Royle, http://www.cs.uwa.edu.au/~gordon, gordon at cs.uwa.edu.au
--