5
$\begingroup$

A finite sequence of distinct real numbers of length $n$ determines a linear order of $\{1,\ldots,n\}$, by mapping position to rank; call this the permutation of the sequence.

Consider the following digraph $P_n$. The vertex set of $P_n$ comprises all the linear orders of $\{1,\ldots,n\}$. Then an arrow connects vertex $v$ to vertex $w$ exactly when the permutation of $v$'s terminal length $n-1$ subsequence equals the permutation $w$'s initial length $n-1$ subsequence.

Question 1: Do these digraphs occur in the literature, and perhaps have a standard terminology and notation?

Observation: I have verified the following (which surprised me) by exhaustive computation: $P_4$ admits 13063680 Hamiltonian paths originating from $v=(1,2,3,4)$ and every one of these extends to a Hamiltonian cycle!

Question 2: Is the previous observation a direct consequence of known theorem?

Question 3: Is anything known about the asymptotics of enumerations of Hamiltonian cycles in these digraphs?

$\endgroup$
19
  • 1
    $\begingroup$ This sounds like a subgraph of a graph based on DeBruijn sequences. You might check out the larger graph and its properties. $\endgroup$ Apr 22, 2015 at 4:11
  • 1
    $\begingroup$ Each Hamiltonian path prolongates to a Hamiltonian cycle exactly for the same reason as the complete domino chain has the same numbers on both ends: a Hamiltonian cycle is an Eulerian path in a graph on the permutations of $n-1$ symbols. $\endgroup$ Apr 22, 2015 at 7:25
  • 2
    $\begingroup$ then this asks for en.wikipedia.org/wiki/BEST_theorem $\endgroup$ Apr 22, 2015 at 7:39
  • 1
    $\begingroup$ The factorization $13063680=2^9\cdot 3^6\cdot 5\cdot 7$ suggests that there might be a simple exact answer in general. $\endgroup$ Apr 22, 2015 at 19:46
  • 1
    $\begingroup$ sage: factor(n) 2^307 * 3^120 * 5^19 * 7^128 * 11 * 13^3 * 19^44 * 31 * 43^44 * 47 * 61 * 113^6 * 127 * 131 * 139^2 * 241 * 1031 * 1481^2 * 1531 * 1621^2 * 1699^2 * 2801^3 * 5147 * 10607 * 47917^2 * 90803^2 * 548521 * 685367 * 2460593 * 47389957 * 2920679263^2 * 8428156447^2 * 216271121699 * 285106814092712039^2 $\endgroup$ Apr 24, 2015 at 5:28

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.