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?

Improve this question
$\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$
    – The Masked Avenger
    Commented 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$
    – Ilya Bogdanov
    Commented Apr 22, 2015 at 7:25
  • 2
    $\begingroup$ then this asks for en.wikipedia.org/wiki/BEST_theorem $\endgroup$
    – Dima Pasechnik
    Commented 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$
    – Richard Stanley
    Commented 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$
    – Dima Pasechnik
    Commented Apr 24, 2015 at 5:28

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .