Timeline for Knight tour prime (conjecture)
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 9, 2012 at 8:00 | comment | added | Eric Naslund | @Gerry Myerson: Intuition tells me that in some sense, the graph is extremely disconnected, but I am not sure how to state this correctly/prove it. | |
| May 8, 2012 at 23:43 | comment | added | Roberto Bosch Cabrera | @Gerry Myerson: thanks for your new questions. | |
| May 8, 2012 at 23:23 | answer | added | timur | timeline score: 4 | |
| May 8, 2012 at 23:17 | comment | added | Gerry Myerson | So, for each $n$, we have a graph whose vertices are the primes up to $n^2$, with two primes adjacent if they are a knight's move away from each other on an $n\times n$ board. The question was whether the graph is Hamiltonian, and Eric's answer, that there is no path at all, says it's not even connected. This suggests a few questions: how many components does the graph have (as a function of $n$)? How large is the largest component? How long is the longest path? Are there cycles for some/most/all large $n$? What is the size of the component containing 2? | |
| May 8, 2012 at 19:41 | answer | added | Eric Naslund | timeline score: 19 | |
| May 8, 2012 at 19:22 | comment | added | Eric Naslund | If $n$ is odd, you can color the board as a checkerboard. Note that odd squares will always be white, and even squares will always be black. Since the knight alternates colors on each jump, and there is only one even prime, the result is proven. Maybe there is a similar trick for $n$ even. | |
| May 8, 2012 at 18:44 | history | asked | Roberto Bosch Cabrera | CC BY-SA 3.0 |