Karel Devriendt: Matroid polytopes and the effective resistance

Abstract.

The study of electrical circuits has many connections to combinatorics and discrete mathematics. For example, in his seminal work Kirchhoff studied the relation between electrical flow and spanning trees and, more recently, Wagner introduced the half-plane property for polynomials inspired by an "energy passivity" property from electrical engineering. In this talk, I will draw a new connection between concepts from electrical circuit theory and combinatorics. The matroid polytope of a graph G is the polytope whose vertices are indicator vectors of the spanning trees of G. The effective resistance of an edge e in G is the fraction of spanning trees that contain e, counted with respect to some positive weights on the edges. We show that the vector of effective resistances is a point in the matroid polytope and that every interior point arises in this way for some choice of weights. A crucial ingredient for this result is the moment map on the Grassmannian. As one application, we characterize graphs with constant effective resistances on the edges and show that these graphs have strong connectivity properties. This talk is based on joint work with Raffaella Mulas.