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

Question

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 $k(N)$ be the least number such that a graph on $k(N)>1$ vertices exists that is the P-graph of exactly one partition of $N$ into $k(N)$ parts. It has been shown, for example, that $k(200)=6$. Determining $k(N)$ in general seems hopeless, but perhaps satisfactory estimates can be found. In particular, how big is, say, $k(1000)$? Less than $12$, as estimated by this proposer?

Answer 1

Old $13$-graph solution put at the bottom.

Edited to add: I think I've found a $11$-vertex $P$-graph that is unique: $187, 143, 91, 133, 95, 85, 87, 69, 46, 58, 6$.

This has a $P$-graph with a $6$-cycle and a $4$-wheel. Proof it's unique:

Assume we have a partition with this $P$-graph. This graph has an odd number of vertices, so there are an odd number of parts in the partition, so the number of even parts of the partition must be odd. As the largest clique in this graph is a triangle, $2$ either doesn't appear as a connecting prime, or it appears as a triangle. In the former case, a version of the AM-GM argument below shows the total would be too large. As such, $2$ must be one of the triangles in the $4$-wheel.

We now ignore the center of the $4$-wheel temporarily, and consider the rest: a $4$-cycle with a $2$, and a $6$-cycle. The goal is to minimize the total from them.

Assume the $29$ is in the $6$-cycle. Then we could decrease the total by "breaking" the $6$-cycle next to the $29$ (on either side), breaking the $4$-cycle (on either side of the $2$), and connecting them, with the $29$ next to the $2$. This will give us a $10$-cycle, which must have total at least $1002$, which is too large.

Similar reasoning puts $23$ on the other side of the $2$, and $3$ across. The filling of the $6$-cycle goes similarly. A generalization of this argument should show that the minimal sum of products from cycles comes from putting together $4$-cycles, with one "extra" cycle; these get filled in sequentially, starting with the most extreme to the least extreme. I don't think there is necessarily any restriction on where the "extra" cycle goes in the sequence, though.

This gives us a total of $994$. Remembering the center of the "wheel", we can now see that it must be divisible by at least $2$ primes, so it must be at least $6$. This gets us to $1000$, so we are done.

Along with @BrianHopkins modified $11$-graph, I think we've likely reached as small as we can get. Here's why:

The most effective technique so far seems to be to find some graph that has a minimum total near $1000$ (possibly using a parity criterion), and then adding to it to get to $1000$ exactly. It is possible to get a (slightly low) estimate for this total using the AM-GM inequality:

Let $k$ be the number of vertices in the "initial graph", and let $n$ be the minimum number of connecting primes in that graph. The product of all of the numbers at the vertices (the elements of the partition) is then at least the square of the product of those primes. The geometric mean is then the $k$th root of that square; the arithmetic mean must be at least as large, so the total is at least

$$\left( \prod_{i=1}^n p_i \right)^{\frac{2}{k}} k$$

This estimate is usually pretty good (low by ~50), as long as the cliques for each prime don't get too large (which may be the next avenue to check). We therefore want to know for which $n,k$ this is near, but below, $1000$.

For $k = 5$, the best $n$ is $7$, with an estimate of around $960$. This is too many edges to not form a triangle; there is no way to force $7$ connecting primes.

For $k=6$, the best $n$ is $7$, with an estimate of around $480$. Interestingly, the "odd-only" version is just over $1000$.

For $k=7$, the best $n$ is $8$, with an estimate of around $694$.

For $k=8$, the best $n$ is $9$, with an estimate of around $978$. This estimate is likely too large to allow a solution under $1000$, given all the approximations used. However, the $n=8$ odd-only version (estimate $824$) is what inspired my original answer.

For $k=9$, the best $n$ is still $9$, with an estimate of around $645$.

For $k=10$, the best $n$ is $10$, with an estimate of around $918$. This is the solution that underlies both my and @BrianHopkins answer.

As we have a solution for $11$, we don't need to go any further.

So if there is a smaller solution, my guess is that it will require some newer, slicker technique.

I did find a modification of this technique that may be useful: adding "tails" to graphs can make the minimum total higher, effectively by forcing larger differences between vertices. This modifies the above formula by allowing one of the prime factors to only appear once, rather than twice.

A graph that might be helpful: take a $6$-cycle and add a lengh $2$ "tail" at one vertex. If the $8$ connecting primes are odd, I think the minimum is $964$. I think it may be possible to get a $9$-graph with this, though adding an isolated point doesn't work.

