Combinatorics & algebra seminar-The additive-multiplicative distance matrix of a tree

Speaker: Apoorva Khare, Indian Institute of Science
Date and time: Tuesday, July 21, 2–3 pm
Place: Rome 771

Abstract: In 1971, Graham and Pollak showed that if D_T is the distance matrix of a tree T on n nodes, then det(D_T) depends only on n, not T. This independence from the tree structure has been verified for many different variants of weighted bi-directed trees. In this talk:

1. We present a general setting which strictly subsumes every known variant, and where we show that det(D_T) - as well as another graph invariant, the cofactor-sum - depends only on the edge-data, not the tree-structure.

2. More generally - even in the original unweighted setting - we strengthen the state-of-the-art, by computing the minors of D_T where one removes rows and columns indexed by equal-sized sets of pendant nodes. (In fact we go beyond pendant nodes.)

3. We explain why our result is the "most general possible", in two ways. First, allowing greater freedom in the parameters leads to dependence on the tree-structure. Second, the result holds over all unital commutative rings - shown via Zariski density, which seemed to be unutilized in the field, yet was richly rewarding.

If time permits, a formula for D_T⁻¹ will be presented, whose special case answers an open problem of Bapat-Lal-Pati (LAA 2006), and which extends to our general setting a result of Graham-Lovasz (Adv. Math. 1978). This is joint work with Projesh Nath Choudhury.