Description
Combinatorics seminar.
Speaker: Projesh Nath Choudhury.
Affiliation: IISc Bengaluru.
Date and Time: Monday 21 October, 3:00 pm - 4:00 pm.
Venue: Room 216, Department of Mathematics.
Title: Distance matrices of trees: invariants, old and new.
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 my talk:
1. I will 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 that
allowing greater freedom in the parameters leads to dependence on the
tree-structure.
4. Our results hold over an arbitrary unital commutative ring. This uses
Zariski density, which seems to be new in the field, yet is richly
rewarding.
We then discuss related results for arbitrary strongly connected graphs,
including a third, novel invariant. If time permits, a formula for
$D_T^{-1}$ will be presented for trees $T$, whose special case answers an
open problem of Bapat-Lal-Pati (Linear Alg. Appl. 2006), and which extends
to our general setting a result of Graham-Lovasz (Advances in Math. 1978).
(Joint with Apoorva Khare)