Skip to main content
To KTH's start page To KTH's start page

Karel Devriendt: Matroid polytopes and the effective resistance

Time: Tue 2023-04-25 10.15

Location: 3721, Lindstedtsvägen 25, and Zoom

Video link: Meeting ID: 621 8808 6001

Participating: Karel Devriendt (MPI-MiS Leipzig)

Export to calendar


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.