Problem of the Week
Hilton Memorial Lecture
The matrix tree theorem asserts that the determinant of the reduced Laplacian matrix of a graph equals the number of spanning trees in the graph. By means of this theorem, solutions to linear resistive electrical network problems (and others, including equilibria of elastic networks, barycentric plane graph embeddings, Markov chains, and dissections of a square into squares) can be expressed by ratios of sums over certain tree or restricted forest enumerations. Each term in some such sums requires a sign derived from the relative orientations of certain pairs of edges in certain circuits or cocircuits associated with the corresponding forest.
A few people including Kirchhoff demonstrated enumerative solutions to resistive network problems with bijective arguments, bypassing the determinants. The enumerated sets have also been recognized as the sets of common bases of matroid pairs. The number of bases T in a single matroid is a well-known Tutte-Grothendieck invariant: It satisfies the deletion-contraction identity T(M) = T(M\e) + T(M/e) when e is neither a loop nor a coloop.
The work we report is part of a program to develop oriented matroid based solvability criteria and models for qualitative reasoning in terms of physical quantity signs for electrical network problems and some analogs. The main result we present is that the resistive ported electrical network's solution, expressed as a rank p extensor in an exterior algebra, is an extensor valued ``P''-ported Tutte-Grothendiek invariant on graphic oriented matroids. This kind of invariant is defined with particular set P with p elements distinguished so the T(M) = T(M\e) + T(M/e) identity is restricted to e not in P.
The pairing of oriented matroids with a common ground set (one for voltage, one for current) together with the operation of port insertion in the pair, which destroys their duality, seems to be fundamental for this theory. Other, non-dual pairs will be briefly described for which the natural condition for unique solvability for a network problem is that the appropriate oriented matroid pair has no common (non-zero) covector.
The talk will include a brief review of some classical and bijective proof methods for the matrix tree theorem and for enumeration based network problem solutions.