Skip to main content
MathOverflow

Return to Answer

added 804 characters in body
Source Link
Gerhard Paseman
Gerhard Paseman
  • 3.2k
  • 1
  • 18
  • 29

Update 2014.04.10: An unverified run suggests there are NO Hamilton path solutions for the 4x4x2 brick. After adding code to detect multiple vertices not yet on the path with only one neighbor, the search visited a little over 1.27 million candidates before failing to find a compatible path of length 30, much less one of length 32. I am now considering an argument involving configurations of numbers divisible by 3 in a potential path in order to get a combinatorial proof of impossibility. It is easy to determine that a 2x2x2 corner section has either 2 or 3 such numbers, and in the case of three, they must all be the same parity. However I have not completed it to show impossibility. If I do, this is the first example (4,4,2) I know which would have only non Hamiltonian solutions.

Gerhard "Ask Me About Sloppy Coding" Paseman, 2014.04.07

Gerhard "Ask Me About Sloppy Coding" Paseman, 2014.04.07

Update 2014.04.10: An unverified run suggests there are NO Hamilton path solutions for the 4x4x2 brick. After adding code to detect multiple vertices not yet on the path with only one neighbor, the search visited a little over 1.27 million candidates before failing to find a compatible path of length 30, much less one of length 32. I am now considering an argument involving configurations of numbers divisible by 3 in a potential path in order to get a combinatorial proof of impossibility. It is easy to determine that a 2x2x2 corner section has either 2 or 3 such numbers, and in the case of three, they must all be the same parity. However I have not completed it to show impossibility. If I do, this is the first example (4,4,2) I know which would have only non Hamiltonian solutions.

Gerhard "Ask Me About Sloppy Coding" Paseman, 2014.04.07

Update on hamilton solutions for 3x3x3.
Source Link
Gerhard Paseman
Gerhard Paseman
  • 3.2k
  • 1
  • 18
  • 29

Update 1: It turns out there are three distinct solutions, all with a terminating 3x3x1 block containing the numbers 19 through 27. The basic problem is in enumerating a 3x3x2 block with the numbers 1 through 18 that allows the last "layer" to be added. Also, a (2x3x1) layer is involved which contains the numbers 13-18 or 12-17. I suspect an approach similar to nsrt's modified for Hamilton paths may show that nx3x3 enumerations will exist for n sufficiently large, as one may be able to arrange layers so that all small (and thus all) gcd relations are observed. I suspect the answer to the original question for three dimensions will be yes, and in a Hamiltonian fashion. It should not be too hard in addition to find conditions on bipartite graphs (e.g. degree conditions) which would constitute obstructions to a coprime Hamiltonian labelling. Indeed, one of the 3x3x3 solutions has a path in a 2x3x3 subgraph which is extendable to a cycle (so 1 and 18 are adjacent in this solution).

Gerhard "Ask Me About Sloppy Coding" Paseman, 2014.04.07

Gerhard "Ask Me About Sloppy Coding" Paseman, 2014.04.07

Update 1: It turns out there are three distinct solutions, all with a terminating 3x3x1 block containing the numbers 19 through 27. The basic problem is in enumerating a 3x3x2 block with the numbers 1 through 18 that allows the last "layer" to be added. Also, a (2x3x1) layer is involved which contains the numbers 13-18 or 12-17. I suspect an approach similar to nsrt's modified for Hamilton paths may show that nx3x3 enumerations will exist for n sufficiently large, as one may be able to arrange layers so that all small (and thus all) gcd relations are observed. I suspect the answer to the original question for three dimensions will be yes, and in a Hamiltonian fashion. It should not be too hard in addition to find conditions on bipartite graphs (e.g. degree conditions) which would constitute obstructions to a coprime Hamiltonian labelling. Indeed, one of the 3x3x3 solutions has a path in a 2x3x3 subgraph which is extendable to a cycle (so 1 and 18 are adjacent in this solution).

Gerhard "Ask Me About Sloppy Coding" Paseman, 2014.04.07

Source Link
Gerhard Paseman
Gerhard Paseman
  • 3.2k
  • 1
  • 18
  • 29

Intrigued by the notion in other posts and comments that there might be solutions to this problem involving Hamiltonian paths, I wrote a program to do breadth-first enumeration of such paths for the 3x3x3 case, and got some interesting results. One nice aspect is that on bipartite graphs, no checking for divisibility by 2 of adjacent pairs is needed, and as a result the number of divisibility checks is halved (so vertices labeled 3 and 9 will never be adjacent).

The results are unverified; the current output is

! 1145801 -19-22-25-26-23-20-21-24-27-18-15-12-3-6-9-8-17-14-11-10-13-16-7-4-1-2-5-

! 1145802 -21-24-27-26-23-20-19-22-25-16-13-10-1-4-7-8-17-14-11-12-15-18-9-6-3-2-5-

! 1145803 -19-22-25-26-23-20-21-24-27-18-15-12-3-6-9-8-7-4-1-10-13-16-17-14-11-2-5-

! 1145804 -21-24-27-26-23-20-19-22-25-16-13-10-1-4-7-8-9-6-3-12-15-18-17-14-11-2-5-

! 1145805 -21-24-27-18-15-12-3-6-9-8-7-4-1-10-13-16-25-22-19-20-23-26-17-14-11-2-5-

! 1145806 -19-22-25-16-13-10-1-4-7-8-9-6-3-12-15-18-27-24-21-20-23-26-17-14-11-2-5-

where the output corresponds to a path based on my enumeration of the vertices. Solution 1145801 corresponds to:

3 2 15 # 8 9 16 # 27 22 21

4 1 14 # 7 10 17 # 26 23 20

5 12 13 # 6 11 18 # 25 24 19

I have not checked all the results, but I believe there are 4 non-isomorphic solutions, all starting with 1 in the middle of the bottom square. I invite verification of this. I also took some statistics on paths of intermediate lengths. I can't properly normalize them, but they suggest interesting growth patterns which are likely a consequence of the gcd restriction. I wonder if growth patterns from such enumerations of partial structures have been studied, and if a solution can be predicted from such growth patterns. In particular, can one predict that there would be a small number of nonisomorphic solutions in this case.

Based on other small examples, I have found Hamilton path enumerations for all of them and would like to see a conjecture on (the shape of parameters for) a grid graph that has a solution which is non Hamiltonian, and no Hamiltonian solutions.

I will update this with some more results.

Gerhard "Ask Me About Sloppy Coding" Paseman, 2014.04.07