Oct 3, 2003 addendum (Karnofsky)

I continued to work on the 10 resistor problem (Oct 3). Tightening and improving my algorithm, I computed the number of possible resistances using from 1 to 15 one ohm resistors as:

2, 4, 8, 16, 36, 80, 194, 506, 1400, 4039, 12044, 36406, 111324, 342447, 1064833

While these numbers are still increasing super-exponentially, the rate of increase of the exponent is slowing down; so I have no good prediction about were the series is headed.

As noted before, these counts all include infinity as a possible value, corresponding to an open circuit. What I didn't mention is that they don't count the value zero, corresponding to a short circuit. Hence you can increase or decrease these counts by one as a matter of taste.

I was also able to translate my ideas into standard graph theory concepts. It seems best to model the problem as a graph, one edge for each resistor and one added, distinguished edge that connects the two distinguished nodes of my previous model. Think of the distinguished edge as having a battery, rather than a resistor.

Then my results can be restated as: A graph is serial parallel indecomposable if and only if it has the complete graph with four nodes as a minor (where subgraphs must include the distinguished edge). A graph has no dangling parts that don't affect the effective resistance if and only if it is 2-connected. A new idea is that the essential graphs to generate are 2-connected ones with minimal order (edges per node) 3 (since the resistances of other graphs can be gotten numerically from these).

Finally, I noted that the set of resistances for 10 resistors was almost symmetrical under inversion. The reason for this is that if a graph of one ohm resistors is planar, then its planar dual has resistance the inverse of the original. The smallest non-planar graph has eight resistors. It seems essentially accidental that none of the eight or nine resistor non-planar graphs have effective resistances different than some planar graph with the same or fewer resistors.

The proof of the inversion property is to see that going to the planar dual interchanges the Kirchoff's laws equations for cycles around faces and those for current into nodes. If the resistances in the original graph (not necessarily one) are replaced by their inverses on corresponding edges in the dual, it turns out that a solution to the equations for the original can be easily transformed into a solution for the dual equations and, further, that the effective resistances will be inverses. Neat.

Allan Gottlieb