The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



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

Chaiken, S (Albany)
Wednesday 09 April 2008, 15:30-16:15

Seminar Room 1, Newton Institute


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.


[pdf ]




The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