20
$\begingroup$

I have been working on this problem for several months now but have not made much progress. It concerns the set of all integer partitions of n.

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.

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.

OOO               OOO
OO      --------  OOO
O   

My question: for what values of n does G(n) have a Hamiltonian path from (n) to (1,1,...,1)?

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?

Is there a determinate way to construct such paths?

I have only been able to construct paths for n = 1 to 6.

n=1 (trivial)

n=2: (2) => (1,1)

n=3:
(3) => (2,1) => (1,1,1)

n=4:
(4) => (3,1) => (2,2) => (2,1,1) => (1,1,1,1)

n=5: (5) => (4,1) => (3,2) => (2,2,1) => (3,1,1) => (2,1,1,1) => (1,1,1,1,1)

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)

None of the basic theorems about Hamiltonian paths have not helped me here.

$\endgroup$
1

6 Answers 6

18
$\begingroup$

What you want is known as a Gray code for integer partitions.

It exists.

See C. D. Savage, Gray code sequences of partitions, Journal of Algorithms 10 (1989) 577-595. Disclaimer: I haven't actually read this paper. Other sources such as this 1997 survey by Savage and these class notes don't say what the construction is but say that it's complicated.

$\endgroup$
1
  • $\begingroup$ Gosh, thanks! I would never have known about Gray codes if it wasn't for you! $\endgroup$
    – Burhan
    Feb 23, 2010 at 1:22
11
$\begingroup$

There are two great general sources for Gray codes on combinatorial objects you might enjoy:

  1. Frank Ruskey's "Combinatorial Generation" book

  2. Don Knuth's "Art of Computer Programming", Vol. 4, Fascicle 2-4 (published separately - all excellent), see https://www-cs-faculty.stanford.edu/~knuth/taocp.html

Preliminary versions of some of these can be downloaded from the internet archive.

$\endgroup$
1
  • $\begingroup$ Thank you for the links. I know you, Prof. I attended several of your IAP classes back when I was an undergrad at MIT. $\endgroup$
    – Burhan
    Feb 23, 2010 at 8:22
4
$\begingroup$

If you mean to allow any part to go down by 1 and any part (or 0) to go up by 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).

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 restrictions 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 https://www-complexnetworks.lip6.fr/~latapy/Publis/tcs04a.pdf.

$\endgroup$
3
$\begingroup$

There seems to be a general pattern indicated by your $n=6$ example. Here is a path for $n=7$:

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

I have written this so that it is obvious that all 15 partitions of 7 are accounted for. Note the 10th partition.

Here is one for $n = 8$:

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

$n=9$:

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  
$\endgroup$
3
  • $\begingroup$ What is the pattern here? $\endgroup$ Feb 24, 2010 at 1:26
  • $\begingroup$ It would probably have been better to say characteristics than pattern. The oscillatory behavior is what I had in mind, along with the appearance that even numbers are easier. $\endgroup$ Feb 24, 2010 at 3:15
  • 1
    $\begingroup$ i still have not read the savage paper. my university's online subscription does not cover that particular issue of the Journal of Algorithm, so i guess i will have to goto another library to read it. it seems that most of the secondary literature does not provide his explicit construction. but they all say it is complicated, and it would be a cool research project to try to simplify it (or show that a simplification is impossible). the ruskey book, p. 175, gives some details. $\endgroup$
    – Burhan
    Feb 25, 2010 at 16:41
2
$\begingroup$

Lo, these many years later...

I wrote a Python implementation of Dr. Savage's Gray-code-order partitions algorithm: https://gist.github.com/thquinn/97f3ed433a6fe5796dbbd054de851b84

$\endgroup$
0
$\begingroup$

I think your problem is related to the dominance partial-ordering of partitions; given partitions $\alpha=(\alpha_1,\alpha_2,\dots)$ and $\beta=(\beta_1,\beta_2,\dots)$ of $n$, we say that $\alpha$ dominates $\beta$, and write $\alpha\succeq\beta$, if $\alpha_1\geq\beta_1$, $\alpha_1+\alpha_2\geq\beta_1+\beta_2$ and so on. This partial order has a unique maximum element $(n)$ and a unique minimum element $(1^n)$. Now it is not a total order, but given $\alpha$ and $\beta$, there is a unique minimal partition $\mu$ such that $\mu\succeq\alpha$ and $\mu\succeq\beta$. Likewise there is a unique maximal partition $\nu$ such that $\alpha\succeq\nu$ and $\beta\succeq\nu$. Finally, dominance is generated by one-box-shifts i.e. given a partition $\alpha$, and $i<j$, such that $\alpha_i>\alpha_{i+1}=\alpha_{i+2}=\dots=\alpha_{j-1}<\alpha_j$, consider the partition $\beta$ with $\beta_i=\alpha_i-1$, $\beta_j=\alpha_j+1$ and $\beta_u=\alpha_u$, for $u\ne i,j$. Then $\alpha\succeq\beta$, and there is no $\gamma\ne\alpha,\beta$ with $\alpha\succeq\gamma\succeq\beta$. Moreover, for an arbitrary pair $\alpha\succeq\beta$, we can get from $\alpha$ to $\beta$ via a sequence of such one-box shifts.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.