Timeline for Arranging all permutations on $\{1,\ldots,n\}$ such that there are no common points
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 2, 2019 at 21:05 | comment | added | fedja | @DominicvanderZypen OK, posted. | |
| May 30, 2019 at 4:17 | comment | added | Dominic van der Zypen | @fedja, it is still of interest to me, I would be glad to hear about it! | |
| May 30, 2019 at 1:27 | comment | added | fedja | @DominicvanderZypen Actually, you can derive the existence of the Hamiltonian cycle drom Dirac's criterion but you have to apply it to some other graph. Let me know if it is still of any interest to you. | |
| May 29, 2019 at 15:24 | comment | added | Martin Rubey | Here is a short program for sage that gives you a Hamiltonian cycle for $n=5$: $\verb|G = lambda n: Graph([Permutations(n), lambda pi1, pi2: all(e != f for e, f in zip(pi1, pi2))])|$ $\verb|G(5).hamiltonian_cycle(algorithm='backtrack')|$ | |
| May 29, 2019 at 14:27 | comment | added | fedja | @DominicvanderZypen The vertex degree here is only about $|V|/e$, so it is a bit short of what you want. | |
| May 29, 2019 at 14:25 | comment | added | Dominic van der Zypen | There is this result by Dirac that states that if the minimum degree of a graph $G=(V,E)$ is larger than $|V(G)|/2$ then $G$ has a Hamiltonian cycle. Maybe such an argument can be applied here? | |
| May 29, 2019 at 13:02 | comment | added | Dominic van der Zypen | Oh - thanks! I suppose this implies that there is a Hamiltonian cycle for all $n\geq 4$, but I just can't write down the argument properly | |
| May 29, 2019 at 12:46 | history | answered | Robert Israel | CC BY-SA 4.0 |