ACW (![[info]](http://p-stat.livejournal.com/img/userinfo.gif){kind=small} acw) wrote,@ 2007-05-12 12:10:00 |
|
11 nodes, and an example of proof technique
Yesterday I thought I had settled the case of 11 nodes, and I thought I'd describe how I went about it to satisfyjokermage's request for my proof technique. It is quite simple, but a bit tedious.
My first step is to see how many links I can jam in just by trial and error. In a comment to my last post,jokermage gives a diagram of a solution with 16 links on 10 nodes. To recap, it consists of two "bowties" sewn together by four extra links at the corners. I think of it as putting the two bowties on the two heads of a drum, with one bowtie rotated 90 degrees with respect to the other. This positions the corners so that the obvious way of tying up the drum generates the solution. (When I become a famous author of recreational math books, my books will have pretty diagrams in them!)
We can get a solution with 18 links on 11 nodes from the one described above, by adding an "ear" to one of the links that connect the two bowties. This ear has a single node, linked to both end-nodes of the old link to complete a triangle. If that link isn't already one side of a triangle, the resulting configuration is guaranteed to be square-free.
So I knew there was an 18-link solution. The next step was a little harder: to find a reasonable upper bound, so I'd know not to bother searching for solutions with more than such-and-such many links.
I've been doing this by a divide-and-conquer approach, breaking the problem up into cases. Each node participates in a certain number of links, and the number of links attached to a given node is called the degree of that node. In an 11-node configuration, the degree of each node must be 10 or less, because there are only 10 other nodes that a given node could be linked to. I organized my search into cases, classified by the degree of the most popular node in the configuration.
Suppose, for example, that there is a node of degree 10. Then there are at least 10 links, connecting the "hub" to the other 10 nodes. How many more links could be added connecting the "satellite" nodes?
Suppose there was a satellite, B, that was linked to two other satellites, A and C. If we call the hub X, then XABC would form a square, and that would be forbidden. So each satellite can be linked to at most one other satellite, and the best we can do is to link the 10 satellites in 5 pairs; the 10 spokes plus these 5 satellite links yields 15 links. This is not as good as the 18-link example we already have. Therefore, if we can in fact do better than 18 links, there will be no nodes of degree 10.
So, what if there is a node of degree 9? There are 9 spoke-links, and at most 4 links among the 9 satellites, but there is one node left over. We can link this node, at best, to one satellite. We can't link it to the hub, because that would give the hub degree 10. We can't link it to two satellites, because that would create a square involving the hub, the two satellites, and the extra node (which I will call a "comet"). So the most links we can pack in in this situation is 9+4+1 or 14. Therefore, if we can get more than 18 links, there will be no nodes of degree 9.
How about degree 8? There are 8 spoke-links, at most 4 links among the 8 satellites, and 2 nodes left over. Each of these 2 comets can be linked to at most one satellite, and then they can be linked to each other, for a total of 8+4+2+1 or 15 links. There can be no winners in this category.
For degree 7, we again count four categories of links: 7 spoke-links, 3 satellite links, and involving the 3 comets there can be at most 3 satellite-comet links and 3 comet-comet links, for a total of 16. It's important to note that we don't need to prove that we actually can pack in 3 links among the comets -- some such links might create squares, after all. The point here is that even if we could put 3 links among the 3 comets, we could achieve 16 links at most. So we can eliminate degree 7.
For degree 6, there will be 4 comets, and the four categories of links (hub-satellite, satellite-satellite, satellite-comet, comet-comet) will provide, respectively, 6, 3, 4, and 4 links. There can be no more than 4 links among the comets -- we have known that since we settled the 4-node case several days ago. The total is 17 links, and this isn't good enough for our high standards: we need 19 links to beat the example we constructed by trial-and-error.
For degree 5, there will be 5 comets, with at most 6 links among them. The four categories yield at most 5+2+5+6 = 18 links, which could tie our example but could not better it. Again note: we haven't proven that we could actually put 6 links among the 5 comets, and we don't need to.
For degree 4, there will be 6 comets, and at most 4+2+6+7 = 19 links. Thus, there is at least the possibility that if no node has more than 4 links, we can find a 19-link solution. So this case remains a possibility.
For degree 3, the comet argument stops working: there would be 7 comets, and (by this argument) at most 3+1+7+9 = 20 links. That would seem to be good news: there'd be a chance of finding record-breaking configurations with the degree limited to 3. But actually, a different kind of argument squelches this hope. Each link has two "ends", which connect to nodes. If none of the nodes has degree higher than 3, there can be at most 33 link-ends; actually there can only be 32, because there must be an even number of ends. This means there would be at most 16 links, regardless of how they are arranged.
For degree 2, this end-counting argument shows that there can be at most 11 links. For degree 1 the maximum number of links drops to 5, and of course for degree 0 there can be no links at all.
This means that if there are any 19-link examples, the maximum degree of any node will be 4. Let's check the end-counting argument to see if it might squelch the possibility. With degrees limited to 4, there will be at most 4 ends per node, thus at most 44 ends or 22 links. This is well over 19, so the 19-link limit still governs, and case 4 still remains open.
Now we consider the minimum degree. Suppose we actually had a solution with 19 links on 11 nodes. The highest degree displayed by any node must be 4, as laboriously shown above. What about the smallest degree? If it were 0, there would be an isolated node which we could just remove, leaving a 19 links on only 10 nodes; we know that's impossible. If it were 1, we could remove a node and the single link connected to it, leaving 18 links on 10 nodes, which is still impossible.
Could there be a node of degree 2? We could remove it and its two links, leaving 17 links on 10 nodes, and we know the best we can do is 16. So we have proven that all the nodes in a 19-link solution have degrees of either 3 or 4. Perhaps even degree 3 is impossible?
Well, if we had a solution with a node of degree 3, and we removed that node and its 3 connected links, that would leave 16 links on 10 nodes: this is still a possibility. In fact we can now get an exact census of the putative solution. It has 19 links, which means there are 38 ends to be distributed among 11 nodes. Each node must use at least 3 of these ends; that accounts for 33 of the 38 ends, leaving 5 unaccounted for. These must be distributed, one apiece, to 5 of the 11 nodes. So there will be 5 nodes of degree 4, and 6 nodes of degree 3.
When I reached this point in my reasoning, I looked at the 18-link example and took a census of the degrees of the nodes. There were 4 nodes of degree 4, 6 of degree 3, and 1 of degree 2. That meant that if I ran a new link between the degree-2 node and one of the degree-3 nodes, there would be 5 4's and 6 3's ... just like the putative solution. Could I do that without creating a square?
There were only 6 possibilities to check, which a symmetry argument reduced to 3. In only a minute after I made this realization, I had found a 19-link solution ... I thought. But later I spotted a square. Then I eliminated the other possibilities. Soon I was able to enumerate all the ways to attach a new degree-3 node to the old 16-link 10-node solution, and I showed that they all had squares.
I was not quite finished showing that 19 links was impossible. I knew that removing a degree-3 node from such a solution would leave 16 links on 10 nodes, and if it left the 16/10 solution I already knew about, this was impossible. But perhaps there was another 16/10 solution that could be extended?
This is my present state of knowledge. If the 16/10 solution is unique, there can be no 19/11 solution, and the only 18 links can be put on 11 nodes. But if there is another 16/10 solution, it might give rise to a 19/11 solution. At the moment I believe that the 16/10 solution is unique, but I haven't done a careful enumeration of the possibilities.
Yesterday I thought I had settled the case of 11 nodes, and I thought I'd describe how I went about it to satisfy
jokermage's request for my proof technique. It is quite simple, but a bit tedious.My first step is to see how many links I can jam in just by trial and error. In a comment to my last post,
jokermage gives a diagram of a solution with 16 links on 10 nodes. To recap, it consists of two "bowties" sewn together by four extra links at the corners. I think of it as putting the two bowties on the two heads of a drum, with one bowtie rotated 90 degrees with respect to the other. This positions the corners so that the obvious way of tying up the drum generates the solution. (When I become a famous author of recreational math books, my books will have pretty diagrams in them!)We can get a solution with 18 links on 11 nodes from the one described above, by adding an "ear" to one of the links that connect the two bowties. This ear has a single node, linked to both end-nodes of the old link to complete a triangle. If that link isn't already one side of a triangle, the resulting configuration is guaranteed to be square-free.
So I knew there was an 18-link solution. The next step was a little harder: to find a reasonable upper bound, so I'd know not to bother searching for solutions with more than such-and-such many links.
I've been doing this by a divide-and-conquer approach, breaking the problem up into cases. Each node participates in a certain number of links, and the number of links attached to a given node is called the degree of that node. In an 11-node configuration, the degree of each node must be 10 or less, because there are only 10 other nodes that a given node could be linked to. I organized my search into cases, classified by the degree of the most popular node in the configuration.
Suppose, for example, that there is a node of degree 10. Then there are at least 10 links, connecting the "hub" to the other 10 nodes. How many more links could be added connecting the "satellite" nodes?
Suppose there was a satellite, B, that was linked to two other satellites, A and C. If we call the hub X, then XABC would form a square, and that would be forbidden. So each satellite can be linked to at most one other satellite, and the best we can do is to link the 10 satellites in 5 pairs; the 10 spokes plus these 5 satellite links yields 15 links. This is not as good as the 18-link example we already have. Therefore, if we can in fact do better than 18 links, there will be no nodes of degree 10.
So, what if there is a node of degree 9? There are 9 spoke-links, and at most 4 links among the 9 satellites, but there is one node left over. We can link this node, at best, to one satellite. We can't link it to the hub, because that would give the hub degree 10. We can't link it to two satellites, because that would create a square involving the hub, the two satellites, and the extra node (which I will call a "comet"). So the most links we can pack in in this situation is 9+4+1 or 14. Therefore, if we can get more than 18 links, there will be no nodes of degree 9.
How about degree 8? There are 8 spoke-links, at most 4 links among the 8 satellites, and 2 nodes left over. Each of these 2 comets can be linked to at most one satellite, and then they can be linked to each other, for a total of 8+4+2+1 or 15 links. There can be no winners in this category.
For degree 7, we again count four categories of links: 7 spoke-links, 3 satellite links, and involving the 3 comets there can be at most 3 satellite-comet links and 3 comet-comet links, for a total of 16. It's important to note that we don't need to prove that we actually can pack in 3 links among the comets -- some such links might create squares, after all. The point here is that even if we could put 3 links among the 3 comets, we could achieve 16 links at most. So we can eliminate degree 7.
For degree 6, there will be 4 comets, and the four categories of links (hub-satellite, satellite-satellite, satellite-comet, comet-comet) will provide, respectively, 6, 3, 4, and 4 links. There can be no more than 4 links among the comets -- we have known that since we settled the 4-node case several days ago. The total is 17 links, and this isn't good enough for our high standards: we need 19 links to beat the example we constructed by trial-and-error.
For degree 5, there will be 5 comets, with at most 6 links among them. The four categories yield at most 5+2+5+6 = 18 links, which could tie our example but could not better it. Again note: we haven't proven that we could actually put 6 links among the 5 comets, and we don't need to.
For degree 4, there will be 6 comets, and at most 4+2+6+7 = 19 links. Thus, there is at least the possibility that if no node has more than 4 links, we can find a 19-link solution. So this case remains a possibility.
For degree 3, the comet argument stops working: there would be 7 comets, and (by this argument) at most 3+1+7+9 = 20 links. That would seem to be good news: there'd be a chance of finding record-breaking configurations with the degree limited to 3. But actually, a different kind of argument squelches this hope. Each link has two "ends", which connect to nodes. If none of the nodes has degree higher than 3, there can be at most 33 link-ends; actually there can only be 32, because there must be an even number of ends. This means there would be at most 16 links, regardless of how they are arranged.
For degree 2, this end-counting argument shows that there can be at most 11 links. For degree 1 the maximum number of links drops to 5, and of course for degree 0 there can be no links at all.
This means that if there are any 19-link examples, the maximum degree of any node will be 4. Let's check the end-counting argument to see if it might squelch the possibility. With degrees limited to 4, there will be at most 4 ends per node, thus at most 44 ends or 22 links. This is well over 19, so the 19-link limit still governs, and case 4 still remains open.
Now we consider the minimum degree. Suppose we actually had a solution with 19 links on 11 nodes. The highest degree displayed by any node must be 4, as laboriously shown above. What about the smallest degree? If it were 0, there would be an isolated node which we could just remove, leaving a 19 links on only 10 nodes; we know that's impossible. If it were 1, we could remove a node and the single link connected to it, leaving 18 links on 10 nodes, which is still impossible.
Could there be a node of degree 2? We could remove it and its two links, leaving 17 links on 10 nodes, and we know the best we can do is 16. So we have proven that all the nodes in a 19-link solution have degrees of either 3 or 4. Perhaps even degree 3 is impossible?
Well, if we had a solution with a node of degree 3, and we removed that node and its 3 connected links, that would leave 16 links on 10 nodes: this is still a possibility. In fact we can now get an exact census of the putative solution. It has 19 links, which means there are 38 ends to be distributed among 11 nodes. Each node must use at least 3 of these ends; that accounts for 33 of the 38 ends, leaving 5 unaccounted for. These must be distributed, one apiece, to 5 of the 11 nodes. So there will be 5 nodes of degree 4, and 6 nodes of degree 3.
When I reached this point in my reasoning, I looked at the 18-link example and took a census of the degrees of the nodes. There were 4 nodes of degree 4, 6 of degree 3, and 1 of degree 2. That meant that if I ran a new link between the degree-2 node and one of the degree-3 nodes, there would be 5 4's and 6 3's ... just like the putative solution. Could I do that without creating a square?
There were only 6 possibilities to check, which a symmetry argument reduced to 3. In only a minute after I made this realization, I had found a 19-link solution ... I thought. But later I spotted a square. Then I eliminated the other possibilities. Soon I was able to enumerate all the ways to attach a new degree-3 node to the old 16-link 10-node solution, and I showed that they all had squares.
I was not quite finished showing that 19 links was impossible. I knew that removing a degree-3 node from such a solution would leave 16 links on 10 nodes, and if it left the 16/10 solution I already knew about, this was impossible. But perhaps there was another 16/10 solution that could be extended?
This is my present state of knowledge. If the 16/10 solution is unique, there can be no 19/11 solution, and the only 18 links can be put on 11 nodes. But if there is another 16/10 solution, it might give rise to a 19/11 solution. At the moment I believe that the 16/10 solution is unique, but I haven't done a careful enumeration of the possibilities.
