The University of Michigan Combinatorics Seminar
Fall 2001
October 26, 4:10-5:00, 3866 East Hall

Networks, Polynomials, and Matroids

David Wagner

University of Waterloo


Consider a connected undirected (multi)graph G with a complex admittance (inverse resistance) ye associated to each edge. For any two vertices a and b of G, the effective admittance of (G,{ye}) between a and b is a rational function of the ye with the following property: if all the ye have positive real part, then the value of the function has positive real part as well. These are classical results in the electrical engineering literature. In this talk I will report on the current state of ongoing joint research with Y.B. Choe, J.G. Oxley, and A.D. Sokal, in which we generalize these ideas from graphs to more general matroids. We do have some necessary and some sufficient conditions, but the relevant classes of matroids seem to be very difficult to characterize. There is also a connection with the 1992 conjecture of Brown and Colbourn on location of zeros of reliability polynomials -- in particular, we find examples of matroids for which the strong form of the B-C conjecture fails.