Similarly, $K_{2,3}$ with a length $2$ "tail" at one of the $3$ vertices of degree $2$ can be under $1000$ (I got $903$ as a minimum), with no parity condition. I'm guessing this is the best chance for a smaller graph using this technique.

The "theta-hexagon" with a single tail seems possible; the minimum I got was $911$.

The odd-only two-tailed pentagon can get $939$.

Old $13$-graph:

Consider the $13$-vertex graph consisting of one $8$-cycle, one complete $4$-graph, and a singleton. This is a $P$-graph for $1000$ with the partition $115, 85, 187, 143, 91, 133, 57, 69, 29, 29, 29, 29, 4$. 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 doesn't 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 $19*23>120$, 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 singleton is at least $1$. This clearly only leaves room for the singleton to be $4$.

Answer 2

Consider a cycle of length greater than 3. If we label the edges of this P-graph by the gcd's, 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 k(1000) being less than 20, perhaps less than 12. At least it will show k(m) is at most 10 for some m not much smaller than 1000.

Gerhard "Maybe Freddy Can Help Here" Paseman, 2018.04.27.

Answer 3

After playing with lots of graph families and combinations, I think I have $k(1000) \le 12$, although the verification is not as clean as user44191's bound of 13.

The P-graph of the partition 187, 143, 119, 115, 95, 91, 87, 58, 57, 46, 1, 1 of 1000 consists of a 6-cycle, a 4-cycle, and 2 isolated vertices. In particular, using Gerhard's notion of labeling cycle edges, the 6-cycle edges have labels 2, 23, 5, 19, 3, 29 and the 4-cycle edges have labels 7, 13, 11, 17.

Is this the only 12-part partition of 1000 with this P-graph? Well, using 31 rather than 29 as the highest edge label makes the sum of the parts from the cycles at least 1004, so we need the smallest 10 primes. I don't know a good explanation for the {{2, 3, 5, 19, 23, 29}, {7, 11, 13, 17}} split other than I had Mathematica do them all. Once the subsets are chosen, the cyclic order of the edge labels follows a pattern as in Gerhard's answer: For $a < b < c < d$, the cyclic order $a,d,b,c$ avoids the largest possible product $cd$ as a part; then $a, e, c, d, b, f$ gives a minimum sum for six labels. This leads to parts 46, 115, 95, 57, 87, 58 on the 6-cycle and 91, 143, 187, 119 on the 4-cycle, total 998. The 2 isolated vertices contribute the two 1s to give 1000. (Tinkering with the order of the edge labels in either cycle increases the sum by at least 4.)

There is an assignment of the same labels to a 6-cycle and a 4-cycle that gives a sum of 994 (specifically, 5, 13, 7, 11, 17, 19 and 2, 23, 3, 29---changing the order of any of these labels increases the sum by at least 8), but no 2 parts corresponding to the isolated vertices can contribute 6 more to make a partition of 1000. Looking at just a 6- & 4-cycle with edges labeled with the first 10 primes, possible sums in increasing order start 994, 998, 1018 (each of these three happens to arise uniquely).

Bernardo, I enjoyed hearing about these at G4G13 and was pleased to find several related threads here. Thanks for all these nice questions.

---

As per User44191's suggestion, this example can be condensed into another verification that $k(1000) \le 11$. The partition of 1000 is 187, 143, 119, 115, 95, 91, 87, 58, 57, 46, 2. The P-graph is a 4-cycle and a 7-cycle with one additional edge connecting two vertices that would otherwise be two apart. The 4-cycle is the same as described above. From the earlier work, the other component is most easily described as adding to the 6-cycle a vertex labeled 2 with two edges labeled 2 connecting to the vertices for 46 and 58. From the uniqueness of the underlying 4- & 6-cycles summing to 998, any other vertex with edges would have a label greater than 2 and take the sum over 1000.

Answer 4

Freddy Barrera has shown that $k(1000)>5$ 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 $k(1000)<36$.

Answer 5

For the sake of completeness, here is the graph found by user44191 (see above), which shows that $k(1000)<11$:

Answer 6

@user44191 Based on your "cycles and tails" idea Freddy Barrera devised and checked by exhaustive computer search that from the following P-graph a unique partition of 1000 in nine parts can be recovered: