Hamiltonian paths where the vertices are integer partitions - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T12:42:08Z http://mathoverflow.net/feeds/question/16107 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/16107/hamiltonian-paths-where-the-vertices-are-integer-partitions Hamiltonian paths where the vertices are integer partitions Burhan 2010-02-22T23:46:09Z 2012-07-18T05:30:26Z <p>Hello,</p> <p>I have been working on this problem for several months now but have not made much progress. It concerns the set of all <a href="http://en.wikipedia.org/wiki/Integer%5Fpartitions" rel="nofollow">integer partitions</a> of n. </p> <p>Let the vertices of the graph G=G(n) denote all the p(n) integer partitions of n. There is an edge between two partitions if and only if one can be transformed into another by only moving one dot between rows in their Ferrers diagram representations. </p> <p>So, for example, the partitions (3,2,1) and (3,3) of 6 are linked because we can move the dot in the last row to the second row.</p> <pre><code>OOO OOO OO -------- OOO O </code></pre> <p>My question: for what values of n does G(n) have a Hamiltonian path from (n) to (1,1,...,1)? </p> <p>That is, is it possible to go through, without repetition, all the partitions of n by simply moving around the dots in the Ferrers diagrams? </p> <p>Is there a determinate way to construct such paths?</p> <p>I have only been able to construct paths for n = 1 to 6.</p> <p>n=1 (trivial)</p> <p>n=2: (2) => (1,1)</p> <p>n=3:<br /> (3) => (2,1) => (1,1,1)</p> <p>n=4:<br /> (4) => (3,1) => (2,2) => (2,1,1) => (1,1,1,1)</p> <p>n=5: (5) => (4,1) => (3,2) => (2,2,1) => (3,1,1) => (2,1,1,1) => (1,1,1,1,1)</p> <p>n=6: (6) => (5,1) => (4,1,1) => (4,2) => (3,3) => (3,2,1) => (2,2,2) => (2,2,1,1) => (3,1,1,1) => (2,1,1,1,1) => (1,1,1,1,1,1)</p> <p>None of the basic theorems about Hamiltonian paths have not helped me here. </p> http://mathoverflow.net/questions/16107/hamiltonian-paths-where-the-vertices-are-integer-partitions/16111#16111 Answer by Steve Huntsman for Hamiltonian paths where the vertices are integer partitions Steve Huntsman 2010-02-23T00:35:39Z 2010-02-23T14:38:12Z <p>There seems to be a general pattern indicated by your $n=6$ example. Here is a path for $n=7$:</p> <pre><code>1. 7 2. 6 + 1 3. 5 + 2 4. 5 + 1 + 1 5. 4 + 1 + 1 + 1 6. 4 + 2 + 1 7. 4 + 3 8. 3 + 3 + 1 9. 3 + 2 + 2 10. 2 + 2 + 2 + 1 11. 3 + 2 + 1 + 1 12. 3 + 1 + 1 + 1 + 1 13. 2 + 2 + 1 + 1 + 1 14. 2 + 1 + 1 + 1 + 1 + 1 15. 1 + 1 + 1 + 1 + 1 + 1 + 1 </code></pre> <p>I have written this so that it is obvious that all 15 partitions of 7 are accounted for. Note the 10th partition.</p> <p>Here is one for $n = 8$:</p> <pre><code>1. 8 2. 7 + 1 3. 6 + 2 4. 6 + 1 + 1 5. 5 + 1 + 1 + 1 6. 5 + 2 + 1 7. 5 + 3 8. 4 + 4 9. 4 + 3 + 1 10. 4 + 2 + 2 11. 4 + 2 + 1 + 1 12. 4 + 1 + 1 + 1 + 1 13. 3 + 1 + 1 + 1 + 1 + 1 14. 3 + 2 + 1 + 1 + 1 15. 3 + 3 + 1 + 1 16. 3 + 2 + 2 + 1 17. 3 + 3 + 2 18. 2 + 2 + 2 + 2 19. 2 + 2 + 2 + 1 + 1 20. 2 + 2 + 1 + 1 + 1 + 1 21. 2 + 1 + 1 + 1 + 1 + 1 + 1 22. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 </code></pre> <p>$n=9$:</p> <pre><code>1. 9 2. 8 + 1 3. 7 + 2 4. 7 + 1 + 1 5. 6 + 1 + 1 + 1 6. 6 + 2 + 1 7. 6 + 3 8. 5 + 4 9. 5 + 3 + 1 10. 5 + 2 + 2 11. 5 + 2 + 1 + 1 12. 5 + 1 + 1 + 1 + 1 13. 4 + 1 + 1 + 1 + 1 + 1 14. 4 + 2 + 1 + 1 + 1 15. 4 + 2 + 2 + 1 16. 4 + 3 + 1 + 1 17. 4 + 4 + 1 18. 4 + 3 + 2 19. 3 + 3 + 3 20. 3 + 3 + 2 + 1 21. 3 + 2 + 2 + 2 22. 2 + 2 + 2 + 2 + 1 23. 3 + 2 + 2 + 1 + 1 24. 3 + 3 + 1 + 1 + 1 25. 3 + 2 + 1 + 1 + 1 + 1 26. 2 + 2 + 2 + 1 + 1 + 1 27. 3 + 1 + 1 + 1 + 1 + 1 + 1 28. 2 + 2 + 1 + 1 + 1 + 1 + 1 29. 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 30. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 </code></pre> http://mathoverflow.net/questions/16107/hamiltonian-paths-where-the-vertices-are-integer-partitions/16112#16112 Answer by Michael Lugo for Hamiltonian paths where the vertices are integer partitions Michael Lugo 2010-02-23T00:45:05Z 2010-02-23T00:45:05Z <p>What you want is known as a Gray code for integer partitions. </p> <p>It exists. </p> <p>See C. D. Savage, Gray code sequences of partitions, <i>Journal of Algorithms</i> 10 (1989) 577-595. Disclaimer: I haven't actually read this paper. Other sources such as <a href="http://www4.ncsu.edu/~savage/AVAILABLE_FOR_MAILING/survey.ps" rel="nofollow">this 1997 survey by Savage</a> and <a href="http://www.cs.uiowa.edu/~sriram/196/fall01/lecture7.ps" rel="nofollow">these class notes</a> don't say what the construction is but say that it's complicated.</p> http://mathoverflow.net/questions/16107/hamiltonian-paths-where-the-vertices-are-integer-partitions/16126#16126 Answer by Igor Pak for Hamiltonian paths where the vertices are integer partitions Igor Pak 2010-02-23T05:23:24Z 2010-02-23T05:28:31Z <p>There are two great general sources for Gray codes on combinatorial objects you might enjoy:</p> <p>1) Frank Ruskey's "Combinatorial Generation" book: <a href="http://tinyurl.com/yly4pq7" rel="nofollow">http://tinyurl.com/yly4pq7</a></p> <p>2) Don Knuth's "Art of Computer Programming", Vol. 4, Fascicle 2-4 (published separately - all excellent), see <a href="http://www-cs-faculty.stanford.edu/~uno/taocp.html" rel="nofollow">http://www-cs-faculty.stanford.edu/~uno/taocp.html</a></p> <p>Preliminary versions of some of these can be downloaded from the internet archive: <a href="http://tinyurl.com/yfo57t4" rel="nofollow">http://tinyurl.com/yfo57t4</a></p> http://mathoverflow.net/questions/16107/hamiltonian-paths-where-the-vertices-are-integer-partitions/102510#102510 Answer by Brian Hopkins for Hamiltonian paths where the vertices are integer partitions Brian Hopkins 2012-07-18T05:30:26Z 2012-07-18T05:30:26Z <p>If you mean to allow any part to go down 1 and any part (or 0) to go up 1, while maintaining non-increasing order, then Carla Savage's 1989 paper does in fact solve your problem (without requiring "double moves" as in the 10th listed partition of 7 above).</p> <p>There are refinements of this operation in the literature. If you only allow a dot to "fall" into an adjacent part, i.e., from $(\ldots, p_i, p_{i+1}, \ldots)$ with $p_i \geq p_{i+1}+2$ to $(\ldots, p_i - 1, p_{i+1}+1, \ldots)$, that is called the "sandpile operation" or Brylawski's vertical rule. There is a transpose horizontal rule, and restictions of these called $\theta$ operations and "ice pile" operations, respectively. For some of these operations, the set of partitions of $n$ is not a connected graph, much less one with a Hamiltonian path. A survey article on these operations is available at <a href="http://www-rp.lip6.fr/~latapy/Publis/tcs04a.pdf" rel="nofollow">http://www-rp.lip6.fr/~latapy/Publis/tcs04a.pdf</a></p>