Given a multiset of positive integers, its P-graph is the loopless graph whose vertex set consists of those integers, any two of which are joined by an edge if they have a common divisor greater than 1, that is, they are not relatively prime. There are 5,371,315,400 partitions of 130 of which 507,334 are partitions into six parts. I have been told that there is just one of these that can be uniquely recovered from its P-graph. Which is it?

  • $\begingroup$ Could you give us the degree sequence as a hint? $\endgroup$ – NL628 Jan 15 '18 at 3:49
  • $\begingroup$ Is a computer bash allowed? $\endgroup$ – NL628 Jan 15 '18 at 3:49
  • $\begingroup$ Yes, allowed @NL628. $\endgroup$ – Bernardo Recamán Santos Jan 15 '18 at 10:35


I had originally found three P-graphs but, as OP correctly pointed out, two of them were invalid and coincided with multiple partitions. This was due to an error in my reasoning.

With the help of a computer, I found the solution can be represented diagramatically as follows:

enter image description here

Together with the corresponding partition, the diagram appears as follows

enter image description here

Explanation of method

1. List all partitions of length $6$.
2. Compute the adjacency matrix of the p-graph associated to each partition.
3. Split the set of unique adjacency matrices into those which appear more than once, $S$, and those that appear exactly once, $T$
4. Partition the set, $T$, into equivalence classes where two matrices are equivalent if they have the same element sum.
5. For each equivalence class $\Gamma$:
    (i) For the first element, $m$, in the class, compute the list, $L$, of adjacency matrices related to that element by interchanging indices
    (ii) Find the list, $l$, of all matrices in $\Gamma$ which appear in $L$.
    (iii) If the length of $l$ is $1$ then $m$ is a candidate solution and we add it to a set $M$.
    (iv) Remove all elements of $l$ from $\Gamma$.
    (v) If $|\Gamma|> 0$, return to (i). If $|\Gamma|=0$, break.
6. For each element $m$ in $M$:
    (i) Recompute the list of adjacency matrices $L_m$ related to $m$ by interchanging indices.
    (ii) For each element of $L_m$, check if it is an element of $S$. If not for any element of $L_m$, then $m$ is a solution.

  • 1
    $\begingroup$ Freddy Barrera, who devised this puzzle, has verified by extensive computer search that for the second of the above graphs there are 52 possible partitions. A different one from the one shown is 3, 4, 25, 30, 30, 38. Likewise for the third of the above graphs there are 2517 possible partitions, 3, 4, 7, 18, 49, 49, being one of them different from yours. The first of the above graphs with its corresponding partition is the partition sought. $\endgroup$ – Bernardo Recamán Santos Jan 15 '18 at 22:23
  • $\begingroup$ I agree with your assessment. I must have made a mistake somewhere. I'll edit the answer and have a look through my code to see how this was missed. Thank you for the puzzle. $\endgroup$ – hexomino Jan 16 '18 at 9:40
  • $\begingroup$ Ah, yes, there is a flaw in step 3 and checking against the discarded set, I'll edit appropriately. $\endgroup$ – hexomino Jan 16 '18 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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