Timeline for A digraph related to permutations
Current License: CC BY-SA 3.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 25, 2015 at 20:12 | comment | added | Richard Stanley | One reason that the number of Hamiltonian cycles divided by $(n-1)!^{(n-1)!}$ factors quite a bit is the $S_n$-symmetry. A similar situation is at OEIS oeis.org/A120061. See also Chapter 10, Exercise 7(d) of my book Algebraic Combinatorics. | |
| Apr 24, 2015 at 5:29 | comment | added | Dima Pasechnik | takes 0.5 sec on my laptop (n is the number after $6!^{720}$) | |
| Apr 24, 2015 at 5:28 | comment | added | Dima Pasechnik | 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 | |
| Apr 24, 2015 at 1:59 | comment | added | Richard Stanley | Continuation of previous comment: $02167802121430577869247906928263206218129022043438732817393$ $78238299321477251081703396523732122511001097003078223354740$ $21115543570842542767571682953869289112205514506240000000000000000000$. This must have a large prime factor since Maple has been taking many hours trying to factor it. | |
| Apr 24, 2015 at 1:58 | comment | added | Richard Stanley | For $n=7$ the number is $6!^{720}\cdot 176183413608273968258307195020261201995935498443817037880077$ $33015680734978977985994540951427241494888517320111715796104$ $01678883391824293568187890362411864333732042160720070054426$ $13973761520215432676342816642484823001649942753538184971817$ $00932653194251714270416078406552688838875907139437076885891$ $46604444975789292489211082309639859152636172062362845942377$ $16134182843447651691194901389583522511049879097164330759592530013$ (continued on next comment) | |
| Apr 23, 2015 at 18:55 | comment | added | Richard Stanley | For $n =6$ the number is $5!^{120}\cdot 2^{32}\cdot 3^{29} \cdot 5^{20}\cdot 7^9\cdot 23\cdot 37^3\cdot 53\cdot 79\cdot 83\cdot 311^9\cdot 1993\cdot 5569\cdot 57679$. | |
| Apr 23, 2015 at 18:41 | comment | added | Richard Stanley | For $n=5$ the number of Hamiltonian cycles is $4!^{24}\cdot 2^{11}\cdot 3^5\cdot 5^6\cdot 13^2\cdot 17\cdot 47$. | |
| Apr 23, 2015 at 8:29 | comment | added | Dima Pasechnik | actually, I wonder if BEST really applies, as $P_n$ has degree $n$, whereas for BEST one would want degree $n+1$, at least naively. | |
| Apr 23, 2015 at 2:28 | comment | added | David Feldman | Right about the factorization...it drops out of the BEST_theorem at least in the form $6^6*280$. The $280$ constitutes a count of arborescences but has an efficient expression as a determinant (though of perhaps a very large matrix as $n$ grows). | |
| Apr 22, 2015 at 19:46 | comment | added | Richard Stanley | The factorization $13063680=2^9\cdot 3^6\cdot 5\cdot 7$ suggests that there might be a simple exact answer in general. | |
| Apr 22, 2015 at 8:26 | review | Suggested edits | |||
| Apr 22, 2015 at 9:09 | |||||
| Apr 22, 2015 at 8:08 | comment | added | Dima Pasechnik | @DavidFeldman, sure, you're welcome! | |
| Apr 22, 2015 at 7:45 | comment | added | David Feldman | Perfect! Thank you Ilya and Dima. My application is mathematical music theory. When and if I write something, may I simply credit you for your help? | |
| Apr 22, 2015 at 7:39 | comment | added | Dima Pasechnik | then this asks for en.wikipedia.org/wiki/BEST_theorem | |
| Apr 22, 2015 at 7:25 | comment | added | Ilya Bogdanov | 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. | |
| Apr 22, 2015 at 7:14 | comment | added | David Feldman | No, Dima, unless I'm misunderstanding. For example 4123 points to 2341 because 123 and 234 have the same position to rank function. But they're not the same sequence of symbols, so no edge connects them in the DeBruijn graph. | |
| Apr 22, 2015 at 6:46 | comment | added | Dima Pasechnik | if you consider en.wikipedia.org/wiki/De_Bruijn_graph, more precisely the one on $n^n$ vertices, then your graph is a subgraph where each vertex corresponds to a permutation of $n$ symbols, right? | |
| Apr 22, 2015 at 5:39 | comment | added | David Feldman | "Sounds like" can cover a multitude of sins. One can attempt to represent a Hamiltonian of my sort by an actual sequence of reals (or natural numbers), but one finds that some Hamiltonians in $P_4$ require 23 distinct values (though others, as few as 5; these special cases only have a DeBruijn feel). | |
| Apr 22, 2015 at 4:11 | comment | added | The Masked Avenger | This sounds like a subgraph of a graph based on DeBruijn sequences. You might check out the larger graph and its properties. | |
| Apr 22, 2015 at 3:55 | comment | added | Steve Huntsman | mathoverflow.net/questions/49555 | |
| Apr 22, 2015 at 3:41 | history | asked | David Feldman | CC BY-SA 3.0 |