On the Hex/Nash connection game theorem

133 Views Asked by At

Consider a pair of planar dual (blue and red) electrical networks each with two terminal nodes. The resistances of intersecting edges are reciprocal to each other. The effective resistances betweeen the terminal nodes will be reciprocal to each other. (follows from Y-Delta equivalence transformation, for example).

Now, we play a connection game: two players take turns choosing an intersecting pair of edges, keeping their color's edge and deleting the opponent's edge. The final goal is to connect the corresponding terminal nodes by a path of edges. The question: is there always winner and loser and there's never tie like in the Hex/Nash connection game theorem? Please, see the picture for an example.

enter image description here

1

There are 1 best solutions below

0
On BEST ANSWER

At the end of the game after all choices were made, assign resistance tending to infinity to edges that were deleted and reciprocal resistance tending to zero for the eges that were left. Now, the effective resistance between terminal nodes will tend to zero if and only if there is a path berween them and to infinity if and only if the terminal nodes are disconnected, because of continuity of rational functions from resistances to effective resistances. The product of the effective resistances is 1, $$R_{RL}R_{UD}=1$$, because the dual networks are Y-Delta equivalent to two dual edges. See https://www.academia.edu/19760380/Circular_planar_e-networks, for more details on that. Therefore, by continuity the effective resistances cannot both tend to zero or infinity, so one tends to zero and another to infinity and we have a winner with a path and disconnected loser and the tie is impossible.