Algebraic Combinatorics Seminar - Melanie Dennis

Title: Lewis Carroll and the Red Hot Potato

Abstract:

The Lewis Carroll identity expresses the determinant of a matrix in terms of subdeterminants obtained by deleting one row and column or a pair of rows and columns. Using the matrix tree theorem, we can convert this into an equivalent identity involving sums over pairs of forests. Unlike the Lewis Carroll Identity, the Forest Identity involves no minus signs. Using the Involution Principle, we can pull back Zeilberger's proof of the Lewis Carroll Identity to a bijective proof of the Forest Identity. This bijection is implemented by the Red Hot Potato algorithm, so called because the way edges get tossed back and forth between the two forests is reminiscent of the children's game of hot potato.