A051252 - Prime Circles - Summary and Update
Gordon Royle
gordon at cs.uwa.edu.au
Tue Jun 25 07:53:44 CEST 2002
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
--
More information about the SeqFan
mailing list