Least number of vertices in a graph with which one can uniquely recover some partition of N

Least number of vertices in a graph with which one can uniquely recover some partition of N

Given a partition of an integer N, its P-graph is the graph whose vertices are its parts, two of which are joined by an edge if and only if they have a common divisor greater than one i.e. they are not relatively prime. For an integer N, let kN be the least number such that a graph on kN1 vertices exists that is the P-graph of exactly one partition of N into kN parts. It has been shown, for example, that k200 6. Determining kN in general seems hopeless, but perhaps satisfactory estimates can be found. In particular, how big is, say, k1000 Less than 12, as estimated by this proposer

Consider a cycle of length greater than 3. If we label the edges of this P-graph by the gcds, then a vertex on this cycle between two labels a and b must be a multiple of ab, and a and b are coprime. Thus all the labels are pairwise coprime and greater than 1, so the smallest k many such labels can be no smaller than the smallest k primes. Suppose going around a ten cycle we have edge labels in order being 17 5 23 2 29 3 19 7 13 11. Then these vertices add up to at least 1000 at least 1002, unfortunately. If there is a labelling that yields a smaller vertex sum, then augment the graph with isolated vertices. Since we are using the smallest labels, I suspect this will lead to a proof of k1000 being less than 20, perhaps less than 12. At least it will show km is at most 10 for some m not much smaller than 1000. Gerhard Maybe Freddy Can Help Here Paseman, 2018.04.27.

Freddy Barrera has shown that k10005 by verifying that every graph with fewer than 6 vertices other than the singleton is the P-graph of at least two partitions of 1000. On the other hand, from the following graph on 35 vertices a unique partition of 1000 can be recovered, hence k100036.

Consider the 15-vertex graph consisting of one 8-cycle, one complete 4-graph, and 3 singletons. This is a P-graph for 1000 with the partition 115, 85, 187, 143, 91, 133, 57, 69, 29, 29, 29, 29, 2, 1, 1. I claim this is the only such partition. Proof: Take a partition with this graph. Because the number of vertices is odd, the number of even elements of the partition must be odd. 2 correspondingly can only appear in edges that are parts of triangles - so it is a connecting prime in the complete 4-graph, or not at all. Most importantly, it doesnt appear in the 8-cycle. The 8-cycle must then use 8 odd connecting primes. Simple construction shows the total for the 8-cycle must be at least 880 which is reached by the solution above - so the total for the 4-graph must be less than 120. Furthermore, the primes 3, 5, 7, 11, 13, 17 must be there for the total to remain below 1000, as the minimal total for 3, 5, 7, 11, 13, 19, 23, 29 is exactly 1000. A parity argument shows that at least one of the elements at the vertex of the 4-graph must be odd. Then as 1923120, the primes connecting to that vertex must all be the same - so the entire 4-graph must be divisible by that odd prime, and that prime is at least 19. The total from the 4-graph is therefore at least 76. Then the total in the 8-cycle is at most 924. This implies that the 8-cycle must have the lowest 8 primes 3, 5, 7, 11, 13, 17, 19, 23, and the prime in the 4-graph must be at least 29. The total from the 4-graph is at least 116, while the total from the 8-cycle is at least 880, and the total from the singletons is at least 3. This clearly only leaves room for one of the singletons to be increased by 1, giving the above partition. So we now know that k1000 leq 15. 1000 seems to be in a bit of a blind spot; its just less than the 1002 given by GerhardPaseman, and just more than what could be covered by an 8-cycle plus a small odd-sized graph uniquely.