skip to content

An extensor tree theorem and a Tutte identity for graphs with distinguished port edges

Wednesday 9th April 2008 - 15:30 to 16:15
INI Seminar Room 1

Suppose Kirchhoff's laws for electricity are expressed by the rows of a matrix, each value of current flow and voltage (drop) along an edge is expressed by a separate variable, and those edges that model resistors each have a weight. Each non-resistor edge is distinguished as a port; each port's voltage and current relate the network to its environment.

Each matrix row can be expressed as a linear combination of basis (co-)vectors. The basis vectors function as rank 1 extensors which can also be thought of as fermionic (anticommuting) Grassmann-Berezin variables. The (anticommutative) exterior product of the rows followed by the operation equivalent to eliminating the resistor current and voltage variables produces the extensor we will study.

We prove that the resulting extensor obeys Tutte-like identities with deletion/contraction allowed only for the non-distinguished (resistor) edges, with anticommutative multiplication, and with sign-correction factors. We get as a result $\binom{2p}{p}$ different weigted matrix-tree theorems, where $p$ is the number of port edges. One application is a combinatorial but not bijective proof of Rayleigh's inequality alternative to that given by Choe.

Our construction and the Tutte identities extend to arbitrary full-rank matrices, but the coefficients in the enumeration fail to be $\pm 1$ without unimodularity.

We will also sketch analogies between our exterior algebraic formulation and the Grassmann-Berezin Calculus.

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons