9
$\begingroup$

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.

The P-graph of a certain mystery partition of 100 has 10 vertices and 42 edges. I've been told that no other partition of 100 has exactly the same P-graph. What is this mystery partition of 100?

$\endgroup$
  • 2
    $\begingroup$ Note that the complete graph on $10$ vertices has $45$ edges, so your graph is very close to being complete. $\endgroup$ – Arthur Apr 14 '17 at 15:38
  • $\begingroup$ Presumably these are proper sets, so that partition is of $100$ into distinct integers? Or is it really any partitions? $\endgroup$ – Thomas Andrews Apr 14 '17 at 15:46
  • 1
    $\begingroup$ Partitions with repetitions allowed. $\endgroup$ – Bernardo Recamán Santos Apr 14 '17 at 15:48
  • $\begingroup$ I have posted another instance of this problem at:puzzling.stackexchange.com/questions/51054/… $\endgroup$ – Bernardo Recamán Santos Apr 16 '17 at 17:40
5
$\begingroup$

Let $G$ be the desired graph. We can consider possible $\overline{G}$ on 10 vertices with 3 edges. There are 5 of them: $(7K_1, K_3)$, $(6K_1,K_{1, 3})$, $(6K_1, P_4)$, $(5K_1, P_2, P_3)$ and $(4K_1, 3P_2)$.

If $G \cong \overline{(6K_1, P_4)}$ then partition is not unique: $$ \begin{align} 100 &= 2 + 20 + 15 + 3 + 6 + 6 + 12 + 12 + 12 + 12\\ &= 2 + 20 + 15 + 3 + 6 + 6 + 6 + 12 + 12 + 18\\ &= 2 + 20 + 15 + 3 + 6 + 6 + 6 + 6 + 12 + 24\\ &= 2 + 20 + 15 + 3 + 6 + 6 + 6 + 6 + 18 + 18\\ &= 2 + 20 + 15 + 3 + 6 + 6 + 6 + 6 + 6 + 30 \end{align}$$

There are exactly 3 pairs of relatively prime numbers: $2$ and $15$, $2$ and $3$, $20$ and $3$, because last $6$ numbers are divisible by $2$ and $3$, $2$ and $20$ are divisible by $2$, $3$ and $15$ are divisible by $3$, $15$ and $20$ are divisible by $5$.

The same for $G \cong \overline{6K_1, K_{1, 3}}$: $$ \begin{align} 100 &= 5 + 6 + 12 + 12 + 10 + 10 + 10 + 10 + 10 + 15\\ &= 5 + 6 + 6 + 18 + 10 + 10 + 10 + 10 + 10 + 15 \end{align}$$

If $G \cong \overline{(7K_1, K_3)}$ then each vertex of $7K_1$ should have at least $3$ prime divisors to have edge with each of 3 pairwise non-adjacent vertices of $K_3$. Therefore there are $7$ numbers in partition that are at least $30$ each. Then it is impossible to get sum of $100$.

If $G \cong \overline{(4K_1, 3P_2)}$ then at least $4$ of vertices of $3P_2$ should have at least $3$ prime factors each (different for each vertex) therefore maximum of them is at least $3 \cdot 5 \cdot 7 = 105 > 100$. So this graph gives no partition.

If $G \cong \overline{(5K_1, P_2, P_3)}$, there is a partition: $$100 = 10 + 10 + 21 + 14 + 15 + 6 + 6 + 6 + 6 + 6.$$ To prove it is unique for this graph let us note that each vertex should have at least $2$ prime factors and there are at least $4$ prime factors in total. As shown above it is possible to take $2, 3, 5$ and $7$ as prime factors and $5$ of $6$ pairs as values for vertices. Also it is easy to see that this way gives minimum sum of values. If we take another prime factors or more then $2$ prime factors for at least $1$ vertex then we get even greater sum. Therefore this partition is unique for its P-graph.

$\endgroup$
4
$\begingroup$

I assumed no repetitions in the partition and no self-loops in the graph and found none that satisfied the requirements.

If repetitions are allowed in the partition there are 2977866 possible partitions of length 10 to explore. Regardless, it then becomes unclear whether two vertexes with the same integer should be linked.

Regardless, here is a graph with repetition in the partition having $\{15,12,10,10,10,10,10,10,8,5\}$ having 42 edges:

enter image description here

The 10a, 10b, etc. distinguish nodes that correspond to the repeated element 10.

Here is the graph found by Smylic:

enter image description here

Bernardo shows that they are not isomorphic.

$\endgroup$
  • $\begingroup$ This graph has 37 edges. $\endgroup$ – Smylic Apr 14 '17 at 19:28
  • $\begingroup$ By "graph" in this case I mean loopless graph, and by "partition", partition with repetitions. I am told, in that case, partition sought is unique. $\endgroup$ – Bernardo Recamán Santos Apr 14 '17 at 22:34
  • $\begingroup$ Oh! Let me re-run my simulations.... $\endgroup$ – David G. Stork Apr 14 '17 at 22:53
  • $\begingroup$ Yes, two different vertices with the same integer are linked. Besides, the graph being sought has 42 edges, not 37. And the mystery partition is such that its P-graph is not the P-graph of any other partition of 100. $\endgroup$ – Bernardo Recamán Santos Apr 14 '17 at 23:26
  • $\begingroup$ They are not isomorphic. Smylic's graph is G≅(5K1,P2,P3), while Stork's is G≅(6K1,P4). $\endgroup$ – Bernardo Recamán Santos Apr 15 '17 at 3:10

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.