DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Andrew Baxter, Rutgers University, baxter{at} math [dot] rutgers [dot] edu

Lara Pudwell, Rutgers University, lpudwell {at} math [dot] rutgers [dot] edu

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: On the Minors of the Paths Matrix in a Forest

Speaker: Pierre Lalonde, Universite du Quebec a Montreal

Date: Thursday, November 1, 2007 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

Consider an acyclic graph (a forest) with edges labeled by a formal "weight". The paths matrix gives the weight of the path (product of the labels of its edges) between any two vertices of the graph. We will have a combinatorial interpretation of the minors of this matrix that will lead, via a sequence of bijections and sign-reversing involutions, to an enumerative formula. The result generalizes the Graham-Pollak theorem on the "distance-matrix" and many of its variants, which can often be recovered by linearization.